java-HashMap-review

Posted on | In

java.util.HashMap源码赏析

HashMap是java.util包下的一个哈希表，它继承AbstractMap类，实现Map接口

1. 简要介绍

HashMap有三个关键参数capacity、loadFactor以及threshold，这三个参数与HashMap的容量和动态扩容相关，在一开始时HashMap是以链表数组形式保存，当数据量足够大的时候，HashMap就会转换为树节点的形式，而HashMap最大可容纳的条目的个数是2的30次方。

HashMap的程序结构(只注明本文中涉及部分)如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
HashMap<k, v>{
    
    //常量
	serialVersionUID;
    DEFAULT_INITIAL_CAPACITY;
    MAXIMUM_CAPACITY;
    DEFAULT_LOAD_FACTOR;
    TREEIFY_THRESHOLD;
    UNTREEIFY_THRESHOLD;
    MIN_TREEIFY_CAPACITY;
    
    //成员变量
    table;
    entrySet;
    size;
    modCount;
    threshold;
    loadFactor;
    
    //构造方法
    HashMap(int initialCapacity, float loadFactor);
    HashMap(int initialCapacity);
    HashMap();
    HashMap(Map<? extends K, ? extends V> m);
    
    //静态方法
    comparableClassFor(Object x);
    compareComparables(Class<?> kc, Object k, Object x);
    tableSizeFor(int cap);
    
    //成员方法
    putMapEntries(Map<? extends K, ? extends V> m, boolean evict);
    getNode(int hash, Object key)
    putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict);
    resize();
    treeifyBin(Node<K,V>[] tab, int hash);
    removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable);
    
    //内部类
    Node{
        hash;
        key;
        value;
        next;
    }
    
    HashIterator{
        next;
        current;
        expectedModCount;
        index;
    }
    
    HashMapSpliterator<K,V>{
        map;
        current;
        index;
        fence;
        est;
        expectedModCount;
    }
    
    //Node的孙子类
    TreeNode{
        parent;
        left;
        right;
        prev;
        red;
        
        root();
        moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root);
        find(int h, Object k, Class<?> kc);
        getTreeNode(int h, Object k);
        tieBreakOrder(Object a, Object b);
        treeify(Node<K,V>[] tab);
        untreeify(HashMap<K,V> map);
        putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v);
        removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable);
        split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit);
        rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p);
        rotateRight(TreeNode<K,V> root, TreeNode<K,V> p);
        balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x);
        balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x);
    }
}

2. 构造方法

HashMap有三种构造方法：

  1. 空参数，不修改HashMap中的任意成员变量。

  2. HashMap(int initialCapacity)，调用this(int initialCapacity, 0.75)。

  3. HashMap(int initialCapacity, float loadFactor)，这两个参数都自行定义，需要注意的是如果initialCapacity小于0或者loadFactor不大于0的话会抛出IllegalArgumentException异常，initialCapacity如果大于最大容量的话会被修改成最大容量。随后更新对象的loadFactor变量和threshold变量，而更新threshold变量时使用的tableSizeFor(int cap)方法就比较有趣了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    这个鬼才看的懂在干什么，笔者以cap为100演示一下，其中|是按位与操作，而>>>是无符号右移。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    cap = 0000,0000,0000,0000,0000,0000,0110,0100
    n = cap - 1 = 0000,0000,0000,0000,0000,0000,0110,0011
    n >>> 1 = 0000,0000,0000,0000,0000,0000,0011,0001
    n |= n >>> 1 = 0000,0000,0000,0000,0000,0000,0111,0011
    n >>> 2 = 0000,0000,0000,0000,0000,0000,0001,1100
    n |= n >>> 2 = 0000,0000,0000,0000,0000,0000,0111,1111
    n |= n >>> 4 = 0000,0000,0000,0000,0000,0000,0111,1111
    n |= n >>> 8 = 0000,0000,0000,0000,0000,0000,0111,1111
    n |= n >>> 16 = 0000,0000,0000,0000,0000,0000,0111,1111

    将结果换算回十进制，发现是127， 最后返回的是128。我们大胆推测，这个方法是将输入参数cap向上取到第一个比它大的2的n次方。所以无论你给容器设置的初始化大小M是多少，都会被换为第一个不小于这个M的2的n次方。

    如果让笔者写的话

    1
    2
    3
    4
    5
    for(int i = 0; i < 31; i++){
    	if(cap < Math.pow(2, i)){
    		return (int) Math.pow(2, i);
    	}
    }

    看起来虽然短，但是效率低多了，远不如位操作高效，看来前辈还是永远滴神。

无论是哪一个构造方法，都只是修改了HashMap的参数，并没有创建实际的容器，所以当你new一个HashMap对象时，它的容量大小是0，只有当你第一次put一个条目进去时，容器才会真的被创建。

3. 动态扩容

与ArrayList，HashSet等容器类似，当HashMap的容量不足时，就会使用动态扩容来增加容器的容量，动态扩容实际上在添加第一个条目就已经发生了，动态扩容主要涉及的是resize()方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = 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)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    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;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    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) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

3.1. 扩容后的大小

扩容分3种情况：

  1. 原table为空，且原threshold为空

    要使得threshold为空就只有一种情况，使用空参构造方法new HashMap()构造对象并且还没有put第一个条目，然后resize()方法就知道了，这是要默认初始化，将capacity设置为默认值，将threshold设置为默认capacity值乘以默认loadFactor值，即容器大小为16，触发动态扩容的阈值为9。

  2. 原table为空而原threshold不为空

    threshold不为空而原table为空说明是用new HashMap(int initCapacity)或者new HashMap(int initCapacity)新建了HashMap对象而还没put第一个条目，这时候成员变量threshold存的值不是触发动态扩容的阈值，而是目标容量将threshold存的值为初始化容量来初始化容器后，将threshold更新为threshold×loadFactor。

  3. 原table不为空

    如果原table不为空，则说明已经put过条目进容器里了，只是容器里条目的数量超过了threshold而触发了动态扩容。一般而言，动态扩容会把容器的大小翻一番。那为什么是扩到2倍而不是3倍或者1.5倍呢？这就涉及扩容后条目如何重定位。

3.2. 扩容后条目重定位

在重新定位条目之前，先看看之前是如何通过hash值定位条目的。容器存储数据的table的数据类型是Node[]，一个链表头组成的数组，先通过hash值找到条目所在链表的链表头，也就是table[hash(key) & (table.length-1)]，然后遍历链表，找到key值相同的node节点。那么扩容table后，hash(key)虽然没变，但是table.length变为原来的两倍，则hash(key) & (table.length)的值会发生变化，需要在扩容后重新定位条目的位置。

那么，需要如何重新定位呢，愚者(例如笔者)就会遍历原来旧table上的所有条目重新按put操作添加到新table上。意思如下：

1
2
3
4
5
Map<k, v> oldTable = new HashMap(16);
Map<k, v> newTable = new HashMap(32);
for(Map.Entry<k, v> enrty : oldTable){
    newTable.put(entry.geKey(), entry.getValue());
}

显然，在resize()方法中并不是这样做的因为有更高明的方法。先看看原来定位条目位置的位运算是怎么做的：

1
2
3
4
5
6
7
8
9
10
11
hash(key1) = 10110110
hash(key2) = 10100110
table.length - 1 = 1111
hash(key1) & (table.length - 1) = 0110
hash(key1) & (table.length - 1) = 0110
----------------------------------------------------
hash(key1) = 10110110
hash(key2) = 10100110
table.length * 2 - 1 = 11111
hash(key1) & (table.length * 2 - 1) = 10110
hash(key1) & (table.length * 2 - 1) = 00110

在二进制下，翻一番就是加了一位，那么原来位置相同的两个条目，扩容后虽然可能位置不同，但仅仅也只有两种可能的位置，在上面的例子中，只要遍历链表，按其与10000的&操作链表分成两个链表，在添加到新table上即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

4. 二叉树

4.1. 触发将链表转换为二叉树

当HashMap中一个链表的长度超过8时，HashMap就有可能将为这个链表加一个二叉树检索，将原来的Node类型转换为它的子类TreeNode，为什么说可能呢，因为在putVal方法里，当链表长度大于TREEIFY_THRESHOLD时就会触发treeifyBin(Node<K,V>[] tab, int hash)方法，而treeifBin方法只有当hashMap大小大于MIN_TREEIFY_CAPACITY时才会去把Node类型转换为TreeNode类型，否则则会扩容来试图减少链表长度。其中TREEIFY_THRESHOLD的值为8而MIN_TREEIFY_CAPACITY的值为64。

4.2. 将Node转换为TreeNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

treeifBin方法把Node节点转换为TreeNode节点后将原链表变成双向链表，但是还没有建立二叉树。而是通过调用TreeNode中的treeify(Node<K,V>[] tab)方法建立二叉树。

4.3. 建立二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    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;
            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)
                    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);
}

treeif方法遍历链表中的所有节点，然后通过比较节点的key值来建立平衡二叉树，这个方法中有四个关键指针。

  1. root：当前二叉树的根节点
  2. x：当前被扫描的待安置的链表节点
  3. p：当前被扫描来与x进行比较的二叉树上的节点
  4. xp：p指针的上一个位置

比较两个节点的大小时按3个方法进行比较，将结果存在dir中

  1. 比较节点的key的hash值
  2. 若hash值相同且key的类型实现了comparable接口，即key是可比较的，那么则直接比较key的值。
  3. 若hash值相同，且key值不可比较，或者key值是可比较的但比较结果相同则调用tieBreakOrder方法，即比较两个key作为Object时的hash值（无视key的类型中有没有重写hashCode()方法）来强行比较大小，若即使如此两个key还是相等，则返回-1。

只有当两个key的类型不同且都不为null是才会出现dir为0的情况。

比较完p和x的大小后，将xp指向p，将p根据dir的值指向p的左孩子或者右孩子，若之后p为空（即找到了x在二叉树中的位置），则将xp作为x的父母，将x作为xp的孩子。然后使用红黑树方法重新平衡二叉树。

在将双向链表做的所有节点加入到二叉树后，将二叉树的根节点移动到双向链表的链表头。

在动态扩容后，如果原来的树需要被拆成两棵树（链表数量不少于UNTREEIFY_THRESHOLD并且重定位后存在两个节点属于不同的位置），则要在拆开链表后重新建立二叉树。

4.4. 平衡二叉树

HashMap平衡二叉树的算法是红黑树，红黑树的规则如下:

  1. 每个节点要么是黑色，要么是红色
  2. 根节点是黑色
  3. 每个叶子节点（NIL）是黑色
  4. 每个红色结点的两个子结点一定都是黑色
  5. 任意一结点到每个叶子结点的路径都包含数量相同的黑结点

如下图所示就是一个典型的红黑树。

4.4.1. 插入

HashMap中插入树节点的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;;) {
        int dir, ph; K pk;
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            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))
                    return q;
            }
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = 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);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

putTreeVal方法通过比较hash值来在二叉树中检索该key在二叉树上的位置，如果发现hash值相同且两个key通过比较发现是相同的，则返回原有的节点，如果key是不能比较的，则使用find方法。如果发现该key在二叉树上没有，则新建一个节点放在对应的位置上，随后调用balanceInsertion方法和moveRootToFront方法来调整二叉树。

HashMap中处理插入后平衡二叉树的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> 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)
            return root;
        if (xp == (xppl = xpp.left)) {
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.right) {
                    root = rotateLeft(root, x = xp);
                    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 (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);
                    }
                }
            }
        }
    }
}

其中root是二叉树的根节点，x是本次插入二叉树的节点，xp是x的父节点，xpp是xp的父节点，xppl是xpp的左孩子，xppr是xpp的右孩子。

  1. 初始化x为红色。
  2. 如果x没有父节点，则说明x是根节点，将x变为黑色后返回直接返回。
  3. 若x的父节点xp为黑色或者没有父节点，则说明该红黑树符合规则，返回根节点。
  4. 如果xp是xpp的左孩子，则到5，否则到。
  5. 若xppr存在且为红色(x可以是xp的左孩子或右孩子)，则经过变色操作后将x的指针指向xpp然后回到2

  1. 若xppr为null且x是xp的右孩子，在经过左旋转、变色、右旋转后在下一次循环中返回根节点

    如果xppr存在但为黑色，但我们已知xppl原右孩子为nulll，x是后来插入的，那么在x插入前xpp倒xp的右边的叶子节点所经过的黑色节点的数量不等于xpp到xppr的叶子节点所经过的黑色节点的个数

  1. 若xppr为null且x是xp的左孩子(同理xppr不可能存在且为黑色)，在经过变色和右旋转后在下一次循环返回根节点

  2. 如果xp是xpp的右孩子那刚好跟5、6、7步镜像翻转。

4.4.2. 删除

HashMap中在二叉树中删除节点的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
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;
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    if (pred == null)
        tab[index] = first = succ;
    else
        pred.next = succ;
    if (succ != null)
        succ.prev = pred;
    if (first == null)
        return;
    if (root.parent != null)
        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;
    if (pl != null && pr != null) {
        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
        TreeNode<K,V> sr = s.right;
        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;
    if (replacement != p) {
        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;
    }

    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);
}

上面的moveable参数在HashMap永远为true，是在CurrentHashMap中才会用到。

处理步骤如下：

  1. 在双向链表中删除该节点

  2. 对二叉树进行调整(假设要删除p)

  3. 如果p的左右孩子存在，将p和以它的右孩子为根节点的森林中key值(hash值或key实现comparable接口后的比较值)最小的节点调换位置和颜色。

  4. 若sr为null，则replacement为p，否则replacement为sr

  5. 如果p的右孩子为null，则replacement为pl

  6. 如果p的左孩子为null，则replacement为pr

  7. 如果p的左右孩子为null，则replacement为p

  8. 如果replacement不为p，则先用repalcement代替原来p在二叉树中的位置，随后消除p在二叉树中的各种指针，即p.parent.left、p.parent.right、p.left、p.right、p.parent等。

  9. 如果p是红色节点，那删了就删了，如果不是，则调用balanceDeletion(root, replacement)方法调整二叉树。

  10. 如果replacement为p则消除p在二叉树中的各种指针，即p.parent.left、p.parent.right、p.left、p.right、p.parent等。

总而言之，由于第3步中调整位置和颜色的步骤存在所以在第8步中，当时二叉树存在以下六种情况(忽略左右孩子的区别)

前四种为p的左右孩子有且只有一个不为null。但是，根据红黑树规则，情况①和情况③并不符合任意节点(节点p)到所有叶子节点的路径上黑色节点的数量相同。因为p到左边的叶子所经过的黑节点至少比到replacement下的叶子节点少1。

后两种为p的左右孩子为空。如果是情况⑥，那么删了后依然满足红黑树的规则，如果是⑤，就要通过旋转和变色来使得红黑树满足规则。

HashMap中处理删除后平衡二叉树的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                           TreeNode<K,V> x) {
    for (TreeNode<K,V> xp, xpl, xpr;;) {
        if (x == null || x == root)
            return root;
        else if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        else if (x.red) {
            x.red = false;
            return root;
        }
        else if ((xpl = xp.left) == x) {
            if ((xpr = xp.right) != null && xpr.red) {
                xpr.red = false;
                xp.red = true;
                root = rotateLeft(root, xp);
                xpr = (xp = x.parent) == null ? null : xp.right;
            }
            if (xpr == null)
                x = xp;
            else {
                TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                if ((sr == null || !sr.red) &&
                    (sl == null || !sl.red)) {
                    xpr.red = true;
                    x = xp;
                }
                else {
                    if (sr == null || !sr.red) {
                        if (sl != null)
                            sl.red = false;
                        xpr.red = true;
                        root = rotateRight(root, xpr);
                        xpr = (xp = x.parent) == null ?
                            null : xp.right;
                    }
                    if (xpr != null) {
                        xpr.red = (xp == null) ? false : xp.red;
                        if ((sr = xpr.right) != null)
                            sr.red = false;
                    }
                    if (xp != null) {
                        xp.red = false;
                        root = rotateLeft(root, xp);
                    }
                    x = root;
                }
            }
        }
        else { // symmetric
            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就是上一个算法中的replacement，算法步骤如下：

  1. 若替换用的x节点是根节点，则说明被删除的p节点原来就是根节点，只需将x变成黑色(如果本来就是黑色则不用换)，二叉树就满足红黑树的规则(①根节点是黑色，②任意节点到任意叶子节点经过的黑色节点数不变)。

  2. 当x不是根节点时，有以下六种情形：

    绿色空心节点代表节点有可能为红色或黑色

  3. 当二叉树为情况①，那么只要把x变成黑色即可，因为如果x是红色，那么被删除的p必为黑色，则删除后，root到leafA的路径上的黑色节点个数减一，不再等于到leafB的路径上的黑色节点个数，需要把x变成黑色来满足红黑树条件。

若二叉树为情况②~⑥就比较复杂，首先因为x是由removeTreeNode方法传进来的，由于被删除的p节点在移动位置后左右孩子必有一个为空，所以如果是传进来的x不是被删除的节点本身而是替换的节点，那么必定为红色。相反，如果为黑色，则x必定是被删除的节点且x左右孩子必为空。而且，如果x是黑色节点，则说明二叉树要删除某一个黑色节点。删除一个黑色节点必然会使得原来经过该节点得路径上得黑色节点数减一(这不废话吗)，使得与其他路径不等，假设根节点(或者x上的所有父辈)r到所有叶子节点的路径上黑色节点数量为N，那么就通过变色和旋转来试图使其保持为N，或者令所有路径的黑色节点数量变为N-1。

  1. 当二叉树为情况②时，通过变色和旋转使其变为③~⑥情况。

  1. 当二叉树为情况③时，无法使得路径上的黑色节点数量保存不变，于是将路径上的黑色节点数调整为N-1，然后将xp变为x再次进入循环。

  1. 当二叉树为情况④时，先通过变色旋转转换成⑤~⑥情况，随后通过变色旋转是路径上的黑色节点数量保持为N。

  2. 当二叉树为情况⑤或情况⑥，通过变色旋转使路径上的黑色节点数量保持为N。

5. LinkedHashMap

LinkedHashMap继承于HashMap，主要是实现了有序的HashMap。在原HashMap中，使用迭代器对条目进行迭代的顺序并不遵循插入或访问顺序。因为在插入进HashMap后就失去了插入和访问的先后信息。

LinkedHashMap的Entry节点继承自原来HashMap中的Node节点，增加了before和after变量来记录插入或者访问的先后顺序。

在构造方法中通过指定accessOrder来指定是否需要因为访问而更新顺序。如果为false，则是插入顺序，后插入的在后。如果为true，则是访问顺序(插入的时候当作访问了一次)，后访问的在后。