TreeMap

image-20220303230207869

image-20220303230515426

特点：

1. 唯一

2. 有序

原理内部是红黑树，key遵循红黑树的特点，放入的元素需要实现比较器，或者指定外部比较器。

源代码：

1. 用于给key排序的比较器

   

   image-20220303231405606
2. 树的根节点

   

   image-20220303232034660
3. 集合的长度

   

   image-20220303232055954
4. 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;
   }