JDK8 源码解读：HashMap-核心方法

痛定思痛。 2022-12-24 03:00 157阅读 0赞

### JDK8 源码解读：HashMap-核心方法 ###

*  源码阅读答疑
 *  核心方法
 *   *  hash(Object key)
     *  get(Object key)
     *   *  getNode(int hash, Object key)
         *  getTreeNode(int h, Object k)
         *  find(int h, Object k, Class<?> kc)
     *  put(K key, V value)
     *   *  putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
         *  putTreeVal(HashMap< K, V > map, Node< K, V >\[\] tab, int h, K k, V v)
         *  moveRootToFront(Node< K, V >\[\] tab, TreeNode< K, V > root)
         *  treeifyBin(Node< K, V >\[\] tab, int hash)
         *  treeify(Node< K, V >\[\] tab)
     *  remove(Object key)
     *   *  removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)
         *  removeTreeNode(HashMap< K, V > map, Node< K, V >\[\] tab, boolean movable)
 *  结尾
 *  源码

# 源码阅读答疑 #

个人对于学习源码时的体会，以及自己遇到困惑的解答，有问题可以来问  
[源码阅读问答][Link 1]

# 核心方法 #

## hash(Object key) ##

扰动函数，计算 key 的 hash 值，扰动函数目的是降低 hash 冲突概率

实在不理解为啥这么算的，那就只要知道他是这么算就好了

/** * 扰动函数 * 让 key 的 hashcode 高16位与低16位进行异或运算 * 目的是为了降低 hash 冲突的概率 * 位的异或运算（^） * 运算规则是：两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1。 */
    static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

## get(Object key) ##

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

### getNode(int hash, Object key) ###

逻辑很好理解

1.  先找到数组上的位置
2.  如果当前节点为红黑树，调用 getTreeNode 按照红黑树的方式去找
3.  否则就是单链表，按照链表循环 next 去找

/** * 获取节点 * Implements Map.get and related methods. * * @param hash hash for key * @param key the key * @return the node, or null if none */
    final Node<K,V> getNode(int hash, Object key) { 
        // tab：map
        // first：hash 对应的节点
        // n：数组容量
        // e：链表循环到的节点
        // k：链表循环到的节点的 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) { 
            // 不存在 hash 冲突，判断 hash 相等且key 相等，返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 存在 hash 冲突
            if ((e = first.next) != null) { 
                // 如果类型是红黑树
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 不是红黑树，链表迭代判断获取
                do { 
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

### getTreeNode(int h, Object k) ###

/** * Calls find for root node. */
    final TreeNode<K,V> getTreeNode(int h, Object k) { 
        // (parent != null) ? root() : this 目的是为了保证从根节点开始遍历
        return ((parent != null) ? root() : this).find(h, k, null);
    }

### find(int h, Object k, Class<?> kc) ###

PS：注意 find 是 TreeNode 红黑树对象中的方法，因此这里的 this 是指代当前红黑树

主要逻辑就是在比较是左树节点还是有右树节点上，循环树节点，然后根据 hash 值进行比较

/** * Finds the node starting at root p with the given hash and key. * The kc argument caches comparableClassFor(key) upon first use * comparing keys. * @param h hash * @param k key * @param kc 值类型 */
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) { 
        TreeNode<K,V> p = this;
        do { 
            // ph：当前节点 hash 值
            // dir：对象对比后的大小关系
            // pk：key
            int ph, dir; K pk;
            // pl：左侧节点
            // pr：右侧节点
            TreeNode<K,V> pl = p.left, pr = p.right, q;
            // 通过 hash 判断节点是在左分支还是右分支
            // 如果是相等，说明找到
            if ((ph = p.hash) > h)
                p = pl;
            else if (ph < h)
                p = pr;
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
            else if (pl == null)
                p = pr;
            else if (pr == null)
                p = pl;
            // 能进这玩意，说明 key 是个对象，且实现了 Comparable
            else if ((kc != null ||
                      // 比较 key 参数类型
                      (kc = comparableClassFor(k)) != null) &&
                     // 比较对象是否相等，其中如果没实现 Comparable 直接返回 0
                     (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr;
            // 代码走到此处, 代表key所属类没有实现Comparable, 固定右边遍历
            else if ((q = pr.find(h, k, kc)) != null)
                return q;
            // “pr.find(h, k, kc)”为空, 固定左边遍历
            else
                p = pl;
        } while (p != null);
        return null;
    }

## put(K key, V value) ##

我相信是个开发都看得懂

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

### putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) ###

/** * Implements Map.put and related methods. * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent 如果 true，不改变已经有的值 * @param evict 如果 false, 说明处于创建模式 * @return previous value, or null if none */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) { 
        // tab：map
        // n：数组容量
        // i：数组索引
        // p：数组节点
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 数组长度为 0 扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果 hash 后发现数组上此节点是空的
        // 万事大吉直接创建一个新节点即可
        // hash 对应数组索引计算公式为 (n - 1) & hash
        // x%2^n == x&(2^n-1)，其中 x 对应 hash，2^n 对应 n，n 为数组容量且符合要求
        // 这个是高效取余运算，why？no why，数学公式
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 否则，mmp 的 hash 冲突了
        else { 
            // e：链表节点
            // k：对应 key
            Node<K,V> e; K k;
            // 第一个节点就找到了，可喜可贺
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果类型为红黑树
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { 
                // 链表情况
                for (int binCount = 0; ; ++binCount) { 
                    // 如果下个节点为 null，则创建一个节点
                    if ((e = p.next) == null) { 
                        p.next = newNode(hash, key, value, null);
                        // 长度过长，转红黑树
                        // 正常是从 1-8 扩容，这里是 0-7
                        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))))
                        break;
                    p = e;
                }
            }
            // e 为空，说明是新创建的节点，e 不为空，说明此节点原来就已经存在
            // 注意上方 p.next = newNode(hash, key, value, null); 后面不在有 e = p.next 的操作，因此新创建的节点不会给 e
            if (e != null) {  // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 给 LinkedHashMap 回调用的，LinkedHashMap 回调设置双向链表属性，HashMap 本身调用没作用
                // 网上说这是为 LinkedHashMap 留的后路
                // 于是我特意去看了 LinkedHashMap 源码，发现里面存在通过 Map 对象构建 LinkedHashMap 的构造函数
                // 因此可以说的通，按我理解应该是为了 LinkedHashMap 在调用 HashMap 方法 put 时，此时可以通过这里的 afterNodeAccess 来设置双向链表属性
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // size 键值对个数增加
        if (++size > threshold)
            // 扩容
            resize();
        // 同上面 afterNodeAccess
        // 说是可能删除 LinkedHashMap 上最旧的节点，为了节省内存，条件是 size > 200
        // 个人认为可以不管
        afterNodeInsertion(evict);
        return null;
    }

### putTreeVal(HashMap< K, V > map, Node< K, V >\[\] tab, int h, K k, V v) ###

/** * 红黑树 put 值 * Tree version of putVal. */
    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;
        // 保证从首节点开始遍历
        TreeNode<K,V> root = (parent != null) ? root() : this;
        for (TreeNode<K,V> p = root;;) { 
            // 前面部分的逻辑和之前 getNode 中是一样的，通过判断 hash 大小来判断，是在左分支还是右分支
            // dir：左分支为 -1，右分支为 1，默认 0 说明 hash 一样
            // pk：当前节点的 key
            int dir, ph; K pk;
            if ((ph = p.hash) > h)
                dir = -1;
            else if (ph < h)
                dir = 1;
            // 说明已经有个一样的 key 存在
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
            // key 为对象且实现了 Comparable
            else if ((kc == null &&
                      (kc = comparableClassFor(k)) == null) ||
                     // 么实现 Comparable 情况下直接返回 0
                     (dir = compareComparables(kc, k, pk)) == 0) { 
    
                // 走到这就说嘛没实现 Comparable
                // 通过 find
                if (!searched) { 
                    TreeNode<K,V> q, ch;
    
                    // 利用 find 方法尝试左右分支看看能否直接找到相同的节点，能找到就直接返回节点
                    // 如果都没找到，searched = true 后，后续不再尝试比较内容相等
                    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))
                        return q;
                }
                // 通过之前的比如 find 方法，我们知道对象的比较需要实现 Comparables，否则无法正确比较
                // 因此，当对象没有实现 Comparables，就需要一种事先约定好的比较方法来进行判断
                dir = tieBreakOrder(k, pk);
            }
    
            TreeNode<K,V> xp = p;
            // 判断左右分支中，是否存在 null的，为 null 说明已经到叶子节点了
            // p = (dir <= 0) ? p.left : p.right 这里将下个节点赋值给 p
            if ((p = (dir <= 0) ? p.left : p.right) == null) { 
                Node<K,V> xpn = xp.next;
                TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                // 通过前面的 dir 判断这个节点是左节点还是右节点
                // 然后添加节点
                if (dir <= 0)
                    xp.left = x;
                else
                    xp.right = x;
                xp.next = x;
                // 红黑树 prev 与 parent 一样
                x.parent = x.prev = xp;
                if (xpn != null)
                    ((TreeNode<K,V>)xpn).prev = x;
                // balanceInsertion：新增时平衡红黑树
                // moveRootToFront：保证红黑树首节点为数组上对应的节点
                moveRootToFront(tab, balanceInsertion(root, x));
                // 返回空，意味着产生了一个新节点
                return null;
            }
        }
    }

### moveRootToFront(Node< K, V >\[\] tab, TreeNode< K, V > root) ###

这个代码本来不是很想贴，但是看着有点逻辑，也放上来好了

就是保住红黑树与双向链表，首节点都是同一个节点，也对应数组的该位置的首节点

/** * 保证红黑树首节点为数组上对应的节点 * Ensures that the given root is the first node of its bin. */
    static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { 
        int n;
        if (root != null && tab != null && (n = tab.length) > 0) { 
            int index = (n - 1) & root.hash;
            // 找到数组上的首节点
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
            // 如果发现首节点不对
            if (root != first) { 
                Node<K,V> rn;
                tab[index] = root;
                // rp：root 双向链表的上个节点
                TreeNode<K,V> rp = root.prev;
                // rn：root 双向链表的下个节点
                if ((rn = root.next) != null)
                    // root 双向链表的下个节点的上个节点为 root 的上个节点
                    // 可以理解为由于 root 现在是首节点了，所以双向链表中把 root 节点摘出来，然后把它上下两节点接起来
                    ((TreeNode<K,V>)rn).prev = rp;
                if (rp != null)
                    rp.next = rn;
                // 然后把 root 变为首节点，把之前的首节点接 root 下面
                // 目的应该是为了保证结构合理性，要不然明明是首节点，但是双向链表部分的结构却存在上个节点，也不太合理
                if (first != null)
                    first.prev = root;
                root.next = first;
                root.prev = null;
            }
            // 断言，结构检查
            assert checkInvariants(root);
        }
    }

### treeifyBin(Node< K, V >\[\] tab, int hash) ###

`if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)` 这行代码就是前面说的，如果数组容量没达到 64，就只是扩容，不转红黑树的校验

/** * 链表转红黑树 * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */
    final void treeifyBin(Node<K,V>[] tab, int hash) { 
        // n：数组容量
        // index：索引
        // e：数组索引位置的红黑树或链表
        int n, index; Node<K,V> e;
        // 判断 table 是否 null，且长度小于 64，扩容
        // 因此链表转红黑树的条件，一个是达到 8，另一个是数组容量要达到 64
        // 不满足就只进行扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) { 
            // hd：双向链表首节点
            // tl：双向链表尾结点
            TreeNode<K,V> hd = null, tl = null;
            do { 
                // 将链表节点对象替换为红黑树节点对象
                TreeNode<K,V> p = replacementTreeNode(e, null);
                // 如果尾结点为空
                if (tl == null)
                    // 当前节点为首节点
                    hd = p;
                else { 
                    // 设置红黑树双向链表
                    // p 为当前节点
                    // 当前节点的上个节点为尾结点，废话接在屁股后面没毛病
                    p.prev = tl;
                    // 上个节点的下个节点为当前节点，没毛病老铁
                    tl.next = p;
                }
                // 设置当前节点为尾结点
                tl = p;
            } while ((e = e.next) != null);
            // 数组上设置首节点
            if ((tab[index] = hd) != null)
                // 链表转红黑树
                hd.treeify(tab);
        }
    }

### treeify(Node< K, V >\[\] tab) ###

具体的链表转红黑树的逻辑

`balanceInsertion` 方法是指新增节点时，通过旋转变色对树进行平衡，确实过于抽象，看一半看不下去了

/** * 链表转红黑树 * Forms tree of the nodes linked from this node. */
    final void treeify(Node<K,V>[] tab) { 
        TreeNode<K,V> root = null;
        // this：当前节点，从头结点开始
        // x：构建红黑树，当前节点
        // next：当前节点的下个节点
        for (TreeNode<K,V> x = this, next; x != null; x = next) { 
            next = (TreeNode<K,V>)x.next;
            x.left = x.right = null;
            // 设置红黑树首节点
            if (root == null) { 
                x.parent = null;
                x.red = false;
                root = x;
            }
            else { 
                K k = x.key;
                int h = x.hash;
                Class<?> kc = null;
                // 依然通过 hash 判断是左分支还是右分支
                for (TreeNode<K,V> p = root;;) { 
                    int dir, ph;
                    K pk = p.key;
                    if ((ph = p.hash) > h)
                        dir = -1;
                    else if (ph < h)
                        dir = 1;
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        // 通过之前的比如 find 方法，我们知道对象的比较需要实现 Comparables，否则无法正确比较
                        // 因此，当对象没有实现 Comparables，就需要一种事先约定好的比较方法来进行判断
                        dir = tieBreakOrder(k, pk);
    
                    TreeNode<K,V> xp = p;
                    if ((p = (dir <= 0) ? p.left : p.right) == null) { 
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;
                        else
                            xp.right = x;
                        // 新增时通过旋转变色平衡红黑树
                        // 可以看到整个方法都没有对颜色进行控制，因为颜色都在这里控制了
                        root = balanceInsertion(root, x);
                        break;
                    }
                }
            }
        }
        // 保证红黑树首节点为数组上对应的节点
        moveRootToFront(tab, root);
    }

## remove(Object key) ##

移除 HashMap 的键值对

/** * Removes the mapping for the specified key from this map if present. * * @param key key whose mapping is to be removed from the map * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */
    public V remove(Object key) { 
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

### removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) ###

/** * 移除节点 * Implements Map.remove and related methods. * * @param hash hash for key * @param key the key * @param value 匹配值或者忽略 * @param matchValue 如果为 true，只有当 value 相等才移除 * @param movable 如果为 false，则删除时不要移动其他节点 * @return the node, or null if none */
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) { 
        // tab：map，数组部分
        // p：node 头节点，do while 处用来记录循环处理过的最后一个非目标节点
        // n：数组容量
        // index：数组索引
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        // 判断你数组不为 null，判断数组长度大于 0，判断索引位置有值
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) { 
    
            // node：当前节点
            // e：链表情况下循环到的节点
            // k：当前节点 key
            // v：当前节点 value
            Node<K,V> node = null, e; K k; V v;
            // hash 一样，key 一样说明找到节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            // 不一样就下个节点
            else if ((e = p.next) != null) { 
                // 判断是否为红黑树
                if (p instanceof TreeNode)
                    // 这里会调用 find 去找节点
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else { 
                    // 链表情况，循环到 hash 一致，key 一致则找到
                    do { 
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) { 
                            node = e;
                            break;
                        }
                        // 没找到，将 p 指向这个已经处理过的节点
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // 如果又找到数据，如果需要 value，则 value 需要相等
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) { 
                // 红黑树移除节点
                if (node instanceof TreeNode)
                    // 移除红黑树上节点
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    // 链表情况下，再判断下是否是首节点，是的话首节点改为删除节点的下个节点
                    // 非首节点情况，由于 if 判断找到节点后会直接 return，导致 p 少走一个 p = e
                    // 首节点例外 p = e，因为 p 已经预先指向首节点
                    tab[index] = node.next;
                else
                    // 这里走链表非首节点情况
                    p.next = node.next;
                ++modCount;
                // size 键值对个数减少
                --size;
                // 给 LinkedHashMap 回调用的，在 LinkedHashMap 情况下，删除了节点，自然需要调整链表的连接
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

### removeTreeNode(HashMap< K, V > map, Node< K, V >\[\] tab, boolean movable) ###

/** * 移除红黑树上节点 * PS：已经在 TreeNode 对象中，因此可以直接拿到红黑树的属性 * @param map HashMap 本身 * @param tab 数组部分 * @param movable 如果为 false，则删除时不要移动其他节点 * Removes the given node, that must be present before this call. * This is messier than typical red-black deletion code because we * cannot swap the contents of an interior node with a leaf * successor that is pinned by "next" pointers that are accessible * independently during traversal. So instead we swap the tree * linkages. If the current tree appears to have too few nodes, * the bin is converted back to a plain bin. (The test triggers * somewhere between 2 and 6 nodes, depending on tree structure). */
    final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                              boolean movable) { 
        // 数组容量
        int n;
        if (tab == null || (n = tab.length) == 0)
            return;
        // 计算在数组上的位置
        int index = (n - 1) & hash;
        // first：第一个节点
        // root：首节点
        // rl：根节点往后两次左节点中，不为 null 的节点，(rl = root.left) == null || rl.left == null
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
        // succ：当前要移除的节点的下个节点
        // pred：当前要移除的节点的上个节点
        TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    
        // 双向链表不存在上个节点，说明此节点为首节点
        // moveRootToFront 方法会保证红黑树的首节点，也是其双向链表的首节点
        // 因此直接将当前节点的下个节点作为首节点
        if (pred == null)
            tab[index] = first = succ;
        else
            // 否则将双向链表上下节点接起来
            // 当前要移除的节点的上个节点的 next 指向当前要移除的节点的下个节点
            pred.next = succ;
    
        // 如果存在当前要移除的节点的下个节点
        // 如果存在当前要移除的节点的下个节点的 prev 指向当前要移除的节点的上个节点
        // 和上面的判断作用一样，就是改变上下两个节点的双向链表指向，保证接起来是对的
        if (succ != null)
            succ.prev = pred;
    
        if (first == null)
            return;
    
        // 循环找到最上级节点作为首节点
        if (root.parent != null)
            root = root.root();
    
        // 如果发现首节点为空，或者首节点的左右子节点存在 null，或者首节点的左节点的左节点存在 null，说明节点数量不可能达到 8
        // 转为链表
        // 这点，根据红黑树任意节点到其叶子节点的黑色节点数量相同，可以验证
        if (root == null
            || (movable
                && (root.right == null
                    || (rl = root.left) == null
                    || rl.left == null))) { 
            tab[index] = first.untreeify(map);  // too small
            return;
        }
        // p：当前要移除的红黑树节点
        // pl：当前要移除的红黑树节点的左子节点
        // pr：当前要移除的红黑树节点的右子节点
        // replacement：当前节点被替换为的节点
        TreeNode<K,V> p = this, pl = left, pr = right, replacement;
        if (pl != null && pr != null) { 
            // sl：从当前要移除的红黑树节点的右子节点开始找，循环左节点，直到左叶子节点
            // s：sl 的父级节点
            TreeNode<K,V> s = pr, sl;
            while ((sl = s.left) != null) // find successor
                s = sl;
            boolean c = s.red; s.red = p.red; p.red = c; // swap colors
            // s 的右节点
            TreeNode<K,V> sr = s.right;
            // s 的父级节点
            TreeNode<K,V> pp = p.parent;
            if (s == pr) {  // p was s's direct parent
                p.parent = s;
                s.right = p;
            }
            else { 
                TreeNode<K,V> sp = s.parent;
                if ((p.parent = sp) != null) { 
                    if (s == sp.left)
                        sp.left = p;
                    else
                        sp.right = p;
                }
                if ((s.right = pr) != null)
                    pr.parent = s;
            }
            p.left = null;
            if ((p.right = sr) != null)
                sr.parent = p;
            if ((s.left = pl) != null)
                pl.parent = s;
            if ((s.parent = pp) == null)
                root = s;
            else if (p == pp.left)
                pp.left = s;
            else
                pp.right = s;
            if (sr != null)
                replacement = sr;
            else
                replacement = p;
        }
        else if (pl != null)
            replacement = pl;
        else if (pr != null)
            replacement = pr;
        else
            replacement = p;
    
        // replacement = sr 情况
        if (replacement != p) { 
            // pp：替代节点的父级节点，为原删除节点的父级节点
            TreeNode<K,V> pp = replacement.parent = p.parent;
            // 为空说明为首节点
            if (pp == null)
                root = replacement;
            // 判断替代的是左节点还是右节点
            else if (p == pp.left)
                pp.left = replacement;
            else
                pp.right = replacement;
            p.left = p.right = p.parent = null;
        }
    
        // 移动完后，通过变色旋转保证红黑树正确
        // balanceDeletion：专门给删除节点时用于平衡红黑树
        TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
    
        // 直接分离当前节点
        if (replacement == p) {   // detach
            TreeNode<K,V> pp = p.parent;
            p.parent = null;
            if (pp != null) { 
                if (p == pp.left)
                    pp.left = null;
                else if (p == pp.right)
                    pp.right = null;
            }
        }
        if (movable)
            moveRootToFront(tab, r);
    }

# 结尾 #

[JDK8 源码解读：HashMap-变量与结构][JDK8 _HashMap-]

[JDK8 源码解读：HashMap-构造函数][JDK8 _HashMap- 1]

[JDK8 源码解读：HashMap-核心方法][JDK8 _HashMap- 2]

# 源码 #

[JDK 1.8 源码阅读-注释版][JDK 1.8 _-]

[JDK 1.8 源码阅读][JDK 1.8]

[Link 1]: https://linjinp.blog.csdn.net/article/details/109747337/
[JDK8 _HashMap-]: https://linjinp.blog.csdn.net/article/details/110130658/
[JDK8 _HashMap- 1]: https://linjinp.blog.csdn.net/article/details/110196639/
[JDK8 _HashMap- 2]: https://linjinp.blog.csdn.net/article/details/110196734/
[JDK 1.8 _-]: https://gitee.com/linjinp/jdk1.8-leaning/
[JDK 1.8]: https://gitee.com/linjinp/jdk1.8.0_111-src/