程序员Java

Java HashMap 简介和源代码分析

2023-02-01  本文已影响0人  AlienPaul

HashMap特点

HashMap是Java中非常高效的key-value对数据存储结构。

它有如下特点:

HashMap的内部结构

HashMap的最外层数据结构为数组。这个数组的size(叫做HashMap的capacity)为初始大小或者是人工指定。这个数组叫做node table,数组的每一个元素可以视为一个篮子,称之为bin。数组的长度必须是2的n次方。放入每个格子的元素是key value对。决定元素放入哪个bin的逻辑为计算key的hashCode(暂时理解为采用hashCode计算,后面代码分析中会发现为了更好的散布将hashCode再次加工了),然后和数组的size - 1按位与(size是2的n次方,减去1在二进制上相当于一个全是1的数,1的位数正好是size,这样可以将任意hashCode尽可能均匀的映射在node table有限的空间中),得到的结果就是bin在数组中的index。

如果元素的key的hashCode相同怎么处理?HashMap引入了二级数据结构:单向链表。hashCode相同的key对应的key value,组成单向链表,存放于同一个bin中。这样就解决了hashCode冲突的问题。

那么问题又来了,如果hashCode冲突的太多怎么处理?这时候链表会非常长,查找或者删除的时候需要遍历很长的链表,效率较低。如果链表过长(大于TREEIFY_THRESHOLD),这时候HashMap将链表自动转换为红黑树结构。红黑树结构对于大量数据的查找非常的高效。

似乎所有的疑问都解决了。但是还有一个:为什么还用单向链表,只要hashCode冲突全用红黑树不就行了?明显是忽略的红黑树的存储代价。HashMap中的红黑树存储占用空间是链表节点的2倍。同一个bin中元素较少的情况,使用红黑树存储并不能比单向链表有更突出的性能。为了平衡性能和空间消耗,HashMap在链表元素数大于TREEIFY_THRESHOLD并且HashMap的capacity大于MIN_TREEIFY_CAPACITY的时候转换为红黑树,在红黑树元素数量小于UNTREEIFY_THRESHOLD的时候退化为单向链表。

Load factor负载因子

通过上面内部结构的讲解可以看到,HashMap的node table存储的越满,hashCode冲突的情况就可能越多,链表和红黑树再优秀,也不可能和按照hashCode直接找bin 的速度相提并论。所以说要有一个机制,node table满到一定程度(多“满”使用HashMapsize / capacity衡量),HashMap需要自动扩容。这个满到什么程度用术语表示即load factor负载因子。默认的负载因子为0.75,平衡了查找元素耗时和存储空间消耗。无特殊需求建议不要更改。

Treeify树型化

HashMap中有个很重要的树形化概念。前面HashMap的内部结构已分析过红黑树,这里仅简要复述。

通常来说HashMap的bin不会存放太多数量的hashCode碰撞的元素。采用链表形式存放已经可以满足性能要求。
但是在一个bin下的节点过多这种情况,链表的查找性能会明显下降。需要将bin的数据结构变换为红黑树。可能有人会问,既然红黑树性能这么好为什么不单纯使用红黑树?问题在于tree node大小是普通链表node的2倍,为了平衡空间和时间的消耗,HashMap规定了TREEIFY_THRESHOLD,值为8。意思是只有一个bin中的节点数量超过8个的时候才可能转换为红黑树。除此之外,如果HashMapresize的时候发现bin的节点数量小于UNTREEIFY_THRESHOLD(值为6),数据结构会退化为普通链表。

性能分析

尽管HashMap为了高性能而设计,但是不恰当的使用会使性能大打折扣。

HashMap性能的影响因素如下:

初始容量和resize

HashMap的初始capacity是16。在使用过程中随着元素的扩容逐渐增大,16 -> 32 -> 64 -> ...。每一次扩充都伴随有resize。resize过程伴随着所有元素重新分配bin,然后移动元素。显然resize是非常耗时的操作。一种优化方式是元素数量可以提前预估的场景,在创建HashMap的时候明确指定初始容量。这样可以避免很多次resize操作。

Load factor

前面讲过,load factor是时间和空间消耗的平衡。load factor设置过低,HashMap会频繁扩容,会浪费空间。load factor设置过高,HashMap延迟扩容,更容易造成hashCode冲突(node table存在更多的链表和红黑树),影响性能。

Key的hashCode散布情况

理想情况均匀散布的key的hashCode能够最小化hashCode冲突造成的性能问题。如果key的hashCode散布不均匀,会造成node table大量空闲但是某些bin存在很长的链表/红黑树这种情况。相当于HashMap最外层数据结构几乎没有发挥作用,严重影响HashMap性能。这一点一定要格外注意。

到这里为止HashMap的文字介绍基本完成,接下来开始HashMap的源代码分析。

HashMap的主要成员变量

// 默认初始化容量大小,默认值为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 支持的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子
// 如果node table入口数量超过了负载因子和当前容量的乘积,node table会扩容并重新计算各个入口的hash,放入对应的桶中
// 相当于重建内部数据结构
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 若一个bin的元素数量超过8,则链表结构才有可能变为树结构
static final int TREEIFY_THRESHOLD = 8;

// 若一个bin的元素数量少于6,则树结构会退化为链表结构
static final int UNTREEIFY_THRESHOLD = 6;

// 只有hashMap容量大小到达这个值的时候,bin链表才有可能树形化
static final int MIN_TREEIFY_CAPACITY = 64;

// 就是前面说的node table
transient Node<K,V>[] table;

// 目前保存的key value对数量
transient int size;

// 修改次数,用于检测并发修改情况,后面会专门分析
transient int modCount;

// 每次HashMap元素增加都去计算该不该扩容效率太低了
// 不如扩容的时候计算好,下次达到什么size的时候再次扩容,这个size就是threshold
// 即下一次该触发resize的阈值
int threshold;

重要操作源代码

插入数据

插入数据对应的put方法。代码如下:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

首先在hash方法中计算key的hash,如果key为null返回0。否则,取key对象的hashCode的高16位和hashCode的低16位异或作为hashCode的低16位,高16位保持不变。
这种算法将hashCode高16位的变化散布到低16位。因为后面计算key对应bin的时候,需要将hash值和HashMap的capacity(即Node<K,V>[] table的大小,不是HashMap实际存储对象数量的size) - 1做按位与运算(意思是只保留hash值的低capacity位)。所以说如果一组key的hashCode正好只在高位发生变化,这组key的hash值进行按位与之后是一定会发生冲突的。因此hash方法将hashCode的高位和低位变化通过异或运算,散布在一起,进一步减少hash碰撞的概率。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

然后调用putVal方法。将数据存入。

// onlyIfAbsent: 如果为true,key对应的值存在的时候不替换
// evict: true的话表示table在creation mode,在afterNodeInsertion回调中使用
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // n为table的length
    // 如果node table为null或者length为0,返回初始化默认容量(16)
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 找出元素对应的bin
    // 算法为取hash值的后capacity位作为tab的下标,找到对应的node
    // 如果node不存在,将值放入新的node中
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 这里node是链表Node
        // bin中只有一个数据的话,也用的是链表节点
        tab[i] = newNode(hash, key, value, null);
    else {
        // 到这里说明存在key的hash碰撞
        // 但不意味着key相同的元素已找到
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 节点内容的hash值相同,key为同一个object或者key语义等价
            // 说明找到key相同的节点,接下来走替换值的流程
            e = p;
        else if (p instanceof TreeNode)
            // 如果p是TreeNode,说明bin数据结构已经树形化,走添加树节点逻辑,后面分析
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 到这里是添加链表节点的过程
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 遍历链表,找到最后一个节点
                    // 在这个节点之后追加新节点
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 如果链表节点数量到达树形化阈值,切换为红黑树结构,后面分析
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 节点内容的hash值相同,key为同一个object或者key等价
                    // 说明key已存在,接下来走替换值的流程
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            // 这里是key相同的节点已找到,替换值的逻辑
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                // 如果允许替换值,或者旧值为null
                // 替换为新值
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 自增修改计数
    // 用来检测遍历的同时是否修改了hashMap
    ++modCount;
    if (++size > threshold)
        // size自增后如果大于threshold(Node table数组大小,2的n次方)
        // 需要扩容2倍
        resize();
    afterNodeInsertion(evict);
    return null;
}

删除数据

删除数据对应的是remove方法。代码如下:

public V remove(Object key) {
    Node<K,V> e;
    // 返回remove掉节点的值
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

hash计算逻辑和前面相同。这里只分析removeNode方法,如下:

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        // 如果找到了hash对应的node,key存在于HashMap
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 如果hash相同,并且key是同一个object或者key语义相等(equals)
            // 说明这个bin中只有一个node,没有链表或者树节点
            // 或者该node恰好是bin中的第一个节点
            // 记录下这个node,走后面删除节点逻辑
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                // 如果这个bin中是树形结构,调用getTreeNode找到这个node
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        // 遍历链表,查找node
                        node = e;
                        break;
                    }
                    // 当找到链表中符合条件的node之后,p为该node的上一个node
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 判断是否需要值相同的时候才移除node
            if (node instanceof TreeNode)
                // 如果是树节点,调用removeTreeNode
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // 如果是bin中第一个节点(链表),tab[index]指向该节点下一个
                // 如果bin中只有这一个节点也没关系,node.next为null,相当于将tab[index]设置为null
                tab[index] = node.next;
            else
                // 如果node不是bin中链表第一个节点
                // p的下一个节点指向node的下一个节点,跳过node,相当于把node删除
                p.next = node.next;
            // 自增修改计数
            ++modCount;
            // 大小减一
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    // key在hashMap中不存在,什么都没有remove,返回null
    return null;
}

获取key对应的value

对应的为get方法。代码如下:

public V get(Object key) {
    Node<K,V> e;
    // 调用了getNode方法
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

接着分析getNode方法。

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 找到bin中的第一个节点
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            // 如果hash和key都相同,返回这个节点
            return first;
        if ((e = first.next) != null) {
            // 如果第一个节点的next节点不为空
            // 说明这个bin中不止一个节点,需要分类为链表和树两种情况处理
            if (first instanceof TreeNode)
                // 如果是树节点,调用getTreeNode方法
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 如果是链表结构,遍历节点,直到找到hash和key都相同的节点返回
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 没有找到符合要求的节点,返回null
    return null;
}

扩容

扩容对应resize方法。它不仅用于扩容,还可以在特定情况下恢复HashMap初始容量。

final Node<K,V>[] resize() {
    // 保存resize之前的node table为oldTable
    Node<K,V>[] oldTab = table;
    // 获取resize之前的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 获取resize之前的threshold
    int oldThr = threshold;
    // 定义新容量,新threshold
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
        // 超过最大容量,不扩容返回
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // resize之前容量大于初始容量,并且容量扩大2倍之后小于最大容量
            // 符合这个条件可进行扩容操作
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 新容量赋值为oldThreshold,为初始容量
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // oldCap和oldThr都为0
        // 初始化容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // 计算thredshold,乘以loadFActor,如果超过MAXIMUM_CAPACITY则newThr为Integer.MAX_VALUE
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 更新threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 创建新的node table,容量为新的容量
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 逐个遍历旧node table
            if ((e = oldTab[j]) != null) {
                // 如果bin中存在node
                // 清空旧table中bin对应的node
                oldTab[j] = null;
                if (e.next == null)
                    // e的next为null说明这个bin中只有一个节点
                    // 重新计算在新table中的位置后存入新table
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 如果节点是treeNode类型
                    // 需要将红黑树分裂,分裂的方法见后面分析
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 到这里,说明bin下存放着链表
                    // 需要将链表分裂
                    // 容量扩大2倍之后,由于hash值计算bin位置的时候需要和(容量-1)做按位与运算
                    // 因此他们在新table中的位置可能会改变
                    // 这里将链表按照在新table中的bin位置是否改变分为拆分为两个
                    // low为不需要移动的node,high为需要移动的node
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        // 遍历链表
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            // hash值没有变化,不需要移动到新的bin
                            // 这里组装low链表,loHead为链表开头,loTail为链表末尾
                            // 如果loTail为null说明为low链表开头,赋值loHead
                            if (loTail == null)
                                loHead = e;
                            else
                                // 否则将节点串到loTail之后
                                loTail.next = e;
                            // loTail指向当前节点,准备下一次循环操作
                            loTail = e;
                        }
                        else {
                            // 组装high链表
                            // hiHead为链表开头,loTail为链表末尾
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        // 这里说明low链表存在
                        loTail.next = null;
                        // low链表放入原先的bin中
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        // 这里说明high链表存在
                        hiTail.next = null;
                        // high链表的bin位置为原来的bin位置+旧的容量值
                        // 将high链表存入新的bin中
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 返回处理过的node table
    return newTab;
}

需要注意的是,扩容遇到链表或者红黑树的时候,需要将它分裂。

链表分裂的原理描述如下:

链表中所有节点的hash值扩容前后是不会改变的。但是hash值和新的容量-1按位与运算之后(确定元素在扩容后的HashMap中的bin位置),可能会出现两种结果(因为新capacity是老capacity的两倍,二进制多了一位):

TreeNodesplit和链表分裂基本相同,区别在于分裂后需要检查红黑树的元素数量,如果数量过少,需要退化为链表结构。

这里将TreeNodesplit方法提前讲解。它的代码如下所示:

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    // 和前面分拆链表的逻辑基本相同
    // 多出来了low和high链表长度的统计,用于决定是否将分拆后的链表转换为树形结构
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            // 如果树中的元素小于阈值,退化为链表结构
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                // 前面构建的low树是个倾斜的树,这里需要重新树形化
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

遍历和并发修改限制

HashMap可以遍历EntrySetkeySet或者是values遍历时执行的逻辑分别是EntrySetkeySetValuesforEach方法。这三个方法的内容基本上是完全一样的,除了消费遍历内容的consumer不一样。我们以EntrySetforEach方法为例分析。

public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
        // 遍历node table
        // 遍历前暂存modCount
        int mc = modCount;
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next)
                // 如果一个bin中存储了链表或者是树结构,逐个遍历他们
                action.accept(e);
        }
        // 遍历完成后检查modCount是否发生变化
        // 如果变化抛出异常
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

需要注意的是modCount这个变量。HashMap只支持单线程操作,因此每次遍历的前后都会检查HashMap是否发生变化(putremove的时候会修改modCount)。如果发生变化,抛出ConcurrentModificationException。可以阻止一个线程使用iterator遍历的同时,另一个线程使用HashMapputremove方法操作HashMap这种场景。

当然。上面的分析不代表HashMap不支持遍历的时候移除元素。我们可以在使用iterator遍历的时候,在同一个线程使用iterator的remove方法移除元素。该remove方法的代码位于HashIteratorremove方法。如下所示:

public final void remove() {
    Node<K,V> p = current;
    if (p == null)
        throw new IllegalStateException();
    // remove前发生并发修改,报错
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    current = null;
    K key = p.key;
    // remove节点
    removeNode(hash(key), key, null, false, false);
    // 然后重设expectedModCount
    // 这是为什么iterator可以遍历的同时remove元素的原因
    expectedModCount = modCount;
}

红黑树

到这里我们开始分析HashMap中最难理解的部分:红黑树的实现。

红黑树相对于其他树的好处是不需要维护各个节点的高度(距离根节点的距离)信息就可以保证基本平衡(比平衡二叉树宽松),处理效率相对较高。

HashMap中的红黑树和传统数据结构算法中的红黑树基本相同。熟悉数据结构的读者可以略过此节。不熟悉的读者可参考https://www.jianshu.com/p/e136ec79235c/

本节侧重于代码层面分析红黑树操作。

树节点定义

TreeNode继承自LinkedHashMap.EntryLinkedHashMap.Entry又继承自HashMap.Node。所以说TreeNode除了树节点自身的特性之外,还可以当作单向链表或者双向链表的节点使用。

// 父节点
TreeNode<K,V> parent;  // red-black tree links
// 左节点
TreeNode<K,V> left;
// 右节点
TreeNode<K,V> right;
// 前一个节点。即便是树结构,仍然保留着链表时候的顺序,通过prev和next指针维护顺序
TreeNode<K,V> prev;    // needed to unlink next upon deletion
// 表示是否是红黑树的红节点
boolean red;

TreeNode中的树节点相关概念:

TreeNode中的双向链表节点相关概念:

TreeNode中的单向链表节点相关概念:

重要方法

重要工具方法

在分析增删和查找节点之前,我们先分析几个比较重要的工具方法。

root方法返回包含当前节点的树的根节点。

final TreeNode<K,V> root() {
    // 一直向上查找当前节点的父节点
    // 直到父节点为null为止
    // 这个节点就是当前树的root节点
    for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}

moveRootToFront方法将指定的root节点作为bin的第一个节点存入node table中。

static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        // 计算root节点应位于哪个bin下
        int index = (n - 1) & root.hash;
        // 取出来这个bin位置的第一个节点
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        if (root != first) {
            // 如果这个节点不是root
            Node<K,V> rn;
            // 将root节点作为这个bin的第一个节点
            tab[index] = root;
            // rp是root的前一个节点
            TreeNode<K,V> rp = root.prev;
            if ((rn = root.next) != null)
                // 如果root下一个节点存在
                // rn的前一个设为rp
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                // 如果rp存在
                // rp的下一个设置为rn
                rp.next = rn;
            // 前面两个if相当于rn和rp直接关联,跳过root节点本身
            if (first != null)
                // 如果first存在,first前一个设置为root
                first.prev = root;
            // 关联root下一个节点为first
            root.next = first;
            root.prev = null;
        }
        // 检查红黑树的合法性
        assert checkInvariants(root);
    }
}

moveRootToFront没有改变树结构,仅仅是将TreeNode视为双向链表调整了顺序。将指定的root节点作为第一个节点存入bin。

checkInvariants方法检查红黑树的合法性。逻辑如下:

static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
    TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
        tb = t.prev, tn = (TreeNode<K,V>)t.next;
    if (tb != null && tb.next != t)
        // 前一个节点存在,且前一个节点的下一个节点不是本节点
        // 说明树有问题,返回false
        return false;
    if (tn != null && tn.prev != t)
        // 下一个节点存在,且下一个节点的前一个节点不是本节点
        return false;
    if (tp != null && t != tp.left && t != tp.right)
        // 父节点存在,当前节点既不是父节点的左节点也不是右节点
        return false;
    if (tl != null && (tl.parent != t || tl.hash > t.hash))
        // 左节点存在,左节点的父节点不是当前节点或者是左节点的hash值大于当前节点的hash值(顺序不对)
        return false;
    if (tr != null && (tr.parent != t || tr.hash < t.hash))
        // 右节点同理
        return false;
    if (t.red && tl != null && tl.red && tr != null && tr.red)
        // 当前节点是红节点,且左右节点都为红色
        return false;
    if (tl != null && !checkInvariants(tl))
        // 左节点需要递归检查
        return false;
    if (tr != null && !checkInvariants(tr))
        // 右节点同理
        return false;
    return true;
}

链表转换为树结构

我们从HashMap把bin中的链表转换为树结构的方法treeifyBin开始分析。代码如下:

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 如果不符合树形化条件,调用resize方法
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 找到bin中第一个节点
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 遍历整个链表
            // 替换e为TreeNode
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                // 设置头节点
                hd = p;
            else {
                // 将链表上所有节点转换为TreeNode,使用prev和next指针,保持原来的顺序串起来
                // 这里只是将节点类型转换而已,真正的树结构还没有形成
                // 最后的treeify方法才生成树结构
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            // 生成树形结构
            hd.treeify(tab);
    }
}

treeify树形化方法,生成树结构。

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        // x为当前节点,next为下一个节点
        next = (TreeNode<K,V>)x.next;
        // 左右都设为null
        x.left = x.right = null;
        if (root == null) {
            // 如果没有root
            // 设置当前节点为root
            x.parent = null;
            // 红黑树root节点为黑节点
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) {
                // 这个for的逻辑为寻找x节点插入树的位置,将x节点插入
                // 从root节点开始,寻找插入节点的位置
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    // p的hash大于x的hash
                    dir = -1;
                else if (ph < h)
                    // p的hash小于x的hash
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    // 如果hash相同,compareTo方法比较也相同,两者class名称仍相同
                    // 调用tieBreakOrder方法比较,使用System.identityHashCode比较
                    dir = tieBreakOrder(k, pk);
                // xp意思是x的父节点
                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // 根据dir,找到p的左节点或右节点,如果为null的话
                    // x的父节点设置为p
                    x.parent = xp;
                    // 根据dir,设置xp的左节点或右节点为x
                    // 将x节点插入树中
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 插入x节点后红黑树可能会被破坏,需要重新平衡
                    // 平衡后root节点可能会有变化
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // 最后,将root节点作为bin的第一个节点,存入node table
    moveRootToFront(tab, root);
}

tieBreakOrder方法从className和内存地址产生的hashCode来比较两个对象。归根结底也要比较出两个对象的大小。

static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        // System.identityHashCode忽略对象是否重写了hashCode方法,永远返回根据对象物理内存地址产生的hash值
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

查找节点

从当前节点的子树中查找符合条件的子节点。

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            // h比ph小,查找左子树
            p = pl;
        else if (ph < h)
            // 否则,查找右子树
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // 如果hash相同,key是同一个object或者是key语义上相同,p就是要找的节点,返回它
            return p;
        else if (pl == null)
            // 如果hash相同,key为null或语义不同
            // 向下遍历存在的子树
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            // 如果左右子树都存在,使用key类型自定义的比较方法比较结果
            // 确定是查找左子树还是右子树
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            // 如果key的自定义比较结果相同,或者kc是null(没实现Comparable接口)
            // 递归查找右子树
            return q;
        else
            // 上面没找到结果,下一次遍历处理左子树
            p = pl;
    } while (p != null);
    // 没有找到返回null
    return null;
}

插入数据

putTreeVal方法,将键值加入到树结构中。

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    // 获取根节点,通常来说this为bin的第一个节点,也是树的根节点
    TreeNode<K,V> root = (parent != null) ? root() : this;
    for (TreeNode<K,V> p = root;;) {
        // 从p(root)节点开始循环
        // ph是p节点的hash
        // pk是p节点的key
        int dir, ph; K pk;
        if ((ph = p.hash) > h)
            // 如果p的hash比要插入节点的hash大
            // 说明需要找p左节点,dir(方向)设置为-1
            dir = -1;
        else if (ph < h)
            // 否则找p的右节点
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // hash值相同的情况下
            // 如果pk和k是同一个object或者语义相等
            // 这个节点已找到,返回它
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            // hash值相同,k为null或者语义不相等
            // k的class没有实现Comparable接口
            // 或者k的class实现了Comparable接口,使用k自定义的比较逻辑比较大小仍相等
            if (!searched) {
                TreeNode<K,V> q, ch;
                // 标记已搜索
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                     // 依次从p的左节点和右节点找值相同的节点,如果找到就返回
                    return q;
            }
            // 如果找不到,就比较class name甚至是k对象本身的hashCode(忽略重写的hashCode方法逻辑)
            dir = tieBreakOrder(k, pk);
        }

        // 赋值p到xp
        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // 根据dir找p的左节点或右节点,如果是null的话
            // 获取xp的下一个节点
            // 这里需要注意prev和next是链表中的概念
            // HashMap在树节点中还同时维护着链表的前后关系
            Node<K,V> xpn = xp.next;
            // 新建一个TreeNode,这个TreeNode下一个节点是xp的next节点
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            // 关联新创建的x节点到树中
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            // 关联链表结构
            xp.next = x;
            // x的前一个节点设为xp
            // x的父节点设置为xp
            x.parent = x.prev = xp;
            // 如果xp下一个节点存在,设置它的前一个节点为新插入的x节点
            // 到这里链表结构的节点新增和树结构的节点新增都已完成
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            // 插入节点后进行平衡树操作,然后找出平衡后的根节点,作为在bin中的first节点
            moveRootToFront(tab, balanceInsertion(root, x));
            // 新插入节点的情况返回null
            return null;
        }
        // 如果上面p的左节点或右节点存在,需要再递归处理它的左节点或右节点
    }
}

balanceInsertion方法用于插入节点之后平衡红黑树。每次插入数据前树都是平衡过的,只需考虑新加入节点造成的影响。

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    // x为新插入的节点
    // 新插入的节点永远是红色的。如果插入后不符合红黑树规则,再做变换
    // 如果新插入的节点是黑色的,那么一定会出现这条路径上黑色节点多于其他路径这种情况
    // 即每次插入节点都必须要平衡,效率很低
    x.red = true;
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        // 一直循环,直到手动退出
        if ((xp = x.parent) == null) {
            // 新插入的节点没有父节点,意思是新插入的节点为树的根节点
            // 根据红黑树规则,根节点一定是黑色节点
            x.red = false;
            // 返回根节点
            return x;
        }
        else if (!xp.red || (xpp = xp.parent) == null)
            // x节点为黑色,或者没有祖父节点,无需操作返回root节点
            // 这个if分支只会在递归向上变换的时候才会进入
            return root;
        if (xp == (xppl = xpp.left)) {
            // 父节点为红色
            // 父节点是祖父节点的左节点
            if ((xppr = xpp.right) != null && xppr.red) {
                // xppr是祖父节点的右节点,即叔叔节点
                // 如果叔叔节点也是红色,只需做变色处理
                // 父节点和叔节点本来是红色的,将他们变为黑色
                xppr.red = false;
                xp.red = false;
                // 将祖父节点变为红色
                xpp.red = true;
                // 当前节点设置为祖父节点,递归变色或旋转过程
                x = xpp;
            }
            else {
                // 如果叔叔节点不存在或者是黑色
                // 需要将树旋转
                if (x == xp.right) {
                    // 如果当前节点是父节点的右节点,需要将父节点左旋
                    // 将xp作为当前节点
                    root = rotateLeft(root, x = xp);
                    // 重新赋值旋转后的xpp(祖父节点)
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    // 如果父节点存在,设置父节点为黑色
                    xp.red = false;
                    if (xpp != null) {
                        // 祖父节点设为红色
                        xpp.red = true;
                        // 祖父节点右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        else {
            // 父节点为红色
            // 父节点是祖父节点的右节点
            // 和上面if分支的处理方式相同,只是逻辑反过来而已
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.left) {
                    // 如果当前节点是父节点的左节点,需要将父节点右旋
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    // 父节点设为黑色
                    xp.red = false;
                    if (xpp != null) {
                        // 祖父节点设为红色,然后左旋
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

紧接着我们分析旋转方法。

rotateLeft方法代码如下所示。

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    // p为需要左旋的节点
    TreeNode<K,V> r, pp, rl;
    if (p != null && (r = p.right) != null) {
        // r赋值为p的右节点
        // 如果p和p的右节点存在
        // 这段用来调整子树
        if ((rl = p.right = r.left) != null)
            // r的左节点变为p的右节点
            // rl节点为从右子树移动到左子树的节点
            // rl的父节点不再为r,需要设置为p
            rl.parent = p;
        // 这段用来调整父节点和旋转后的r节点的关系
        if ((pp = r.parent = p.parent) == null)
            // 右节点的父节点不再为p,需要调整为p的父节点
            // pp设为r的父节点
            // 如果pp不存在,说明旋转过后的r为目前树的根节点
            // 重新设置root节点,将root节点标记为黑色
            (root = r).red = false;
        else if (pp.left == p)
            // 如果旋转之前当前节点是pp的左节点
            // 那么旋转后pp的左节点为r
            pp.left = r;
        else
            // 同理,旋转之前当前节点是pp的右节点
            // 那么旋转后pp的右节点为r
            pp.right = r;
        // 这段用来调整r和p的关系
        // p变为r的左节点
        r.left = p;
        // p的父节点为r
        p.parent = r;
    }
    return root;
}

右旋的逻辑和左旋基本相同,唯一区别就是代码中左右节点反过来。不再赘述。

插入节点平衡逻辑整理如下:

  1. 插入的节点永远为红色
  2. 如果插入节点的父节点为黑色,不需要平衡
  3. 如果插入节点的父节点为红色。分为下面两种情形。

下面只讨论插入节点的父节点是祖父节点的左节点(xp == xppl)。

如果xp == xppr,和上面的情形逻辑相同,操作方向对称过来即可,不再赘述。

删除数据

removeTreeNode方法在树中删除当前节点(谁调用removeTreeNode就删除谁)。

红黑树节点删除分为如下步骤:

这里的后继节点是比删除节点大的最小节点。

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                          boolean movable) {
    // movable是删除节点的时候可否移动其他节点
    int n;
    if (tab == null || (n = tab.length) == 0)
        return;
    // 计算节点hash
    int index = (n - 1) & hash;
    // 找到树的root节点(对应bin中的第一个节点)
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    // 从链表的范畴,将本节点(要删除的节点)剔除
    // succ为当前节点的后继节点,pred为前置节点
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    if (pred == null)
        // 如果没有前置节点,把bin的第一个节点设置为后继节点
        tab[index] = first = succ;
    else
        // 否则把前置节点和后继节点连起来,跳过要删除的当前节点
        pred.next = succ;
    if (succ != null)
        // 如果有后继节点,把它和前置节点连起来
        succ.prev = pred;
    if (first == null)
        return;
    if (root.parent != null)
        // 如果root节点不是tree真正的root节点,找到它
        root = root.root();
    if (root == null
        || (movable
            && (root.right == null
                || (rl = root.left) == null
                || rl.left == null))) {
        // 树中元素太少,退化为链表结构
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    // p为要删除的节点,pl是要删除节点的左节点,right是要删除节点的右节点,replacement是替换掉要删除节点的节点
    // 删除一个节点后,为了仍保持树结构,需要找到比删除节点大的最小节点来替换它,这个替换的节点就是replacement
    if (pl != null && pr != null) {
        // 最复杂的情况,pl和pr都存在
        TreeNode<K,V> s = pr, sl;
        while ((sl = s.left) != null) // find successor
            // 一直向下查找pr的各级左节点,找到比删除节点大的最小节点
            s = sl;
        // s节点和p节点交换颜色
        // 后面会交换s和p节点,意思就是s节点和p节点所在位置的颜色不变
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        if (s == pr) { // p was s's direct parent
            // 如果正好p的右节点是s,即s的父节点是p
            // s p交换位置
            p.parent = s;
            s.right = p;
        }
        else {
            TreeNode<K,V> sp = s.parent;
            if ((p.parent = sp) != null) {
                // p的父节点指向s的父节点
                // p取代原来s的位置
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            if ((s.right = pr) != null)
                // s右节点设为p的右节点
                // p右节点的父节点设置为s
                // 即p的右子树关联到s上
                pr.parent = s;
        }
        // p左节点清空
        p.left = null;
        if ((p.right = sr) != null)
            // p右节点设为s的右节点
            // sr父节点设置为p
            sr.parent = p;
        if ((s.left = pl) != null)
            // s不可能存在左子树,因为s是刚好比p大的最小元素,是从pr节点开始一直查找左节点,直到它是叶子节点的结果(一直查找直到左节点是null为止)
            // s的左节点和p原本的左节点树建立联系
            pl.parent = s;
        // 这段if用来关联s和pp节点
        if ((s.parent = pp) == null)
            // 设置s的父节点为p的父节点
            // 如果为null,说明现在s为根节点
            root = s;
        else if (p == pp.left)
            // pp关联到s节点
            // s取代p节点
            pp.left = s;
        else
            // 同上
            pp.right = s;
        // 到这里为止s和p节点已完成位置交换
        // 如果s有右节点,replacement为右节点
        // 否则为p,接下来会移除p节点
        // sl肯定为null,所以这里不用考虑
        if (sr != null)
            replacement = sr;
        else
            replacement = p;
    }
    else if (pl != null)
        // 如果p的子节点只有左或右,replacement取这个唯一的子节点
        replacement = pl;
    else if (pr != null)
        // 同上
        replacement = pr;
    else
        // 如果没有任何子节点(1)
        replacement = p;
    if (replacement != p) {
        // replacement为sr
        // 设置sr的父节点为交换过位置之后的p节点的parent
        // p节点被孤立
        TreeNode<K,V> pp = replacement.parent = p.parent;
        if (pp == null)
            // 如果pp为null,说明root节点就是replacement节点
            root = replacement;
        // 下面将pp直接和replacement关联起来,p节点彻底和树断开联系
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        // p和其他所有节点解除关系
        p.left = p.right = p.parent = null;
    }

    // 如果删除的节点(现在的p节点,颜色为原来s节点的颜色,因为前面s和p互换过颜色)是红节点,不需额外操作树仍然是平衡的
    // 否则需要做删除后平衡
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

    if (replacement == p) {  // detach
        // (1)中的情况,p没有任何子节点
        TreeNode<K,V> pp = p.parent;
        // 将p和p的父节点解除关系
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
    if (movable)
        // 将root节点作为bin中存放的第一个节点
        moveRootToFront(tab, r);
}

上面的逻辑总结为:

  1. 找出后继节点s(比p大的最小节点,即pr递归查找left节点,直到left节点为null为止)。
  2. s和p节点交换位置,s原本的右子树关联到p节点上,p原本的左右子树关联到s节点上。
  3. 如果p节点有子节点,将pp节点和p的子节点(只可能有右节点)直接连接。p节点被孤立,将被移除。替换p节点的节点为原s的右节点。
  4. 如果p节点为红色节点,直接移除不违反红黑树规则。否则需要做删除后平衡。
  5. 如果p没有子节点,直接移除p。替换p的节点是p本身。

balanceDeletion方法删除后平衡。删除节点之前的树是平衡过的,仅需要考虑本次删除节点造成的影响。

static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                           TreeNode<K,V> x) {
    // x为替换节点,即removeTreeNode中的replacement
    // 如果s,p交换前s没有右节点,replacement为交换后的p节点,否则为交换后的p节点的右节点(即交换前的s节点的右节点)
    // 方法返回值为平衡后树的根节点
    for (TreeNode<K,V> xp, xpl, xpr;;) {
        if (x == null || x == root)
            // x不存在或者x就是root,返回root
            return root;
        else if ((xp = x.parent) == null) {
            // 如果x是root节点,s,p交换后root节点可能发生变化
            // 根据红黑树规则,设置x节点为黑色
            x.red = false;
            // 返回x节点
            return x;
        }
        else if (x.red) {
            // 如果x是红节点,变为黑色
            // 如果x是叶子节点,移除了不影响平衡下
            // 如果x不是叶子节点,p节点的右节点是replacement节点,被移除的p节点一定是黑色的(两个红色节点不可能相邻)
            // 移除p后少一个黑色节点,把x变为黑色后刚好弥补,树结构仍然正确,无需进一步处理
            x.red = false;
            return root;
        }
        else if ((xpl = xp.left) == x) {
            // x是黑色节点,x是其父节点的左节点
            // (1)
            if ((xpr = xp.right) != null && xpr.red) {
                // x的右兄弟节点为红色,将其变为黑色
                xpr.red = false;
                // 父节点变为红色
                xp.red = true;
                // 左旋父节点,为左子树补充一个黑色节点,右子树黑节点不变
                root = rotateLeft(root, xp);
                // 赋值旋转后的兄弟节点,为原兄弟节点的左节点(如果有的话),黑色
                xpr = (xp = x.parent) == null ? null : xp.right;
            }
            // 如果没有兄弟节点,此时子树已经平衡,需要向上递归执行
            if (xpr == null)
                x = xp;
            else {
                // 如果有兄弟节点
                // 到这里xpr一定是黑色
                // 如果xpr存在且为黑色,不走上面的(1)处的if分支
                // 如果xpr是上面(1)处if分支左旋之后的新xpr,这个新xpr是原来x兄弟节点的左节点
                // 原来兄弟节点是红色(进if分支的条件),由红黑树规则可知,红色节点不可能直接连接
                // 所以原来x兄弟节点的左节点一定是黑色的
                // 因此这里xpr一定是黑色
                TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                // sl为兄弟节点左节点,sr为兄弟节点右节点
                if ((sr == null || !sr.red) &&
                    (sl == null || !sl.red)) {
                    // 兄弟节点的左右节点都不是红色节点
                    // 设置兄弟节点为红色
                    // 此时兄弟节点所在子树的黑色节点数减少1,和x节点子树相同,xp以下已平衡
                    xpr.red = true;
                    // 向上递归
                    x = xp;
                }
                else {
                    // 兄弟节点的左右节点存在红节点
                    if (sr == null || !sr.red) {
                        // 兄弟节点右节点不存在或者是黑色
                        // 兄弟节点左节点不存在或者是红色
                        if (sl != null)
                            // 兄弟节点左节点存在,变为黑色
                            // 左子树黑色+1
                            sl.red = false;
                        // 兄弟节点变为红色
                        // 从兄弟节点开始,左子树黑色数量复原,右子树黑色-1
                        xpr.red = true;
                        // 兄弟节点右旋
                        // sl为黑色,s为红色,sr为黑色
                        // 右旋后左子树黑色节点不变,右子树黑色复原
                        // 恢复平衡
                        root = rotateRight(root, xpr);
                        // 获取右旋后的兄弟节点
                        // 这段if变换后,兄弟节点是原兄弟节点的左节点,为黑色
                        // 兄弟节点的右节点为红色
                        xpr = (xp = x.parent) == null ?
                            null : xp.right;
                    }
                    // 下面统一处理兄弟节点的右节点为红色这种情况
                    // 这里思路就是从兄弟节点右子树中借一个红色节点过来(sr)
                    // 旋转前后保持原来x,xp和s位置的节点颜色不变
                    // 这样x节点所在子树就比原来多了一个黑色节点,x兄弟节点所在子树黑色不变
                    // x节点替换后可保持平衡
                    // 如果兄弟节点存在
                    if (xpr != null) {
                        // 兄弟节点设置为父节点的颜色
                        // 如果父节点不存在,兄弟节点设置为黑色
                        xpr.red = (xp == null) ? false : xp.red;
                        // 如果兄弟节点右节点存在,设置为黑色
                        if ((sr = xpr.right) != null)
                            sr.red = false;
                    }
                    if (xp != null) {
                        // x有父节点,则父节点设置为黑色,xp左右树黑色都+1
                        xp.red = false;
                        // 左旋父节点
                        root = rotateLeft(root, xp);
                    }
                    // 将x设为root,递归
                    x = root;
                }
            }
        }
        else { // symmetric
            // 如果x是黑色节点,x是父节点的右节点
            // 和上面的逻辑相同,只有操作方向是反过来的,完全对称
            if (xpl != null && xpl.red) {
                xpl.red = false;
                xp.red = true;
                root = rotateRight(root, xp);
                xpl = (xp = x.parent) == null ? null : xp.left;
            }
            if (xpl == null)
                x = xp;
            else {
                TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                if ((sl == null || !sl.red) &&
                    (sr == null || !sr.red)) {
                    xpl.red = true;
                    x = xp;
                }
                else {
                    if (sl == null || !sl.red) {
                        if (sr != null)
                            sr.red = false;
                        xpl.red = true;
                        root = rotateLeft(root, xpl);
                        xpl = (xp = x.parent) == null ?
                            null : xp.left;
                    }
                    if (xpl != null) {
                        xpl.red = (xp == null) ? false : xp.red;
                        if ((sl = xpl.left) != null)
                            sl.red = false;
                    }
                    if (xp != null) {
                        xp.red = false;
                        root = rotateRight(root, xp);
                    }
                    x = root;
                }
            }
        }
    }
}

下面总结最复杂的情况:删除节点(x)是黑色,并且存在兄弟节点。

如果替换节点是父节点(xp)的左节点(x == xpl)且xpr(兄弟节点)为红色。xp变为红色,xpr变为黑色,左旋xp。之后x的兄弟节点为原来的xprl,一定是黑色。变换为下面的场景。

如果替换节点是父节点(xp)的左节点(x == xpl)且xpr(兄弟节点)为黑色。

同理,如果替换节点是父节点(xp)的右节点(x == xpr),逻辑和前面的相同,区别仅是操作方向对称过来,不再赘述。

树结构退化为链表

untreeify方法将树结构退化为链表。

// 调用这个方法的节点应为头节点(树中最小的节点)
final Node<K,V> untreeify(HashMap<K,V> map) {
    // 创建head(hd)和tail(tl)
    Node<K,V> hd = null, tl = null;
    for (Node<K,V> q = this; q != null; q = q.next) {
        // 从当前节点逐个向后遍历
        // 替换树节点为普通链表节点
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            // 开始遍历的时候tl为null,需要指定hd
            hd = p;
        else
            // 链表向后组装
            tl.next = p;
        // 移动链表尾部指针
        tl = p;
    }
    // 返回链表头节点
    return hd;
}

参考文献

https://www.jianshu.com/p/e136ec79235c/

上一篇下一篇

猜你喜欢

热点阅读