TreeMap
特点:
唯一
有序
原理内部是红黑树,key遵循红黑树的特点,放入的元素需要实现比较器,或者指定外部比较器。
源代码:
用于给key排序的比较器
树的根节点
集合的长度
put方法
public V put(K key, V value) { Entry<K,V> t = root; // 第一次放入,那么该元素就是根节点 if (t == null) { compare(key, key); // type (and possibly null) check // 将key和value包装为 Entry 对象,设置根节点 root = new Entry<>(key, value, null); size = 1; modCount++; return null; } // 非第一次放入 int cmp; Entry<K,V> parent; Comparator<? super K> cpr = comparator; // 如果外部比较器不存在,则使用内部比较器比较 if (cpr != null) { // 循环比较所有元素 do { parent = t; // 如果比当前的节点小,那么下次比较他的左节点 // 如果比当前的节点大,那么下次比较他的右节点 // 如果与当前节点相同,直接替换当前节点的值 cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } // 如果外部比较器存在,则使用外部比较器比较 else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") 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); } // 找到合适的位置后,创建Entry,并插入到树中 Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }
最后更新于