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

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

# **TreeMap的原理** #

**一、     数据结构**

**源码定义如下  **

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

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

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

//比较器，因为TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
            private final Comparator<? super K> comparator;
            //TreeMap红-黑节点，为TreeMap的内部类
            private transient Entry<K,V> root = null;
            //容器大小
            private transient int size = 0;
            //TreeMap修改次数
            private transient int modCount = 0;
            //红黑树的节点颜色--红色
            private static final boolean RED = false;
            //红黑树的节点颜色--黑色
            private static final boolean BLACK = true;
           对于叶子节点Entry是TreeMap的内部类，它有几个重要的属性：
    
    //键
            K key;
            //值
            V value;
            //左孩子
            Entry<K,V> left = null;
            //右孩子
            Entry<K,V> right = null;
            //父亲
            Entry<K,V> parent;
            //颜色
            boolean color = BLACK;

**      二、存储**

**    先看源码**

public V put(K key, V value) {
        Entry<K,V> t = root;
        /**
         * 如果根节点都为null，还没建立起来红黑树，我们先new Entry并赋值给root把红黑树建立起来，这个时候红
         * 黑树中已经有一个节点了，同时修改操作+1。
         */
        if (t == null) {
            compare(key, key); 
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        /**
         * 如果节点不为null,定义一个cmp，这个变量用来进行二分查找时的比较；定义parent，是new Entry时必须
         * 要的参数
         */
        int cmp;
        Entry<K,V> parent;
        // cpr表示有无自己定义的排序规则，分两种情况遍历执行
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            /**
             * 从root节点开始遍历，通过二分查找逐步向下找
             * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法
             * cpr.compare(key, t.key)比较传入的key和根节点的key值，如果传入的key<root.key，那么
             * 继续在root的左子树中找，从root的左孩子节点（root.left）开始：如果传入的key>root.key,
             * 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;如果恰好key==root.key，
             * 那么直接根据root节点的value值即可。
             * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
             *
             * 需要注意的是：这里并没有对key是否为null进行判断，建议自己的实现Comparator时应该要考虑在内
             */
            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 {
            //从这里看出，当默认排序时，key值是不能为null的
            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);
        }
        /**
         * 能执行到这里，说明前面并没有找到相同的key,节点已经遍历到最后了，我们只需要new一个Entry放到
         * parent下面即可，但放到左子节点上还是右子节点上，就需要按照红黑树的规则来。
         */
        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;
    }

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

再重点看下 fixAfterInsertion方法的源码

private void fixAfterInsertion(Entry<K,V> x) {
        //新插入的节点为红色节点
        x.color = RED;
        //我们知道父节点为黑色时，并不需要进行树结构调整，只有当父节点为红色时，才需要调整
        while (x != null && x != root && x.parent.color == RED) {
            //如果父节点是左节点，对应上表中情况1和情况2
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                //如果叔父节点为红色，对应于“父节点和叔父节点都为红色”，此时通过变色即可实现平衡
                //此时父节点和叔父节点都设置为黑色，祖父节点设置为红色
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    //如果插入节点是黑色，插入的是右子节点，通过【左右节点旋转】（这里先进行父节点左旋）
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    //设置父节点和祖父节点颜色
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    //进行祖父节点右旋（这里【变色】和【旋转】并没有严格的先后顺序，达成目的就行）
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                //父节点是右节点的情况
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                //对应于“父节点和叔父节点都为红色”，此时通过变色即可实现平衡
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    //如果插入节点是黑色，插入的是左子节点，通过【右左节点旋转】（这里先进行父节点右旋）
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    //进行祖父节点左旋（这里【变色】和【旋转】并没有严格的先后顺序，达成目的就行）
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        //根节点必须为黑色
        root.color = BLACK;
    }

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3liNTQ2ODIyNjEy_size_16_color_FFFFFF_t_70][]

三、读取

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

public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }
    /**
     * 从root节点开始遍历，通过二分查找逐步向下找
     * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过k.compareTo(p.key)比较传入的key和
     * 根节点的key值；
     * 如果传入的key<root.key, 那么继续在root的左子树中找，从root的左孩子节点（root.left）开始；
     * 如果传入的key>root.key, 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;
     * 如果恰好key==root.key，那么直接根据root节点的value值即可。
     * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
     */
    //默认排序情况下的查找
    final Entry<K,V> getEntry(Object key) {
        
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }
    /**
     * 从root节点开始遍历，通过二分查找逐步向下找
     * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法
     * cpr.compare(key, t.key)比较传入的key和根节点的key值，如果传入的key<root.key，那么
     * 继续在root的左子树中找，从root的左孩子节点（root.left）开始：如果传入的key>root.key,
     * 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;如果恰好key==root.key，
     * 那么直接根据root节点的value值即可。
     * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
     */
    //自定义排序规则下的查找
    final Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
        K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

四、删除

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

public V remove(Object key) {
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;
    
        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
    }

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

1.  删除的是根节点，则直接将根节点置为null;
2.  待删除节点的左右子节点都为null，删除时将该节点置为null;
3.  待删除节点的左右子节点有一个有值，则用有值的节点替换该节点即可；
4.  待删除节点的左右子节点都不为null，则找前驱或者后继，将前驱或者后继的值复制到该节点中，然后删除前驱或者后继（前驱：**左子树中值最大的节点**，后继：**右子树中值最小的节点**）；
    
        private void deleteEntry(Entry<K,V> p) {
            modCount++;
            size--;
        	//当左右子节点都不为null时，通过successor(p)遍历红黑树找到前驱或者后继
            if (p.left != null && p.right != null) {
                Entry<K,V> s = successor(p);
                //将前驱或者后继的key和value复制到当前节点p中，然后删除节点s(通过将节点p引用指向s)
                p.key = s.key;
                p.value = s.value;
                p = s;
            } 
            Entry<K,V> replacement = (p.left != null ? p.left : p.right);
            /**
             * 至少有一个子节点不为null，直接用这个有值的节点替换掉当前节点，给replacement的parent属性赋值,给
             * parent节点的left属性和right属性赋值，同时要记住叶子节点必须为null,然后用fixAfterDeletion方法
             * 进行自平衡处理
             */
            if (replacement != null) {
                //将待删除节点的子节点挂到待删除节点的父节点上。
                replacement.parent = p.parent;
                if (p.parent == null)
                    root = replacement;
                else if (p == p.parent.left)
                    p.parent.left  = replacement;
                else
                    p.parent.right = replacement;
                p.left = p.right = p.parent = null;
                /**
                 * p如果是红色节点的话，那么其子节点replacement必然为红色的，并不影响红黑树的结构
                 * 但如果p为黑色节点的话，那么其父节点以及子节点都可能是红色的，那么很明显可能会存在红色相连的情
                 * 况，因此需要进行自平衡的调整
                 */
                if (p.color == BLACK)
                    fixAfterDeletion(replacement);
            } else if (p.parent == null) {//这种情况就不用多说了吧
                root = null;
            } else { 
                /**
                 * 如果p节点为黑色，那么p节点删除后，就可能违背每个节点到其叶子节点路径上黑色节点数量一致的规则，
                 * 因此需要进行自平衡的调整
                 */ 
                if (p.color == BLACK)
                    fixAfterDeletion(p);
                if (p.parent != null) {
                    if (p == p.parent.left)
                        p.parent.left = null;
                    else if (p == p.parent.right)
                        p.parent.right = null;
                    p.parent = null;
                }
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3liNTQ2ODIyNjEy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200602194228347.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3liNTQ2ODIyNjEy,size_16,color_FFFFFF,t_70