# TreeMap

![image-20220303230207869](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-c643ea39ca0ba5301941dbc44f29c7430140dadf%2Fimage-20220303230207869.png?alt=media)

![image-20220303230515426](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-842a5add378a4ead8a16889ae60a02643e8522ad%2Fimage-20220303230515426.png?alt=media)

**特点：**

1. 唯一
2. 有序

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

源代码：

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

   ![image-20220303231405606](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-aae87ac8683e3a1b5639be0bc3e7e0b2c1f73959%2Fimage-20220303231405606.png?alt=media)
2. 树的根节点

   ![image-20220303232034660](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-cb3bec61b951dd3671ffc61a9430921a69cf701e%2Fimage-20220303232034660.png?alt=media)
3. 集合的长度

   ![image-20220303232055954](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-f3e2d25200658f57d0373533101e62e5a66f5e43%2Fimage-20220303232055954.png?alt=media)
4. put方法

   ```java
   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;
   }
   ```