java集合的底层原理（Map的底层原理（TreeMap） 二）

一时失言乱红尘 2023-02-14 07:57 123阅读 0赞

TreeMap的原理

一、 数据结构

源码定义如下 

  1. public class TreeMap<K,V>
  2.     extends AbstractMap<K,V>
  3.     implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合， NavigableMap则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法 。

TreeMap中同时也包含了如下几个重要的属性：

  1. //比较器，因为TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
  2.         private final Comparator<? super K> comparator;
  3.         //TreeMap红-黑节点，为TreeMap的内部类
  4.         private transient Entry<K,V> root = null;
  5.         //容器大小
  6.         private transient int size = 0;
  7.         //TreeMap修改次数
  8.         private transient int modCount = 0;
  9.         //红黑树的节点颜色--红色
  10.         private static final boolean RED = false;
  11.         //红黑树的节点颜色--黑色
  12.         private static final boolean BLACK = true;
  13.        对于叶子节点Entry是TreeMap的内部类，它有几个重要的属性：
  15. //键
  16.         K key;
  17.         //值
  18.         V value;
  19.         //左孩子
  20.         Entry<K,V> left = null;
  21.         //右孩子
  22.         Entry<K,V> right = null;
  23.         //父亲
  24.         Entry<K,V> parent;
  25.         //颜色
  26.         boolean color = BLACK;

二、存储

先看源码

  1. public V put(K key, V value) {
  2.     Entry<K,V> t = root;
  3.     /**
  4.      * 如果根节点都为null，还没建立起来红黑树，我们先new Entry并赋值给root把红黑树建立起来，这个时候红
  5.      * 黑树中已经有一个节点了，同时修改操作+1。
  6.      */
  7.     if (t == null) {
  8.         compare(key, key); 
  9.         root = new Entry<>(key, value, null);
  10.         size = 1;
  11.         modCount++;
  12.         return null;
  13.     }
  14.     /**
  15.      * 如果节点不为null,定义一个cmp，这个变量用来进行二分查找时的比较；定义parent，是new Entry时必须
  16.      * 要的参数
  17.      */
  18.     int cmp;
  19.     Entry<K,V> parent;
  20.     // cpr表示有无自己定义的排序规则，分两种情况遍历执行
  21.     Comparator<? super K> cpr = comparator;
  22.     if (cpr != null) {
  23.         /**
  24.          * 从root节点开始遍历，通过二分查找逐步向下找
  25.          * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法
  26.          * cpr.compare(key, t.key)比较传入的key和根节点的key值，如果传入的key<root.key，那么
  27.          * 继续在root的左子树中找，从root的左孩子节点（root.left）开始：如果传入的key>root.key,
  28.          * 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;如果恰好key==root.key，
  29.          * 那么直接根据root节点的value值即可。
  30.          * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
  31.          *
  32.          * 需要注意的是：这里并没有对key是否为null进行判断，建议自己的实现Comparator时应该要考虑在内
  33.          */
  34.         do {
  35.             parent = t;
  36.             cmp = cpr.compare(key, t.key);
  37.             if (cmp < 0)
  38.                 t = t.left;
  39.             else if (cmp > 0)
  40.                 t = t.right;
  41.             else
  42.                 return t.setValue(value);
  43.         } while (t != null);
  44.     }
  45.     else {
  46.         //从这里看出，当默认排序时，key值是不能为null的
  47.         if (key == null)
  48.             throw new NullPointerException();
  49.         @SuppressWarnings("unchecked")
  50.         Comparable<? super K> k = (Comparable<? super K>) key;
  51.         //这里的实现逻辑和上面一样，都是通过二分查找，就不再多说了
  52.         do {
  53.             parent = t;
  54.             cmp = k.compareTo(t.key);
  55.             if (cmp < 0)
  56.                 t = t.left;
  57.             else if (cmp > 0)
  58.                 t = t.right;
  59.             else
  60.                 return t.setValue(value);
  61.         } while (t != null);
  62.     }
  63.     /**
  64.      * 能执行到这里，说明前面并没有找到相同的key,节点已经遍历到最后了，我们只需要new一个Entry放到
  65.      * parent下面即可，但放到左子节点上还是右子节点上，就需要按照红黑树的规则来。
  66.      */
  67.     Entry<K,V> e = new Entry<>(key, value, parent);
  68.     if (cmp < 0)
  69.         parent.left = e;
  70.     else
  71.         parent.right = e;
  72.     /**
  73.      * 节点加进去了，并不算完，我们在前面红黑树原理章节提到过，一般情况下加入节点都会对红黑树的结构造成
  74.      * 破坏，我们需要通过一些操作来进行自动平衡处置，如【变色】【左旋】【右旋】
  75.      */
  76.     fixAfterInsertion(e);
  77.     size++;
  78.     modCount++;
  79.     return null;
  80. }

put方法源码中通过fixAfterInsertion(e)方法来进行自平衡处理

再重点看下 fixAfterInsertion方法的源码

  1. private void fixAfterInsertion(Entry<K,V> x) {
  2.     //新插入的节点为红色节点
  3.     x.color = RED;
  4.     //我们知道父节点为黑色时，并不需要进行树结构调整，只有当父节点为红色时，才需要调整
  5.     while (x != null && x != root && x.parent.color == RED) {
  6.         //如果父节点是左节点，对应上表中情况1和情况2
  7.         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
  8.             Entry<K,V> y = rightOf(parentOf(parentOf(x)));
  9.             //如果叔父节点为红色，对应于“父节点和叔父节点都为红色”，此时通过变色即可实现平衡
  10.             //此时父节点和叔父节点都设置为黑色，祖父节点设置为红色
  11.             if (colorOf(y) == RED) {
  12.                 setColor(parentOf(x), BLACK);
  13.                 setColor(y, BLACK);
  14.                 setColor(parentOf(parentOf(x)), RED);
  15.                 x = parentOf(parentOf(x));
  16.             } else {
  17.                 //如果插入节点是黑色，插入的是右子节点，通过【左右节点旋转】（这里先进行父节点左旋）
  18.                 if (x == rightOf(parentOf(x))) {
  19.                     x = parentOf(x);
  20.                     rotateLeft(x);
  21.                 }
  22.                 //设置父节点和祖父节点颜色
  23.                 setColor(parentOf(x), BLACK);
  24.                 setColor(parentOf(parentOf(x)), RED);
  25.                 //进行祖父节点右旋（这里【变色】和【旋转】并没有严格的先后顺序，达成目的就行）
  26.                 rotateRight(parentOf(parentOf(x)));
  27.             }
  28.         } else {
  29.             //父节点是右节点的情况
  30.             Entry<K,V> y = leftOf(parentOf(parentOf(x)));
  31.             //对应于“父节点和叔父节点都为红色”，此时通过变色即可实现平衡
  32.             if (colorOf(y) == RED) {
  33.                 setColor(parentOf(x), BLACK);
  34.                 setColor(y, BLACK);
  35.                 setColor(parentOf(parentOf(x)), RED);
  36.                 x = parentOf(parentOf(x));
  37.             } else {
  38.                 //如果插入节点是黑色，插入的是左子节点，通过【右左节点旋转】（这里先进行父节点右旋）
  39.                 if (x == leftOf(parentOf(x))) {
  40.                     x = parentOf(x);
  41.                     rotateRight(x);
  42.                 }
  43.                 setColor(parentOf(x), BLACK);
  44.                 setColor(parentOf(parentOf(x)), RED);
  45.                 //进行祖父节点左旋（这里【变色】和【旋转】并没有严格的先后顺序，达成目的就行）
  46.                 rotateLeft(parentOf(parentOf(x)));
  47.             }
  48.         }
  49.     }
  50.     //根节点必须为黑色
  51.     root.color = BLACK;
  52. }

光看文字有点不好理解，请结合下图，会看得更清晰

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3liNTQ2ODIyNjEy_size_16_color_FFFFFF_t_70

三、读取

get方法是通过二分查找的思想，我们看一下源码

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

四、删除

remove方法可以分为两个步骤，先是找到这个节点，直接调用了上面介绍的getEntry(Object key)，这个步骤我们就不说了，直接说第二个步骤，找到后的删除操作。

  1. public V remove(Object key) {
  2.     Entry<K,V> p = getEntry(key);
  3.     if (p == null)
  4.         return null;
  6.     V oldValue = p.value;
  7.     deleteEntry(p);
  8.     return oldValue;
  9. }

通过deleteEntry(p)进行删除操作，删除操作的原理我们在前面已经讲过

  1. 删除的是根节点，则直接将根节点置为null;
  2. 待删除节点的左右子节点都为null，删除时将该节点置为null;
  3. 待删除节点的左右子节点有一个有值，则用有值的节点替换该节点即可；

  4. 待删除节点的左右子节点都不为null，则找前驱或者后继，将前驱或者后继的值复制到该节点中，然后删除前驱或者后继（前驱：左子树中值最大的节点，后继：右子树中值最小的节点）；

    1. private void deleteEntry(Entry<K,V> p) {
    2.     modCount++;
    3.     size--;
    4.     //当左右子节点都不为null时，通过successor(p)遍历红黑树找到前驱或者后继
    5.     if (p.left != null && p.right != null) {
    6.         Entry<K,V> s = successor(p);
    7.         //将前驱或者后继的key和value复制到当前节点p中，然后删除节点s(通过将节点p引用指向s)
    8.         p.key = s.key;
    9.         p.value = s.value;
    10.         p = s;
    11.     } 
    12.     Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    13.     /**
    14.      * 至少有一个子节点不为null，直接用这个有值的节点替换掉当前节点，给replacement的parent属性赋值,给
    15.      * parent节点的left属性和right属性赋值，同时要记住叶子节点必须为null,然后用fixAfterDeletion方法
    16.      * 进行自平衡处理
    17.      */
    18.     if (replacement != null) {
    19.         //将待删除节点的子节点挂到待删除节点的父节点上。
    20.         replacement.parent = p.parent;
    21.         if (p.parent == null)
    22.             root = replacement;
    23.         else if (p == p.parent.left)
    24.             p.parent.left  = replacement;
    25.         else
    26.             p.parent.right = replacement;
    27.         p.left = p.right = p.parent = null;
    28.         /**
    29.          * p如果是红色节点的话，那么其子节点replacement必然为红色的，并不影响红黑树的结构
    30.          * 但如果p为黑色节点的话，那么其父节点以及子节点都可能是红色的，那么很明显可能会存在红色相连的情
    31.          * 况，因此需要进行自平衡的调整
    32.          */
    33.         if (p.color == BLACK)
    34.             fixAfterDeletion(replacement);
    35.     } else if (p.parent == null) {//这种情况就不用多说了吧
    36.         root = null;
    37.     } else { 
    38.         /**
    39.          * 如果p节点为黑色，那么p节点删除后，就可能违背每个节点到其叶子节点路径上黑色节点数量一致的规则，
    40.          * 因此需要进行自平衡的调整
    41.          */ 
    42.         if (p.color == BLACK)
    43.             fixAfterDeletion(p);
    44.         if (p.parent != null) {
    45.             if (p == p.parent.left)
    46.                 p.parent.left = null;
    47.             else if (p == p.parent.right)
    48.                 p.parent.right = null;
    49.             p.parent = null;
    50.         }
    51.     }
    52. }

发表评论

表情：
评论列表 （有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

    相关 TreeMap底层原理？

    1.TreeMap实现了SortedMap接口，保证了有序性。默认的排序是根据key值进行升序排序，也可以重写comparator方法来根据value进行排序具体取决于使用的构

    叁歲伎倆叁歲伎倆/ 0 赞/ 63 阅读