TreeMap中的put方法详解

忘是亡心i 2021-12-10 22:19 445阅读 1赞

public V put(K key, V value) \{  
//用t表示二叉树的当前节点  
Entry<K,V> t = root;  
//t为null表示一个空树，即TreeMap中没有任何元素，直接插入  
if (t == null) \{  
//比较key值，个人觉得这句代码没有任何意义，空树还需要比较、排序？  
compare(key, key); // type (and possibly null) check  
//将新的key-value键值对创建为一个Entry节点，并将该节点赋予给root  
root = new Entry<>(key, value, null);  
//容器的size = 1，表示TreeMap集合中存在一个元素  
size = 1;  
//修改次数 + 1  
modCount++;  
return null;  
\}  
int cmp; //cmp表示key排序的返回结果  
Entry<K,V> parent; //父节点  
// split comparator and comparable paths  
Comparator<? super K> cpr = comparator; //指定的排序算法  
//如果cpr不为空，则采用既定的排序算法进行创建TreeMap集合  
if (cpr != null) \{  
do \{  
parent = t; //parent指向上次循环后的t  
//比较新增节点的key和当前节点key的大小  
cmp = cpr.compare(key, t.key);  
//cmp返回值小于0，表示新增节点的key小于当前节点的key，则以当前节点的左子节点作为新的当前节点  
if (cmp < 0)  
t = t.left;  
//cmp返回值大于0，表示新增节点的key大于当前节点的key，则以当前节点的右子节点作为新的当前节点  
else if (cmp > 0)  
t = t.right;  
//cmp返回值等于0，表示两个key值相等，则新值覆盖旧值，并返回新值  
else  
return t.setValue(value);  
\} while (t != null);  
\}  
//如果cpr为空，则采用默认的排序算法进行创建TreeMap集合  
else \{  
if (key == null) //key值为空抛出异常  
throw new NullPointerException();  
/\* 下面处理过程和上面一样 */  
Comparable<? super K> k = (Comparable<? super K>) key;  
do \{  
parent = t;  
cmp = k.compareTo(t.key);  
if (cmp < 0)  
t = t.left;  
else if (cmp > 0)  
t = t.right;  
else  
return t.setValue(value);  
\} while (t != null);  
\}  
//将新增节点当做parent的子节点  
Entry<K,V> e = new Entry<>(key, value, parent);  
//如果新增节点的key小于parent的key，则当做左子节点  
if (cmp < 0)  
parent.left = e;  
//如果新增节点的key大于parent的key，则当做右子节点  
else  
parent.right = e;  
/*  
\* 上面已经完成了排序二叉树的的构建，将新增节点插入该树中的合适位置  
\* 下面fixAfterInsertion()方法就是对这棵树进行调整、平衡，具体过程参考上面的五种情况  
\*/  
fixAfterInsertion(e);  
//TreeMap元素数量 + 1  
size++;  
//TreeMap容器修改次数 + 1  
modCount++;  
return null;  
\}

## 总结： ##

在TreeMap中存储数据的时候，首先是判断根节点是否为空，也就是我们上课看的代码中Entry<K,V> t = root;if (t == null) 这两句话，如果根节点为空，我们就可以直接往根节点中存储数据，并将这个数据作为树的根节点，也就是代码中的root = new Entry<>(key, value, null);这里面的null说明此时的根节点还是指向空。在根节点的储存过程中注意根节点的第一个储存数据不能储存成为null，这样会报错（ throw new NullPointerException();因为在对null进行强转的时候会出现空指针  
接下来的存储就是比较存储，如果将要存储的值比当前节点的值要小，就存储为dang前值的左节点，如果大于当前节点的值的话就储存为右节点，本处要注意，这里是一直沿着树的枝桠比较，知道有位置可放的情况下才会新建一个书的枝桠。