1、TreeMap-源码分析-底层数据结构

  1. 1、TreeMap的存储结构是红黑树，它包含几个重要的成员变量： root, size, comparator。
  2. 　　1-1、root 是红黑数的根节点。它是Entry类型，Entry是红黑数的节点，它包含了红黑数的6个基本组成成分：key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)。Entry节点根据key进行排序，Entry节点包含的内容为value。 
  3. 　　1-2、红黑数排序时，根据Entry中的key进行排序；Entry中的key比较大小是根据比较器comparator来进行判断的。
  4. 　　1-3、size是红黑数中节点的个数。
  6. 2、TreeMap主要成员属性：
  7.     /**
  8.      * 默认情况下comparator为null，这个时候按照key的自然顺序进行排序，
  9.       * 如果想让Map的自动排序按照我们自己的规则，这个时候你就需要传递Comparator的实现类
  10.      * @serial
  11.      */
  12.     private final Comparator<? super K> comparator;
  14.     /**
  15.      * TreeMap的存储结构既然是红黑树，那么必然会有唯一的根节点。
  16.      */
  17.     private transient Entry<K,V> root;
  19.     /**
  20.      * Map中key-value对的数量，也即是红黑树中节点Entry的数量
  21.      */
  22.     private transient int size = 0;
  24.     /**
  25.      * 红黑树结构的调整次数
  26.      */
  27.     private transient int modCount = 0;

2、TreeMap-源码分析-构造函数

  1. 1、TreeMap提供了四个构造方法，实现了方法的重载。
  2.     1-1、无参构造方法中比较器的值为null,采用自然排序的方法，如果指定了比较器则称之为定制排序.
  3.         1-1-1、自然排序：TreeMap的所有key必须实现Comparable接口，所有的key都是同一个类的对象
  4.         1-1-2、定制排序：创建TreeMap对象传入了一个Comparator对象，该对象负责对TreeMap中所有的key进行排序，采用定制排序不要求Map的key实现Comparable接口。
  6. 2、源码代码：
  8.     /**
  9.      * 默认构造函数，按照key的自然顺序排列。
  10.      * 插入到映射中的所有键都必须实现comparable接口。
  11.      */
  12.     public TreeMap() {
  13.         comparator = null;
  14.     }
  16.     /**
  17.      * 传递Comparator具体实现，按照该实现规则进行排序
  18.      * 插入到映射中的所有键都必须实现comparable接口。
  19.      */
  20.     public TreeMap(Comparator<? super K> comparator) {
  21.         this.comparator = comparator;
  22.     }
  24.     /**
  25.      * 传递一个map实体构建TreeMap,按照默认规则排序
  26.      * 插入到映射中的所有键都必须实现comparable接口。
  27.      */
  28.     public TreeMap(Map<? extends K, ? extends V> m) {
  29.         comparator = null;
  30.         putAll(m);
  31.     }
  33.     /**
  34.      * 传递一个map实体构建TreeMap,按照传递的map的排序规则进行排序。
  35.      * 这个方法以线性时间运行[涉及线性时间排序算法]。
  36.      */
  37.     public TreeMap(SortedMap<K, ? extends V> m) {
  38.         comparator = m.comparator();
  39.         try {
  40.             buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
  41.         } catch (java.io.IOException cannotHappen) {
  42.         } catch (ClassNotFoundException cannotHappen) {
  43.         }
  44.     }

3、TreeMap-源码分析-添加元素

  1. 1、添加元素，调用的.put()方法，TreeMap的put方法
  2. 2、.put()方法源码分析：
  3.     public V put(K key, V value) {
  4.         Entry<K,V> t = root;
  5.         /**
  6.          * 如果根节点都为null，还没建立起来红黑树，我们先new Entry并赋值给root把红黑树建立起来，这个时候红黑树中已经有一个节点了，同时修改操作+1。
  7.          */
  8.         if (t == null) {
  9.             compare(key, key); // type (and possibly null) check
  11.             root = new Entry<>(key, value, null);
  12.             size = 1;
  13.             modCount++;
  14.             return null;
  15.         }
  16.         //如果节点不为null,定义一个cmp，这个变量用来进行二分查找时的比较；
  17.         int cmp;
  18.         //定义parent，是new Entry时必须要的参数
  19.         Entry<K,V> parent;
  20.         // cpr表示有无自己定义的排序规则，分两种情况遍历执行
  21.         Comparator<? super K> cpr = comparator;
  22.         //有自定义的排序规则的情况。
  23.         if (cpr != null) {
  24.             /**
  25.              * 从root节点开始遍历，通过二分查找逐步向下找
  26.              * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法
  27.              * cpr.compare(key, t.key)比较传入的key和根节点的key值，如果传入的key<root.key，那么
  28.              * 继续在root的左子树中找，从root的左孩子节点（root.left）开始：如果传入的key>root.key,
  29.              * 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;如果恰好key==root.key，
  30.              * 那么直接根据root节点的value值即可。
  31.              * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
  32.              *
  33.              * 需要注意的是：这里并没有对key是否为null进行判断，建议自己的实现Comparator时应该要考虑在内
  34.              */
  35.             do {
  36.                 parent = t;
  37.                 cmp = cpr.compare(key, t.key);
  38.                 if (cmp < 0)
  39.                     t = t.left;
  40.                 else if (cmp > 0)
  41.                     t = t.right;
  42.                 else
  43.                     return t.setValue(value);
  44.             } while (t != null);
  45.         }
  46.         else {
  47.             //当默认排序时，key值是不能为null的，为null会抛出异常
  48.             if (key == null)
  49.                 throw new NullPointerException();
  50.             @SuppressWarnings("unchecked")
  51.                 Comparable<? super K> k = (Comparable<? super K>) key;
  52.             //通过二分查找
  53.             do {
  54.                 parent = t;
  55.                 cmp = k.compareTo(t.key);
  56.                 if (cmp < 0)
  57.                     t = t.left;
  58.                 else if (cmp > 0)
  59.                     t = t.right;
  60.                 else
  61.                     return t.setValue(value);
  62.             } while (t != null);
  63.         }
  64.         /**
  65.          * 执行到这里，说明前面并没有找到相同的key,节点已经遍历到最后了，我们只需要new一个Entry放到
  66.          * parent下面即可，但放到左子节点上还是右子节点上，就需要按照红黑树的规则来。
  67.          */
  68.         Entry<K,V> e = new Entry<>(key, value, parent);
  69.         if (cmp < 0)
  70.             parent.left = e;
  71.         else
  72.             parent.right = e;
  73.         /**
  74.          * 节点加进去了，红黑树,一般情况下加入节点都会对红黑树的结构造成破坏，
  75.          * 我们需要通过一些操作来进行自动平衡处置，如【变色】【左旋】【右旋】
  76.          */
  77.         fixAfterInsertion(e);
  78.         size++;
  79.         modCount++;
  80.         return null;
  81.     }
  83.     /**
  84.         红黑树插入时自平衡调整的逻辑：
  85.             无需调整                        
  86.                 当父节点为黑色时插入子节点
  87.             【变色】即可实现平衡                                     
  88.                 空树插入根节点，将根节点红色变为黑色
  89.                 父节点和叔父节点都为红色
  90.             【旋转+变色】才可实现平衡
  91.                 父节点为红色左节点，叔父节点为黑色，插入左子节点，那么通过【左左节点旋转】
  92.                 父节点为红色左节点，叔父节点为黑色，插入右子节点，那么通过【左右节点旋转】
  93.                 父节点为红色右节点，叔父节点为黑色，插入左子节点，那么通过【右左节点旋转】
  94.                 父节点为红色右节点，叔父节点为黑色，插入右子节点，那么通过【右右节点旋转】                            -                            
  95.     */
  96.     /** From CLR */
  97.     private void fixAfterInsertion(Entry<K,V> x) {
  98.         //新插入的节点为红色节点
  99.         x.color = RED;
  100.         //父节点为黑色时，并不需要进行树结构调整，只有当父节点为红色时，才需要调整平衡
  101.         while (x != null && x != root && x.parent.color == RED) {
  102.             //如果父节点是左节点
  103.             if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
  104.                 //获取x节点的父节点的兄弟节点，判断出x节点的父节点为左节点，所以直接取右节点
  105.                 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
  106.                 //如果叔父节点为红色，对应于"父节点和叔父节点都为红色"，此时通过变色即可实现平衡
  107.                 if (colorOf(y) == RED) {
  108.                     setColor(parentOf(x), BLACK);    //父节点设置为黑色，
  109.                     setColor(y, BLACK);                //叔父节点设置为黑色，
  110.                     setColor(parentOf(parentOf(x)), RED); //祖父节点设置为红色
  111.                     x = parentOf(parentOf(x));    //x=p.parent.parent
  112.                 } else {//如果叔父节点为黑色，则插入右子节点，通过【左右节点旋转】
  113.                     //先进行父节点左旋
  114.                     if (x == rightOf(parentOf(x))) {
  115.                         x = parentOf(x);
  116.                         //进行父节点左旋
  117.                         rotateLeft(x);
  118.                     }
  119.                     //设置父节点和祖父节点颜色
  120.                     setColor(parentOf(x), BLACK);
  121.                     setColor(parentOf(parentOf(x)), RED);
  122.                     //进行祖父节点右旋
  123.                     rotateRight(parentOf(parentOf(x)));
  124.                 }
  125.             } else {//父节点是右节点的情况，且颜色为红色
  126.                 //获取x节点的父节点的兄弟节点，判断出x节点的父节点为右节点，所以直接取左节点
  127.                 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
  128.                 //叔父节点，是一个左节点，颜色为红色时，符合"父节点和叔父节点都为红色"
  129.                 if (colorOf(y) == RED) {
  130.                     setColor(parentOf(x), BLACK);
  131.                     setColor(y, BLACK);
  132.                     setColor(parentOf(parentOf(x)), RED);
  133.                     x = parentOf(parentOf(x));
  134.                 } else {//如果插入节点是黑色，插入的是左子节点，通过【右左节点旋转】
  135.                     if (x == leftOf(parentOf(x))) {
  136.                         //先进行父节点右旋
  137.                         x = parentOf(x);
  138.                         rotateRight(x);
  139.                     }
  140.                     setColor(parentOf(x), BLACK);
  141.                     setColor(parentOf(parentOf(x)), RED);
  142.                     //进行祖父节点左旋
  143.                     rotateLeft(parentOf(parentOf(x)));
  144.                 }
  145.             }
  146.         }
  147.         //根节点必须为黑色
  148.         root.color = BLACK;
  149.     }
  151.     /** 
  152.         From CLR,左旋的方法逻辑 
  153.         左旋规则：逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点
  154.         [!!!]方法里的= 赋值是指 指针的指向。
  155.     */
  156.     private void rotateLeft(Entry<K,V> p) {
  157.         if (p != null) {
  158.             /**
  159.              * 断开当前节点p与其右子节点的关联，重新将节点p的右子节点的地址指向节点p的右子节点的左子节点
  160.              * 这个时候节点r没有父节点
  161.              */
  162.             Entry<K,V> r = p.right;
  163.             p.right = r.left;
  164.             if (r.left != null)
  165.                 //将节点p作为节点r的父节点
  166.                 r.left.parent = p;2
  167.             //将节点p的父节点和r的父节点指向同一处        
  168.             r.parent = p.parent;
  169.             //p的父节点为null，则将节点r设置为root
  170.             if (p.parent == null)
  171.                 root = r;
  172.             //如果节点p是左子节点，则将该左子节点替换为节点r
  173.             else if (p.parent.left == p)
  174.                 p.parent.left = r;
  175.             else
  176.                 //如果节点p为右子节点，则将该右子节点替换为节点r
  177.                 p.parent.right = r;
  178.             //重新建立p与r的关系
  179.             r.left = p;
  180.             p.parent = r;
  181.         }
  182.     }
  184.     /** From CLR,右旋的方法逻辑 */
  185.     private void rotateRight(Entry<K,V> p) {
  186.         if (p != null) {
  187.             Entry<K,V> l = p.left;
  188.             p.left = l.right;
  189.             if (l.right != null) l.right.parent = p;
  190.             l.parent = p.parent;
  191.             if (p.parent == null)
  192.                 root = l;
  193.             else if (p.parent.right == p)
  194.                 p.parent.right = l;
  195.             else p.parent.left = l;
  196.             l.right = p;
  197.             p.parent = l;
  198.         }
  199.     }

3-1、TreeMap-源码分析-添加元素-左旋代码逻辑-示意图


容器(Map)-TreeMap-源码分析 - 图2

3-2、TreeMap-源码分析-添加元素-put代码流程逻辑-示意图


容器(Map)-TreeMap-源码分析 - 图3

4、TreeMap-源码分析-获取元素

  1. 1、获取元素-.get()方法：
  2. 2、源代码：
  3.     // 获取"键(key)"对应的"值(value)"
  4.     public V get(Object key) {
  5.         Entry<K,V> p = getEntry(key);
  6.         return (p==null ? null : p.value);
  7.     }
  9.     // 获取"键"为key的节点(p)
  10.     /**
  11.      * 默认情况下，即：比较器为空
  12.      * 从root节点开始遍历，通过二分查找逐步向下找
  13.      * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过k.compareTo(p.key)比较传入的key和
  14.      * 根节点的key值；
  15.      * 如果传入的key<root.key, 那么继续在root的左子树中找，从root的左孩子节点（root.left）开始；
  16.      * 如果传入的key>root.key, 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;
  17.      * 如果恰好key==root.key，那么直接根据root节点的value值即可。
  18.      * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
  19.      */
  20.     final Entry<K,V> getEntry(Object key) {
  21.         // Offload comparator-based version for sake of performance
  22.         //比较器不为空的情况
  23.         if (comparator != null)
  24.             return getEntryUsingComparator(key);
  25.         if (key == null)
  26.             throw new NullPointerException();
  27.         @SuppressWarnings("unchecked")
  28.             Comparable<? super K> k = (Comparable<? super K>) key;
  29.         Entry<K,V> p = root;
  30.         while (p != null) {
  31.             int cmp = k.compareTo(p.key);
  32.             if (cmp < 0)
  33.                 p = p.left;
  34.             else if (cmp > 0)
  35.                 p = p.right;
  36.             else
  37.                 return p;
  38.         }
  39.         return null;
  40.     }
  42.     //使用自定义比较器，获取"键"为key的节点(p)
  43.     /**
  44.      * 从root节点开始遍历，通过二分查找逐步向下找：
  45.      * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法
  46.      * cpr.compare(key, t.key)比较传入的key和根节点的key值，
  47.      * 如果传入的key<root.key，那么继续在root的左子树中找，从root的左孩子节点（root.left）开始：
  48.      * 如果传入的key>root.key,那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;
  49.      * 如果恰好key==root.key，那么直接根据root节点的value值即可。
  50.      * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
  51.      */
  52.     final Entry<K,V> getEntryUsingComparator(Object key) {
  53.         @SuppressWarnings("unchecked")
  54.             K k = (K) key;
  55.         Comparator<? super K> cpr = comparator;
  56.         if (cpr != null) {
  57.             Entry<K,V> p = root;
  58.             while (p != null) {
  59.                 int cmp = cpr.compare(k, p.key);
  60.                 if (cmp < 0)
  61.                     p = p.left;
  62.                 else if (cmp > 0)
  63.                     p = p.right;
  64.                 else
  65.                     return p;
  66.             }
  67.         }
  68.         return null;
  69.     }

5、TreeMap-源码分析-删除元素

  1. 1、删除元素：.remove()方法
  2. 2、源代码：
  3.     // 先是找到这个节点，直接调用了.getEntry(Object key)
  4.     public V remove(Object key) {
  5.         // 先是找到这个节点
  6.         Entry<K,V> p = getEntry(key);
  7.         if (p == null)
  8.             return null;
  10.         V oldValue = p.value;
  11.         //找到后的删除操作
  12.         deleteEntry(p);
  13.         return oldValue;
  14.     }
  16.     /**
  17.         删除操作的原理：
  18.             1.删除的是根节点，则直接将根节点置为null;
  19.             2.待删除节点的左右子节点都为null，删除时将该节点置为null;
  20.             3.待删除节点的左右子节点有一个有值，则用有值的节点替换该节点即可；
  21.             4.待删除节点的左右子节点都不为null，则找前驱或者后继，将前驱或者后继的值复制到该节点中，然后删除前驱或者后继(前驱：左子树中值最大的节点，后继：右子树中值最小的节点)
  22.      */
  23.     private void deleteEntry(Entry<K,V> p) {
  24.         modCount++;
  25.         size--;
  27.         //当左右子节点都不为null时，通过successor(p)遍历红黑树找到前驱或者后继
  28.         //前驱：左子树中值最大的节点，后继：右子树中值最小的节点
  29.         if (p.left != null && p.right != null) {
  30.             //一个节点的按次序排序后的下一个节点
  31.             Entry<K,V> s = successor(p);
  32.             //将前驱或者后继的key和value复制到当前节点p中，然后删除节点s(通过将节点p引用指向s)
  33.             p.key = s.key;
  34.             p.value = s.value;
  35.             p = s;
  36.         } // p has 2 children
  38.         /**
  39.          * 至少有一个子节点不为null，直接用这个有值的节点替换掉当前节点，给replacement的parent属性赋值,给parent节点的left属性和right属性赋值，同时要记住叶子节点必须为null,然后用fixAfterDeletion方法
  40.          * 进行自平衡处理
  41.          */
  42.         Entry<K,V> replacement = (p.left != null ? p.left : p.right);
  44.         if (replacement != null) {
  45.             // Link replacement to parent
  46.             //将待删除节点的子节点挂到待删除节点的父节点上。
  47.             replacement.parent = p.parent;
  48.             if (p.parent == null)
  49.                 root = replacement;
  50.             else if (p == p.parent.left)
  51.                 p.parent.left  = replacement;
  52.             else
  53.                 p.parent.right = replacement;
  55.             // Null out links so they are OK to use by fixAfterDeletion.
  56.             p.left = p.right = p.parent = null;
  58.             /**
  59.              * p如果是红色节点的话，那么其子节点replacement必然为红色的，并不影响红黑树的结构
  60.              * 但如果p为黑色节点的话，那么其父节点以及子节点都可能是红色的，那么很明显可能会存在红色相连的情况，因此需要进行自平衡的调整
  61.              */
  62.             if (p.color == BLACK)
  63.                 //进行删除后自平衡的调整
  64.                 fixAfterDeletion(replacement);
  65.         } else if (p.parent == null) { // return if we are the only node.
  66.             root = null;
  67.         } else { //  No children. Use self as phantom replacement and unlink.
  68.             /**
  69.              * 如果p节点为黑色，那么p节点删除后，就可能违背每个节点到其叶子节点路径上黑色节点数量一致的规则，因此需要进行自平衡的调整
  70.              */ 
  71.             if (p.color == BLACK)
  72.                 //进行删除后自平衡的调整
  73.                 fixAfterDeletion(p);
  75.             if (p.parent != null) {
  76.                 if (p == p.parent.left)
  77.                     p.parent.left = null;
  78.                 else if (p == p.parent.right)
  79.                     p.parent.right = null;
  80.                 p.parent = null;
  81.             }
  82.         }
  83.     }
  85.     //进行删除后自平衡的调整
  86.     private void fixAfterDeletion(Entry<K,V> x) {
  87.         /**
  88.          * 当节点x不是root节点且颜色为黑色时
  89.          */
  90.         while (x != root && colorOf(x) == BLACK) {
  91.             /**
  92.              *    分节点x是否为左右节点两种情况
  93.              */
  94.             if (x == leftOf(parentOf(x))) {
  95.                 Entry<K,V> sib = rightOf(parentOf(x));
  96.                 /**
  97.                  * 场景1：当x是左黑色节点，兄弟节点sib是红色节点
  98.                  * 兄弟节点由红转黑，父节点由黑转红，按父节点左旋，
  99.                  * 左旋后树的结构变化了，这时重新赋值sib，这个时候sib指向了x的兄弟节点
  100.                  */
  101.                 if (colorOf(sib) == RED) {
  102.                     setColor(sib, BLACK);
  103.                     setColor(parentOf(x), RED);
  104.                     rotateLeft(parentOf(x));
  105.                     sib = rightOf(parentOf(x));
  106.                 }
  107.                 /**
  108.                  * 场景2：节点x、x的兄弟节点sib、sib的左子节点和右子节点都为黑色时，需要将该节点sib由黑变红，同时将x指向当前x的父节点
  109.                  */
  110.                 if (colorOf(leftOf(sib))  == BLACK &&
  111.                     colorOf(rightOf(sib)) == BLACK) {
  112.                     setColor(sib, RED);
  113.                     x = parentOf(x);
  114.                 } else {
  115.                     /**
  116.                      * 场景3：节点x、x的兄弟节点sib、sib的右子节点都为黑色，sib的左子节点为红色时，
  117.                      * 需要将sib左子节点设置为黑色，sib节点设置为红色，同时按sib右旋，再将sib指向x的
  118.                      * 兄弟节点
  119.                      */
  120.                     if (colorOf(rightOf(sib)) == BLACK) {
  121.                         setColor(leftOf(sib), BLACK);
  122.                         setColor(sib, RED);
  123.                         rotateRight(sib);
  124.                         sib = rightOf(parentOf(x));
  125.                     }
  126.                     /**
  127.                      * 场景4：节点x、x的兄弟节点sib都为黑色，而sib的左右子节点都为红色或者右子节点为红色、左子节点为黑色，此时需要将sib节点的颜色设置成和x的父节点p相同的颜色，
  128.                      * 设置x的父节点为黑色，设置sib右子节点为黑色，左旋x的父节点p，然后将x赋值为root
  129.                      */
  130.                     setColor(sib, colorOf(parentOf(x)));
  131.                     setColor(parentOf(x), BLACK);
  132.                     setColor(rightOf(sib), BLACK);
  133.                     rotateLeft(parentOf(x));
  134.                     x = root;
  135.                 }
  136.             } else { // symmetric ，x是右节点的情况
  137.                 Entry<K,V> sib = leftOf(parentOf(x));
  139.                 if (colorOf(sib) == RED) {
  140.                     setColor(sib, BLACK);
  141.                     setColor(parentOf(x), RED);
  142.                     rotateRight(parentOf(x));
  143.                     sib = leftOf(parentOf(x));
  144.                 }
  146.                 if (colorOf(rightOf(sib)) == BLACK &&
  147.                     colorOf(leftOf(sib)) == BLACK) {
  148.                     setColor(sib, RED);
  149.                     x = parentOf(x);
  150.                 } else {
  151.                     if (colorOf(leftOf(sib)) == BLACK) {
  152.                         setColor(rightOf(sib), BLACK);
  153.                         setColor(sib, RED);
  154.                         rotateLeft(sib);
  155.                         sib = leftOf(parentOf(x));
  156.                     }
  157.                     setColor(sib, colorOf(parentOf(x)));
  158.                     setColor(parentOf(x), BLACK);
  159.                     setColor(leftOf(sib), BLACK);
  160.                     rotateRight(parentOf(x));
  161.                     x = root;
  162.                 }
  163.             }
  164.         }
  166.         setColor(x, BLACK);
  167.     }

5-1、TreeMap-源码分析-删除元素后自平衡-情况

  1. 1、删除元素后自平衡-情况：
  2.     1-1、当x是左黑色节点，兄弟节点sib是红色节点，需要兄弟节点由红转黑，父节点由黑转红，按父节点左旋，左旋后树的结构变化了，这时重新赋值sib，这个时候sib指向了x的兄弟节点。
  3.     1-2、节点x、x的兄弟节点sib、sib的左子节点和右子节点都为黑色时，需要将该节点sib由黑变红，同时将x指向当前x的父节点。
  4.     1-3、节点x、x的兄弟节点sib、sib的右子节点都为黑色，sib的左子节点为红色时，需要将sib左子节点设置为黑色，sib节点设置为红色，同时按sib右旋，再将sib指向x的兄弟节点。
  5.     1-4、节点x、x的兄弟节点sib都为黑色，而sib的左右子节点都为红色或者右子节点为红色、左子节点为黑色，此时需要将sib节点的颜色设置成和x的父节点p相同的颜色，设置x的父节点颜色为黑色，设置sib右孩子的颜色为黑色，左旋x的父节点p，然后将x赋值为root。

5-1-1、TreeMap-源码分析-删除元素后自平衡-情况1-示意图

容器(Map)-TreeMap-源码分析 - 图4

5-1-2、TreeMap-源码分析-删除元素后自平衡-情况2-示意图

容器(Map)-TreeMap-源码分析 - 图5

5-1-3、TreeMap-源码分析-删除元素后自平衡-情况3-示意图容器(Map)-TreeMap-源码分析 - 图6

5-1-4、TreeMap-源码分析-删除元素后自平衡-情况4-示意图

容器(Map)-TreeMap-源码分析 - 图7

6、TreeMap-源码分析-Entry类

  1. 1、静态内部类Entry<K,V>类实现类Map.Entry接口，节点属性：通过left属性可以建立左子树，通过right属性可以建立右子树，通过parent可以往上找到父节点。
  2. 2、源代码：
  3.     static final class Entry<K,V> implements Map.Entry<K,V> {
  4.         K key;                //节点的key值
  5.         V value;            //节点的value值
  6.         Entry<K,V> left;    //定义了节点的左节点
  7.         Entry<K,V> right;    //定义了节点的右节点
  8.         Entry<K,V> parent;    //定义了节点的父节点，可通过该节点可以反过来往上找到自己的父亲
  9.         boolean color = BLACK; //默认情况下为黑色节点，可调整
  11.         /**
  12.          * 构造器
  13.          */
  14.         Entry(K key, V value, Entry<K,V> parent) {
  15.             this.key = key;
  16.             this.value = value;
  17.             this.parent = parent;
  18.         }
  20.         /**
  21.          * 获取节点的key值
  22.          */
  23.         public K getKey() {
  24.             return key;
  25.         }
  27.         /**
  28.          * 获取节点的value值
  29.          */
  30.         public V getValue() {
  31.             return value;
  32.         }
  34.         /**
  35.          * 用新值替换当前值，并返回当前值(旧值)
  36.          */
  37.         public V setValue(V value) {
  38.             V oldValue = this.value;
  39.             this.value = value;
  40.             return oldValue;
  41.         }
  43.         public boolean equals(Object o) {
  44.             if (!(o instanceof Map.Entry))
  45.                 return false;
  46.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  48.             return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
  49.         }
  51.         public int hashCode() {
  52.             int keyHash = (key==null ? 0 : key.hashCode());
  53.             int valueHash = (value==null ? 0 : value.hashCode());
  54.             return keyHash ^ valueHash;
  55.         }
  57.         public String toString() {
  58.             return key + "=" + value;
  59.         }
  60.     }

6-1、Entry类-实现结构图


容器(Map)-TreeMap-源码分析 - 图8

7、TreeMap-源码分析-带SortedMap的构造函数

  1. 1、带SortedMap的构造函数，SortedMap会成为TreeMap的子集，SortedMap是一个有序的Map，我们通过buildFromSorted()来创建对应的Map。
  3. 2、源代码：
  4.     public TreeMap(SortedMap<K, ? extends V> m) {
  5.         comparator = m.comparator();
  6.         try {
  7.             buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
  8.         } catch (java.io.IOException cannotHappen) {
  9.         } catch (ClassNotFoundException cannotHappen) {
  10.         }
  11.     }
  13.     // 根据已经一个排好序的map创建一个TreeMap
  14.      // 将map中的元素逐个添加到TreeMap中，并返回map的中间元素作为根节点。
  15.     private void buildFromSorted(int size, Iterator<?> it,
  16.                                  java.io.ObjectInputStream str,
  17.                                  V defaultVal)
  18.         throws  java.io.IOException, ClassNotFoundException {
  19.         this.size = size;
  20.         root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
  21.                                it, str, defaultVal);
  22.     }
  24.     @SuppressWarnings("unchecked")
  25.     private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
  26.                                              int redLevel,
  27.                                              Iterator<?> it,
  28.                                              java.io.ObjectInputStream str,
  29.                                              V defaultVal)
  30.         throws  java.io.IOException, ClassNotFoundException {
  31.         /*
  32.          * Strategy: The root is the middlemost element. To get to it, we
  33.          * have to first recursively construct the entire left subtree,
  34.          * so as to grab all of its elements. We can then proceed with right
  35.          * subtree.
  36.          *
  37.          * The lo and hi arguments are the minimum and maximum
  38.          * indices to pull out of the iterator or stream for current subtree.
  39.          * They are not actually indexed, we just proceed sequentially,
  40.          * ensuring that items are extracted in corresponding order.
  41.          */
  43.         if (hi < lo) return null;
  44.         // 获取中间元素，右移运算，相当于/2
  45.         int mid = (lo + hi) >>> 1;
  47.         Entry<K,V> left  = null;
  48.         // 若lo小于mid，则递归调用获取(middle的)左节点
  49.         if (lo < mid)
  50.             left = buildFromSorted(level+1, lo, mid - 1, redLevel,
  51.                                    it, str, defaultVal);
  53.         // extract key and/or value from iterator or stream
  54.         // 获取middle节点对应的key和value
  55.         K key;
  56.         V value;
  57.         if (it != null) {
  58.             if (defaultVal==null) {
  59.                 Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
  60.                 key = (K)entry.getKey();
  61.                 value = (V)entry.getValue();
  62.             } else {
  63.                 key = (K)it.next();
  64.                 value = defaultVal;
  65.             }
  66.         } else { // use stream
  67.             key = (K) str.readObject();
  68.             value = (defaultVal != null ? defaultVal : (V) str.readObject());
  69.         }
  70.         // 创建middle节点
  71.         Entry<K,V> middle =  new Entry<>(key, value, null);
  73.         // color nodes in non-full bottommost level red
  74.         // 若当前节点的深度=红色节点的深度，则将节点着色为红色。
  75.         if (level == redLevel)
  76.             middle.color = RED;
  77.         // 设置middle为left的父亲，left为middle的左孩子
  78.         if (left != null) {
  79.             middle.left = left;
  80.             left.parent = middle;
  81.         }
  82.         // 递归调用获取(middle的)右孩子。
  83.         if (mid < hi) {
  84.             Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
  85.                                                it, str, defaultVal);
  86.             // 设置middle为left的父亲，left为middle的左孩子
  87.             middle.right = right;
  88.             right.parent = middle;
  89.         }
  91.         return middle;
  92.     }

8、TreeMap-源码分析-Entry相关函数

  1. 1、Entry相关函数：TreeMap的 firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry() 、
  3. 2、firstEntry()和getFirstEntry()的源代码：都是用于获取第一个节点
  4.     /**
  5.         防止用户修改返回的Entry。getFirstEntry()返回的Entry是可以被修改的，但是经过firstEntry()返回的Entry不能被修改，只可以读取Entry的key值和value值。
  6.     */
  7.     //firstEntry() 是对外接口,对firstEntry()返回的Entry对象只能进行getKey()、getValue()等读取操作。
  8.     public Map.Entry<K,V> firstEntry() {
  9.         return exportEntry(getFirstEntry());
  10.     }
  12.     //getFirstEntry()是内部接口,而对getFirstEntry()返回的对象除了可以进行读取操作之后，还可以通过setValue()修改值。
  13.     final Entry<K,V> getFirstEntry() {
  14.         Entry<K,V> p = root;
  15.         if (p != null)
  16.             while (p.left != null)
  17.                 p = p.left;
  18.         return p;
  19.     }
  21.     //.exportEntry(): 新建一个AbstractMap.SimpleImmutableEntry类型的对象，并返回。
  22.     static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
  23.         return (e == null) ? null :
  24.             new AbstractMap.SimpleImmutableEntry<>(e);
  25.     }

9、TreeMap-源码分析-其他相关函数

  1. 1、TreeMap实现的Cloneable接口，即实现了clone()方法。.clone()方法的作用很简单，就是克隆一个TreeMap对象并返回。
  3. 2、TreeMap实现java.io.Serializable，分别实现了串行读取、写入功能。
  4.     2-1、串行写入函数是writeObject()，它的作用是将TreeMap的“容量，所有的Entry”都写入到输出流中。
  5.     2-2、而串行读取函数是readObject()，它的作用是将TreeMap的“容量、所有的Entry”依次读出。
  6.     2-3、readObject() 和 writeObject() 正好是一对，通过它们，我能实现TreeMap的串行传输。
  8. 3、TreeMap实现的NavigableMap接口-API-简介：
  9.     3-1、descendingMap() 的作用是返回当前TreeMap的反向的TreeMap。所谓反向，就是排序顺序和原始的顺序相反。
  10.     3-2、NavigableSubMap，它是一个抽象集合类，为2个子类--"(升序)AscendingSubMap"和"(降序)DescendingSubMap"而服务。