首页 JDK 源码

# 要思考的问题

  • HashMap 的底层数据结构 (节点结构，这种结构有什么优点)
  • 如何处理 hash 冲突
  • 怎么扩容？扩展机制是什么？
  • 增删改查过程
  • 链表到红黑树的转换过程，反之？
  • 红黑树相关 (见另一篇数据结构之红黑树)
  • hash 计算

# 达到的目标

# 看之前要掌握的知识点

# 红黑树

# 看之前大体了解的知识点

# hash 算法

# Poisson 分布

poisson 分布

# 开始

# HashMap 的继承体系

HashMap01-继承体系.png

  • AbstractMap: map 的抽象类，以最大限度的减少实现 Map 接口的类的工作量。

# hashMap 结构

# 字段解释

# 常量字段 (默认值字段)

  • DEFAULT_INITIAL_CAPACITY=1<<4: 默认的初始容量，默认是为 16, 必须是 2 的 n 次方。为什么呢？见扩容的方法。
  • DEFAULT_LOAD_FACTOR=0.75f: 默认的负载因子。它和哈希表的容量的乘积是决定是否重新 hash 的阈值。
  • TREEIFY_THRESHOLD=8: 使用树而不是链表的计数阈值。当桶的元素添加到具有至少这么多节点时，桶被转换为树。
  • UNTREEIFY_THRESHOLD=6: 用于在调整大小操作期间解除（拆分）桶的桶计数阈值。(untreeifying 不是一个英语单词，这里的以是非树化，即转换成普通列表的过程). 也就是说从树转换成普通的桶 (链表) 的阈值。
  • MAXIMUM_CAPACITY=1<<30: 最大的容量: 1<<30 ，如果具有参数的任一构造函数隐式指定更高的值，则使用此参数。必须是 2 的 n 次方，小于等于 1<<30
  • MIN_TREEIFY_CAPACITY=64: 容器可以树化的最小容量 (否则，如果 bin 中的节点太多，则会调整表的大小.) 应该至少为 4 * TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突.

# 类属性

  • table: transient HashMap.Node<K,V>[] table ; table 在首次使用时初始化，并根据需要调整大小。分配时，长度始终是 2 的幂。(我们还在一些操作中容忍长度为零，以允许当前不需要的自举机制)
  • entrySet: transient Set<Map.Entry<K,V>> entrySet ; 保存缓存的 entrySet.
  • size: transient int size ; map 中元素的数量。结构修改是那些改变 HashMap 中映射数量或以其他方式修改其内部结构（例如，rehash）的修改。此字段用于在 HashMap 的 Collection-views 上快速生成迭代器 (见 ConcurrentModificationException)

注意：这些字段都是 transient 的？为什么呢？

  • loadFactor: final float loadFactor; hash 表的负载因子，在实例化 hashTable 的时候指定，该对象内不能变更 (final);
  • threshold: int threshold; , 下一次调整容器大小的阈值. threshold=capacity * load factor

# HashMap 的两种节点

  • 基本的哈希桶的节点 (链表的结点) Node

static class Node<K,V> implements Map.Entry<K,V> 它继承了 Map 的 Entry, 是对子类的行为规范。要求提供了 getKey (),getValue () 等常用方法。

链表节点的结构如下:

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
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 避免重复计算key的hash值
    final K key;
    V value;
    // 指向下一个节点的指针
    HashMap.Node<K,V> next;

    Node(int hash, K key, V value, HashMap.Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    @Override
    public final K getKey()        { return key; }
    @Override
    public final V getValue()      { return value; }
    @Override
    public final String toString() { return key + "=" + value; }

    // todo 没有找到在哪里使用了这个方法
    @Override
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    @Override
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
  • Tree 的节点 TreeNode

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> 继承了其子类的 Entry, 子类的 Entry 继承了父类的 Node. 注意了，这里乍一看还挺乱。来张图吧。
hashMap的节点的继承图.png

这里呢，TreeNode 其实是 Node 的孙子，也就是说 HashMap 的树节点是链表节点的孙子辈儿的。
为什么要使两种节点有继承关系呢？为什么 TreeNode 不直接继承 Node 节点呢？

1
2
3
4
5
6
7
8
9
10
11
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    HashMap.TreeNode<K,V> parent;  // red-black tree links
    HashMap.TreeNode<K,V> left;
    HashMap.TreeNode<K,V> right;
    HashMap.TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, HashMap.Node<K,V> next) {
        super(hash, key, val, next);
    }
    // 省略其他代码
}

# HashMap 增加方法 HashMap#put ()

1
2
3
4
5
6
7
8
9
10
/**
*  将指定的value和key关联在map中。
*  如果map中已经存在了key,那么将会替换掉老的value。
* @param key key 指定的key
* @param value value 和指定key关联的value
* @return 如果返回了value，就说明map中原来和key关联是有值的。如果返回null就说明没有value。
*/
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

这里就比较有看点了，1. 这里是 hashMap 的增加方法，增加方法里必然会遇到 hash 冲突的问题，我们等会看下 hash 冲突是如何处理的，还会涉及到扩容的问题，我们也要来看看他是怎么扩容的，扩容的过程中还会遇到普通的桶转换成树的过程。我们先来看下 hash 值是怎么计算出来的。

  • hash 值的计算
1
2
3
4
5
6
7
8
9
/**
 * 计算key的hashCode并且和hashCode值高16位进行异或运算。(异或: 相同为0，不同为1)
 * 混和低位和高位，就是为了加大低位的随机性,而且混合后的低位掺杂了高位的部分特征,
 * 这样高位的信息也被变相的保留了下来。
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么这么做呢？见 HashMap 的 Hash 函数到底有什么意义

  • 那我们接下接着看 putVal() 方法。
{.line-numbers}
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
/**
 * 实现Map.put相关的方法。
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 *                     如果是true的,不会修改存在的值。返回老的值。
 * @param evict if false, the table is in creation mode.
 *              如果为false的时候,表属于创建模式,第一次新增元素的时候。
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {

    HashMap.Node<K,V>[] tab;
    HashMap.Node<K,V> p;
    int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        // 如果数组为null,或者数组长度为0的时候，数组需要调整大小。
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 定位到数组的桶为null的时候,创建桶内的第一个元素。next=null;
        tab[i] = newNode(hash, key, value, null);
    else {
        // 如果桶不为null，则创建链表
        HashMap.Node<K,V> e; K k;
        // p表示当前桶的第一个元素。
        // 如果新增的元素和第一个元素相等的话(出现hash冲突),暂存已经存在的元素到变量e中。
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof HashMap.TreeNode)
            // 如果是树节点。
            e = ((HashMap.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)
                        // 如果桶内的元素数量达到树化的阈值,将链表转换成树。
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    // 如果第一个元素和要新增的元素hash,key都相等的话,直接进行新增操作。
                    break;
                p = e;
            }
        }

        if (e != null) { // existing mapping for key
            // 如果原来的元素不为空,保留原来的值。
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                // 覆盖掉原来的value;
                e.value = value;
            // 留一个无方法体的方法，供子类扩展
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // failFast计数
    ++modCount;
    if (++size > threshold)
        // 如果table中的桶的数量超过了阈值。扩容。
        resize();
    // 供子类扩展的方法。
    afterNodeInsertion(evict);
    return null;
}

这段代码里中有三处重要的地方， resize() , treeifyBin() , putTreeNode() , 接下来我们依次看下这三个方法。

# resize

{.line-numbers}
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/**
 * 初始化，或者加倍表格的大小
 * 如果为null时候，根据字段threshold的初始容量进行分配
 * 否则，因为我们正在使用二次幂扩展，所以每个bin中的元素必须保持相同的索引，或者在新表中以两个偏移的幂移动
 *
 * @return the table 新的表
 */
final HashMap.Node<K, V>[] resize() {
    HashMap.Node<K, V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 如果旧表的大小大于0
        if (oldCap >= MAXIMUM_CAPACITY) {
            // hash表达到最大容量
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY) {
            // 如果翻倍后旧表大小<最大表长度，并且旧表长度>默认初始化长度。
            // 扩容的阈值也翻倍。 还是等级 table.length*loadFactor
            newThr = oldThr << 1; // double threshold
        }
    } else if (oldThr > 0) { // initial capacity was placed in threshold
        // 旧表长度<=0,旧的threshold>0,
        // 就把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) {
        // 如果新的扩缩容阈值等于0,设置新的扩缩容阈值为新的容量*负载因子.
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                (int) ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

    // 重新创建新的hash表
    @SuppressWarnings({"rawtypes", "unchecked"})
    HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
    table = newTab;
    // 如果旧表不为空,进行扩容.
    // 否则(旧表为空)就进行初始化过程.
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            HashMap.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 HashMap.TreeNode) {
                    // 如果当前桶是棵红黑树
                    ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                } else { // preserve order
                    // 桶是链表,将该桶内的元素重新分配到表中。

                    HashMap.Node<K, V> loHead = null, loTail = null;
                    HashMap.Node<K, V> hiHead = null, hiTail = null;
                    HashMap.Node<K, V> next;

                    // 遍历桶内的元素，将元素重新分配到hash表内的各个桶中。
                    // 具体的实现过程是: 将当前的元素的hash值和容量取&,如果>0,那就说明该元素应该分配到新的桶内。
                    // 桶的位置就是: oldCap+j.即桶原来容器+该元素所在的桶的下标。(hiHead所标识的位置)
                    // 反之如果hash值是==0的,那么该元素就应该还在当前桶内。(loHead所标识的位置)
                    // 这里所说的位置都是指桶的下标,整个表都是新的了,位置肯定都变了。
                    // 为什么可以这么实现呢？
                    // 因为扩容的时候，使用的是原来容量的2倍进行扩容的。所以就可以使用(oldCap+j)的方式来确定元素的新位置了。
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            // 还在原桶中
                            if (loTail == null)
                                loHead = e;
                            else {
                                // 位置最后一个节点为空,使用e=next的时候，next为null的情况。
                                // 在桶内元素遍历完成后,会把桶的最后一个元素的next置为null。
                                loTail.next = e;
                            }
                            loTail = e;
                        } else {
                            // 放置到新的桶内。
                            if (hiTail == null)
                                hiHead = e;
                            else {
                                // 位置最后一个节点为空,使用e=next的时候，next为null的情况。
                                // 在桶内元素遍历完成后,会把桶的最后一个元素的next置为null。
                                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;
}

看一个散列还算非常均匀的例子来看扩容过程。

hashMap04-Put方法过程01.png

那么进行扩容的过程是怎么样的呢？

hashMap05-resize方法01.png

以元素 1 和 12 为例，看扩容过程:
元素 1 的 hash 值为 49.(以 hashMap 计算 hash 值的方式得出。)， 与 15 取 & 计算桶的下标为 1, 扩容后，与 31 取 &, 计算桶的下标为 17. 所以扩容前位置是 0，扩容后元素 1 的存放位置是 17。
代码中是怎么完成这个过程的呢？
和扩容前 hash 表的容量取 &, 得 49 & 16 = 16 > 0 (代码第 86-96 行), 新的桶的头节点 (对应代码里的 hiHead) 就是当前节点 1，尾节点 (hiTail) 赋为当前节点。然后进行下一次 do...while 循环，处理节点 12, 计算出节点 12 的 hash 值为 1569 , 进行计算 1569 & 16 = 0 == 0 原来桶的头结点是节点 12, 尾节点也是节点 12 (对应着代码第 76-86 行), 这样 hitail 和 loTail 均不为 null, 所以然后直接使用 newTab[j] = loHead; 和 newTab[j + oldCap] = hiHead; 的方式确定桶的位置。这个案例里，处理完节点 12 才会确定桶的位置。因为原来的表中下标为 1 的桶中有两个元素 1 和 12. 那桶里只有一个元素的怎么处理的呢？ newTab[e.hash & (newCap - 1)] = e; e 是当前节点，newCap 是新表的容量。

如果你想问为什么能使用 hash & olcCap==0? 来决定是 newTab[j] 还是 newTab[j+oldCap] 这种方式来确定新的桶的下标的话。 那么原因就是扩容使用的是 2 次幂的方式，容量是原来容量的 2 倍。所以就可以使用 hash & olcCap==0? 来判断了。

这个例子呢，演示了扩容过程中的链表的新增和扩容过程。再回头看 resize 方法，还有一种情况我们没有分析过。那就是

1
2
3
4
5
6
...
else if (e instanceof HashMap.TreeNode) {
    // 如果当前桶是棵红黑树
    ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
}
...
{.line-numbers}
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
/**
    * 将原来树桶中的节点拆分为更低或更高的树桶,如果太小的话就转化成链表
    * 只被resize方法调用
    *
    * @param map   hash表
    * @param tab   表中的指定的桶的头结点(桶是一个棵树)
    * @param index 要拆分的hash表的节点
    * @param bit   the bit of hash to split on 要分裂的hash位
    */
final void split(HashMap<K, V> map, HashMap.Node<K, V>[] tab, int index, int bit) {
    HashMap.TreeNode<K, V> b = this;
    // Relink into lo and hi lists, preserving order
    HashMap.TreeNode<K, V> loHead = null, loTail = null;
    HashMap.TreeNode<K, V> hiHead = null, hiTail = null;
    // lc代表的是原来的桶的元素的数量
    // hc代表新的桶中的元素的数量, 用来和UNTREEIFY_THRESHOLD比较决定是否要转换结构.
    int lc = 0, hc = 0;
    // 这里还是当做链表去处理，把桶内的元素重新散列。
    for (HashMap.TreeNode<K, V> e = b, next; e != null; e = next) {
        next = (HashMap.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;
        }
    }
    //  散列完后，判断原来的桶(lo)和新的桶中的元素个数
    //  然后决定转换为树还是链表
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                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);
        }
    }
}

将树重新穿换成链表的过程就比较简单了：

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
    * Returns a list of non-TreeNodes replacing those linked from
    * this node.
    */
final HashMap.Node<K, V> untreeify(HashMap<K, V> map) {
    HashMap.Node<K, V> hd = null, tl = null;
    for (HashMap.Node<K, V> q = this; q != null; q = q.next) {
        // replacementNode:将TreeNode转成Node
        HashMap.Node<K, V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

这里就是和红黑树相关的内容了，这里关键的是 split 调用了一个 treeify 的方法。这个方法同时也被 treeifyBin 调用了。所以 treeify 方法就和 treeifyBin 方法一块分享。
顺便提一嘴，他们有如下的关系:

hashMap06-红黑树相关方法调用关系.png
其中蓝色的是红黑树的方法，黄色的是 HashMap 调用的方法。

# treeifyBin

{.line-numbers}
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
/**
* 将链表转换成树。
* 替换给定hash值的索引处的桶的所有节点，如果表太小(table.length小于64),就调整大小.这里其实是对hash表的一种优化,防止因为表长度太小而转换成树,造成性能浪费
* @param hash 用于确定桶的位置。
*/
final void treeifyBin(HashMap.Node<K, V>[] tab, int hash) {
    int n, index;
    // 链表的节点
    HashMap.Node<K, V> e;
    // 如果hash表为空或者hash表的长度小于最小化的树化容量(64)，这时会重调整大小。
    // 将容量扩大为原来的两倍。
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
        resize();
    } else if ((e = tab[index = (n - 1) & hash]) != null) {
        `HashMap.TreeNode<K, V> hd = null, tl = null;
        do {
            // 构建一个树的节点。
            HashMap.TreeNode<K, V> p = replacementTreeNode(e, null);
            // 如果尾为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);
        }`
    }
}

其实呢，这个 treeifyBin 方法还是做了一些将桶树化的前置操作，然后将装有 TreeNode 节点的桶交给了 treeify 方法去真正的转换为一棵红黑树。那我们接下来看下 treeify 方法。注意这个方法定义在 HashMap.TreeNode#treeify()

# treeify () 方法
{.line-numbers}
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
/**
 * Forms tree of the nodes linked from this node.
 * 把该节点连接的所有节点组成一棵树。(树化的过程)
 */
final void treeify(HashMap.Node<K, V>[] tab) {
    // 该棵树的根节点。
    HashMap.TreeNode<K, V> root = null;
    // x是遍历的每个节点。
    for (HashMap.TreeNode<K, V> x = this, next; x != null; x = next) {
        // 存下下一个节点。(指向下一个节点的指针)
        next = (HashMap.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 (HashMap.TreeNode<K, V> p = root; ; ) {
                // dir,负值和0为左子树，正值为右子树。
                int dir, ph;
                K pk = p.key;

                /*************判断节点在左子树还是右子树 -start***************/
                // h为当前节点的hash值。
                // p是父节点, ph是父节点的hash值。
                if ((ph = p.hash) > h) {
                    // 放在左子树
                    dir = -1;
                } else if (ph < h) {
                    // 放在又子树
                    dir = 1;
                }
                //如果当前节点和父节点的hash值相等:
                //如果节点的key实现了Comparable, 或者 父节点和当前节点的key为一个。
                else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                        (dir = compareComparables(kc, k, pk)) == 0) {
                    // k是当前节点的key，pk是父节点的key
                    // 根据hashMap定义的规则,判断当前节点应该位于左子树还是右子树。
                    dir = tieBreakOrder(k, pk);
                }
                /*************判断节点在左子树还是右子树 -end***************/

                HashMap.TreeNode<K, V> xp = p;
                // p==null,代表着遍历到了叶子节点。
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // xp是当前节点的父节点。
                    x.parent = xp;
                    if (dir <= 0){
                        xp.left = x;
                    } else {
                        xp.right = x;
                    }
                    // 平衡插入的红黑树(完成插入后，红黑树的性质可能被破坏,这里进行重新平衡)
                    root = balanceInsertion(root, x);
                    break;
                }
            }

        }
    }
    //确保红黑树的根节点是桶的第一个节点。
    moveRootToFront(tab, root);
}

在这里呢，有 3 个方法没有仔细去说明，分别是 tieBreakOrder (),balanceInsertion () 和 moveRootToFront (tab, root), 注意，这三个方法在下面的 PutTreeVal 中也有调用。当然包括调整平衡的左旋 (rotateLeft), 右旋 (rotateRight) 方法。我们接着往下看吧。

# balanceInsertion 方法

在说这个方法之前，先总结下红黑树变换的 5 条规则。

  • 规则 1: 红黑树为空树 ==> {直接插入当前节点，节点涂为黑色。}
  • 规则 2: 插入节点的父节点是黑色 ==> {直接插入当前节点.}
  • 规则 3: 当前节点的父节点是红色，并且叔叔节点是红色。==> {父节点涂黑，叔叔节点涂黑，祖父节点涂红.}
  • 规则 4: 当前节点的父节点是红色，叔叔是黑色，当前节点是父节点的右子树. ==> {当前节点的父节点作为新的当前节点，以新的当前节点左旋。}
  • 规则 5: 当前节点的父节点是红色，叔叔节点是黑色，当前节点是父节点的左子树. ==> {父节点变为黑色，祖父节点变为红色，以祖父节点为支点右旋.}
    下面结合代码看 HashMap 是怎么实现上面这个 5 个规则的:
{.line-numbers}
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
94
95
96
/**
 * 调整红黑树
 * @param root 根节点
 * @param x 当前节点
 */
static <K, V> HashMap.TreeNode<K, V> balanceInsertion(HashMap.TreeNode<K, V> root,
                                                        HashMap.TreeNode<K, V> x) {
    x.red = true;
    // xp: 当前节点的父节点(父节点)
    // xpp: 当前节点的父节点的父节点(祖父节点)
    // xppl: 当前节点的父节点的父节点的左子树(叔叔节点)
    // xppr: 当前节点的父节点的父节点的右子树(叔叔节点)
    for (HashMap.TreeNode<K, V> xp, xpp, xppl, xppr; ; ) {
        // 规则1
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // 父节点为黑色 或者祖父节点为空==>规则2
        else if (!xp.red || (xpp = xp.parent) == null) {
            return root;
        }

        // 父节点是左子树
        if (xp == (xppl = xpp.left)) {
            // 父节点是左子树,且祖父节点存在右子树(叔叔节点为右子树)，并且叔叔为红色。 ==> 父节点是右子树时的性质1.
            if ((xppr = xpp.right) != null && xppr.red) {
                // 叔叔节点涂黑
                xppr.red = false;
                // 父节点涂黑
                xp.red = false;
                // 祖父节点涂红
                xpp.red = true;
                // 以祖父节点为新的当前节点
                x = xpp;
            }
            // 祖父节点没有右子树或者有右子树,颜色为黑色。
            else {
                // 当前节点是父节点的右子树==> 规则4
                if (x == xp.right) {
                    // 左旋
                    root = rotateLeft(root, x = xp);
                    // 设置祖父节点要么为空要么是父节点。
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // 规则5
                if (xp != null) {
                    // 父节点涂成黑色
                    // 此时xp可能为root.
                    xp.red = false;
                    // 如果xp不是root的时候。
                    if (xpp != null) {
                        // 祖父节点涂成红色,右旋。
                        xpp.red = true;
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }

        // 父节点不是左子树==> 父节点是右子树。
        else {
            // 叔叔节点(祖父节点的左子树),叔叔为红色 ==> 规则3
            if (xppl != null && xppl.red) {
                    // 叔叔涂黑
                xppl.red = false;
                // 父节点涂黑
                xp.red = false;
                // 祖父节点涂红
                xpp.red = true;
                // 以祖父节点为新的当前节点
                x = xpp;
            }
            // 祖父节点没有右子树或者有右子树,颜色为黑色。 ==> 规则4
            else {
                // 当前节点是左子树
                if (x == xp.left) {
                    // 右旋
                    root = rotateRight(root, x = xp);
                    // 设置祖父节点要么为空要么是父节点。
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // ==> 规则5
                if (xp != null) {
                    xp.red = false;
                    // 如果有祖父
                    if (xpp != null) {
                        // 祖父节点涂成红色,右旋。
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}
# rotateLeft 左旋

这里的代码不能用语言描述，真的是只能意会不能言传啊。

{.line-numbers}
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
static <K, V> HashMap.TreeNode<K, V> rotateLeft2(HashMap.TreeNode<K, V> root, HashMap.TreeNode<K, V> p) {
            HashMap.TreeNode<K, V> r, pp, rl;
            // p是父节点
    if (p != null && p.right != null) {
        // 右孩子
        r = p.right;
        // 右孩子有左孩子的话.
        if (r.left != null) {
            // 右孩子变成右孩子的左孩子。即rl变成了p的右孩子。
            p.right = r.left;
            rl = r.left;
            rl.parent = p;
            // 注意此时r没有关联。
        }
        pp = p.parent;
        // 如果p没有有父节点的话。
        if (p.parent == null) {
            // 将r的父节点置为null
            r.parent = p.parent;
            // 颜色涂成黑色，并且r就是根节点。
            (root = r).red = false;
        }
        //  如果p节点有父节点，并且p是左子树的话
        else if (pp.left == p) {
            // 将祖父节点的左子树置为r,
            pp.left = r;
        } else {
            // 将祖父节点的右子树置为r,
            pp.right = r;
        }
        // 将r和p连接起来。
        r.left = p;
        p.parent = r;
    }
    return root;
}

注意下，这里的代码是我修改之后，JDK 的源码看起来很精简，理解起来，啧啧啧。

MD, 来张图:

HashMap07-左旋的过程.md

这里假设右孩子是有左孩子的。如果没有的话，那就直接去掉绿色的 rl 就好了。

# rotateRight

右旋的过程同理:

{,.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static <K, V> HashMap.TreeNode<K, V> rotateRight(HashMap.TreeNode<K, V> root,
                                                         HashMap.TreeNode<K, V> p) {
    HashMap.TreeNode<K, V> l, pp, lr;
    if (p != null && (l = p.left) != null) {
        if ((lr = p.left = l.right) != null)
            lr.parent = p;
        if ((pp = l.parent = p.parent) == null)
            (root = l).red = false;
        else if (pp.right == p)
            pp.right = l;
        else
            pp.left = l;
        l.right = p;
        p.parent = l;
    }
    return root;
}

这图啊，有空再做吧。今天太累了。

还有一个方法:

# moveRootToFront
{.line-numbers}
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
 /**
  * Ensures that the given root is the first node of its bin.
  * // 确保红黑树的根节点是桶的第一个节点。
  * 为什么不直接将tab[index]==root? 是为了树重新转换成链表的时候使用的。
  */
static <K, V> void moveRootToFront(HashMap.Node<K, V>[] tab, HashMap.TreeNode<K, V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        int index = (n - 1) & root.hash;
        HashMap.TreeNode<K, V> first = (HashMap.TreeNode<K, V>) tab[index];
        // 判断第一个节点和root是不是相等的,判断的是地址。
        if (root != first) {
            HashMap.Node<K, V> rn;
            tab[index] = root;
            HashMap.TreeNode<K, V> rp = root.prev;

            if ((rn = root.next) != null) {
                // root的后一个节点的指向前的指针指向root的前一个节点。
                ((HashMap.TreeNode<K, V>) rn).prev = rp;
            }

            if (rp != null) {
                // root的前一个节点的指向后的指针指向root的后一个节点。
                rp.next = rn;
            }

            if (first != null) {
                // 第一个元素的前指针指向root
                first.prev = root;
            }
            // root的后向指针指向first
            root.next = first;
            // root的前向指针置为null
            root.prev = null;
        }
        // 递归不变检查
        assert checkInvariants(root);
    }
}

# putTreeNode

{./line-bumbers}
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
final HashMap.TreeNode<K, V> putTreeVal(HashMap<K, V> map, HashMap.Node<K, V>[] tab,
                                                int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    HashMap.TreeNode<K, V> root = (parent != null) ? root() : this;
    for (HashMap.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) {
                HashMap.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);
        }

        /***************判断 左右子树 end******************/

        HashMap.TreeNode<K, V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            HashMap.Node<K, V> xpn = xp.next;
            HashMap.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)
                ((HashMap.TreeNode<K, V>) xpn).prev = x;
            // 这里比较重要了，不过我们在treeify中已经说过了。
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

这样，HashMap 的新增过程我们就处理完了。

# HashMap 删除方法 HashMap#remove ()

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
/**
 * 从map中删除指定的key,如果key存在的话
 * @param key key whose mapping is to be removed from the map
 * @return value 如果key存在,返回key对应的Value,如果不存在返回null
 */
public V remove(Object key) {
    HashMap.Node<K, V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
}

其中计算 hash 值的方法还是和之前的一样。

# removeNode

{.line-numbers}
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
/**
 * Implements Map.remove and related methods.
 * 实现Map.remove相关的方法
 * @param hash       hashCode
 * @param key       key
 * @param value     value
 * @param matchValue 如果是true，仅在value相等的时候删除。
 * @param movable   如果为false，则在删除节点的时候不移动其他节点。
 * @return 返回删除的节点
 */
final HashMap.Node<K, V> removeNode(int hash, Object key, Object value,
                                    boolean matchValue, boolean movable) {
    HashMap.Node<K, V>[] tab;
    HashMap.Node<K, V> p;
    int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
        HashMap.Node<K, V> node = null, e;
        K k;
        V v;
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof HashMap.TreeNode) {
                // 找到红黑树中的节点
                node = ((HashMap.TreeNode<K, V>) p).getTreeNode(hash, key);
            } else {
                // 删除链表中的节点1: 查找到节点的位置。
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key ||
                                    (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 真正的去删除的过程。
        if (node != null && (!matchValue || (v = node.value) == value ||
                (value != null && value.equals(v)))) {
            if (node instanceof HashMap.TreeNode) {
                // 删除红黑树的节点
                ((HashMap.TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
            }else if (node == p) {
                // 桶中只有当前的节点。
                tab[index] = node.next;
            }else {
                // 链表中节点的删除
                p.next = node.next;
            }
            // 修改次数+1
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

还有一个最难理解的方法落在了红黑树的移除上了。

# HashMap#TreeNode#removeTreeNode

还是先看下红黑树的删除是怎么回事。

在删除方法调用之前必须要有存在的给定节点。
这比典型的红黑删除代码更混乱，因为我们不能将内部节点的内容与叶子后继交换，后者由遍历期间可独立访问的 “下一个” 指针固定。 所以我们交换树链接。 如果当前树似乎有太少的节点，则红黑树 (bin) 将转换回普通的链表 (普通 bin). （测试会在 2 到 6 个节点之间触发，具体取决于树结构）。
上面是 removeTreeNode 方法的解释。说实话，没理解…

HashMap 的删除不同于普通的红黑树的删除，因为它其中还维护了，一个链表的指向. HashMap 采用的是将树中的两个节点进行换位，颜色也要进行互换，来保证红黑树的平衡，并不改变二者在链表中的位置，互换后，删除节点此时的左子树是空的，将问题转换成了对左子树为空的节点的删除。

有一个简单的问题，千万不要弄混了，就是 TreeNode 中要删除的节点是谁？？

删除的签名是这样的: final void removeTreeNode(HashMap<K, V> map, HashMap.Node<K, V>[] tab,boolean movable) , 并没有传 TreeNode 啊？是不是？？

干吗呢！大兄嘚。要删除的节点是：this 啊。我们现在走到了 TreeNode 内部了！！它本身就是要被删除的节点啊。

好了，那我现在要告诉你：删除自己！

HashMap 删除红黑树的节点，实际上就是 TreeNode 自己删除自己。那么它是怎么删的呢？

它分成了三步:

  • 1. 将删除节点从双链向链表中删除.
  • 2. 将删除节点与其右子树最小节点互换，之后平衡树
  • 3. 将树根节点，移动到 tab[index] 指针处
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
final void removeTreeNode(HashMap<K, V> map, HashMap.Node<K, V>[] tab,
                                  boolean movable) {
        // 注意了： 这个时候被删除的节点是谁??
        // 是this.
        int n;
        if (tab == null || (n = tab.length) == 0)
            return;

        // 找到对应的索引(确定对应桶的位置), n 是当前表的长度
        int index = (n - 1) & hash;
        // first: 第一个树节点(当前为父节点),root，父节点。rl:
        HashMap.TreeNode<K, V> first = (HashMap.TreeNode<K, V>) tab[index], root = first, rl;
        // succ:下一个节点(链表的指向)。pred, 前一个节点。
        HashMap.TreeNode<K, V> succ = (HashMap.TreeNode<K, V>) next, pred = prev;

        if (pred == null) {
            // 前一个为空时，即当前接是父节点:(被删除的节点是根节点)
            tab[index] = first = succ;
        } else {
            // 否测,前一个节点的下一个执行当前节点的下一个。(意会)
            pred.next = succ;
        }

        if (succ != null) {
            // 当前节点的后节点不为null,后一个节点的前节点指向当前节点的前节点(意会)
            succ.prev = pred;
        }

        if (first == null) {
            // 如果删除当前节点，该桶变成了null的。就直接返回
            return;
        }

        if (root.parent != null) {
            // 重置table[index]处为树的根节点。
            root = root.root();
        }

        // PS: 说点没用， JDK除了部分ifelse不加括号之外，
        // 其实换行，还是用的挺多的，看起来也挺舒服的。
        // 值得借鉴
        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,用来交换的节点。
        HashMap.TreeNode<K, V> p = this, pl = left, pr = right, replacement;
        if (pl != null && pr != null) {

            // s为右子树的最小的节点,sl为左子树(一下五行和源码略有不同)
            HashMap.TreeNode<K, V> s = pr, sl = s.left;
            while (sl != null) { // find successor
                s = sl;
                sl = s.left;
            }

            // 交换颜色
            boolean c = s.red;
            s.red = p.red;
            p.red = c; // swap colors

            // 交换节点连接
            HashMap.TreeNode<K, V> sr = s.right;
            HashMap.TreeNode<K, V> pp = p.parent;
            // pr是当前节点的右孩子节点
            // s是当前节点的右子树的最小的节点
            // p的右子树,只有s这一个节点
            if (s == pr) { // p was s's direct parent
                p.parent = s;
                s.right = p;
            } else { //
                // sp： 最小节点的父节点
                HashMap.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;
            }
            // 置null孩子。
            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) {
            HashMap.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;
        }

        // 是否要进行重平衡树?
        HashMap.TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);

        // 在平衡后删除该节点
        if (replacement == p) {  // detach
            HashMap.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;
            }
        }
        // 参数moveable控制是否删除节点后确保树的根节点为链表的头节点
        if (movable) {
            // 将树根节点，移动到tab[index]指针处
            moveRootToFront(tab, r);
        }
    }

这样呢，整个删除过程就完成了。
用官方中的话，比较混乱。尤其是涉及到红黑树的删除，这部分内容。还是需要好好消化，消化的。

下面我们还剩下两个内容：修改和查找

# HashMap 的查找方法

HashMap 的查找的方法，有 get , getOrDefault . 很明显，这两个方法前者不存在的时候返回的是 null ，后者返回的就是 defaultValue .

先来看下这两个方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 根据指定的key返回映射的Value，当没有包含key的映射时，会返回 null
 * 更正式的情况下： 如果存在一个key(K)的映射 value (V),使得 key==null?K==null:key.equals(K),
 * 如果等式的值为 true, 那么返回V
 * 否则返回 null
 * 不能通过 返回值为null 来判断是否含有<K,V> 映射，因为HashMap允许value为null。
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

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

我们可以看到，它调用的都是同一个方法，顺藤摸瓜，我们看这个 getNode 方法.

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
final HashMap.Node<K, V> getNode(int hash, Object key) {
    HashMap.Node<K, V>[] tab;
    HashMap.Node<K, V> first, e;
    int n;
    K k;
    // 数组不为空，并且对应的桶(bin)不为null
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        // 检查是否为桶内的第一个节点是否满足
        // 为什么要检测第一个节点，直接进入循环或者树节点的检测不行吗?
        // 假设第一个节点是目的节点,可以直接返回，少执行一次if判断，来判断其是树节点还是链表节点。
        // 如果不是第一个节点，循环也会少执行一次,树节点的遍历，也会少遍历一次。
        if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果第一个节点不是要查找的节点
        if ((e = first.next) != null) {
            // 如果是树节点
            if (first instanceof HashMap.TreeNode) {
                return ((HashMap.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;
}

由于 jdk8 之后，有两种类型的节点，我们还说过，这两种节点是 爷孙 的关系.
链表的节点遍历就不用看了，比较简单。我们看下 红黑树的节点的查找:

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 HashMap.TreeNode<K, V> getTreeNode(int h, Object k) {
    // 如果当前节点不是根节点,找到根节点，调用find进行查找,
    // 如果是根节点，调用find进行查找。
    return ((parent != null) ? root() : this).find(h, k, null);
}
/*
* 红黑树的查找，
* 从根节点开始, 直接判断hash值即可。
* 如果hash值，小于当前节点hash值，对其左子树进行遍历。
* 反之，对右子树进行遍历。
* key值相等直接返回.
* 注意: 这里有左右子树为null的情况。
* 对接k和k的类进行比较,判断其要遍历的树为左子树或者右子树。
*/
final HashMap.TreeNode<K, V> find(int h, Object k, Class<?> kc) {
    HashMap.TreeNode<K, V> p = this;
    do {
        int ph, dir;
        K pk;
        HashMap.TreeNode<K, V> pl = p.left, pr = p.right, q;
        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;
        else if ((kc != null ||
                (kc = comparableClassFor(k)) != null) &&
                (dir = compareComparables(kc, k, pk)) != 0) {
            p = (dir < 0) ? pl : pr;
        } else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

这个查找关键因素在于判断对左子树还是右子树进行递归遍历匹配。

以上就是红黑树的查找过程了。

# HashMap 的其他常用方法

这些方法中的实现，我们大部分都分享过了。接下来，我们简单的看下其是如何调用的就好了.

# HashMap.containsKey() 和 HashMap.containsValue()

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
/**
 * 如果Map中包含一个映射关系,则返回true,注意是包含映射关系就会返回ture.
 * hashMap.put("1",null),也会返回true
 */
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

/**
 * 如果存在指定的Value,就会返回true
 */
public boolean containsValue(Object value) {
    HashMap.Node<K, V>[] tab;
    V v;
    // 如果table的长度不为空
    if ((tab = table) != null && size > 0) {
        // 遍历每个bin
        for (int i = 0; i < tab.length; ++i) {
            // 遍历bin下的每个Node
            for (HashMap.Node<K, V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

这里为什么可以通过 .next 的方式去遍历呢？
这个主要是考虑在转换成树节点和树节点的新增的时候。 hashMap 在这两个时刻都对 HashMap 的 next "指针" 进行了维护。所以，在这里就可以明白了，为什么树化节点时候还要维护 .next 了.

# HashMap.size()

HashMap 的 size 函数最简单了，因为 HashMap 内部本来就维护了一个 size 字段，来记录 HashMap 的元素数量.

1
2
3
4
5
6
7
/**
 * 返回HashMap的映射数量
 */
@Override
public int size() {
    return size;
}

# HashMap.isEmpty()

HashMap 的 isEmpty 同样简单，废话少说，看下它的实现

1
2
3
4
5
6
7
/**
 * 如果为映射数量为0的时候，返回true
 */
@Override
public boolean isEmpty() {
    return size == 0;
}

# HashMap.entrySet()

这个方法是我们在遍历的时候，常用的一个方法，它的实现有点小复杂。 我们来看下。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 返回这个Map里映射关系的一个 Set 视图.
 * 修改HashMap会影响这个 Set 视图, 同样的，在这个视图里修改, 也会影响HashMap
 * 如果通过对视图的迭代过程来修改HashMap(除了迭代器自身的remove方法,或者对迭代器返回的Entry的setValue操作),
 * 修改的结果是不确定的。
 * 这个 set 视图, 支持元素的删除, 也会从 HashMap 中删除对应的元素.
 *  支持 Iterator.remove, Set.remove,  Set.removeAll, Set.retainAll, Set.clear 等操作
 * 但是它不支持 add, addAll 操作
 */
public Set<Map.Entry<K, V>> entrySet() {
    Set<Map.Entry<K, V>> es;
    return (es = entrySet) == null ? (entrySet = new HashMap.EntrySet()) : es;
}

从上面的代码可以看出，如果 entrySet 这个属性的为 null 的时候，就会返回一个空的 HashMap 的 entry , 否则就返回 entrySet(es) .
那么 entrySet 这个字段是怎么来的呢？

最先 HashMap 定义了一个这样的字段。

1
2
3
4
5
/**
 * 保存缓存的 entrySet().
 * 注意: 这个AbstractMap 的字段会被 keySet() 和 values()使用。
 */
transient Set<Map.Entry<K, V>> entrySet;

好了，我们接着来看 HashMap.EntrySet()

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
/**
    * EntrySet 继承的是 AbstractSet,
    * 泛型传入
    */
final class EntrySet extends AbstractSet<Map.Entry<K, V>> {

    public final int size() {
        return size;
    }

    public final void clear() {
        HashMap.this.clear();
    }

    /**
        * 直接调用 HashMap 迭代器
        *
        * @return
        */
    public final Iterator<Map.Entry<K, V>> iterator() {
        return new HashMap.EntryIterator();
    }

    /**
        * 判断是否存在,
        * 直接调用的是hashMap的getNode方法
        */
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
        Object key = e.getKey();
        HashMap.Node<K, V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }

    /**
        * 直接调用的 HashMap的删除方法.
        * 从这个方法中也可以看出来, 我们在 set试图中删除元素是会直接影响Hashmap的。
        */
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }

    /**
        * entrySet 的分隔器
        */
    public final Spliterator<Map.Entry<K, V>> spliterator() {
        return new HashMap.EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }

    /**
        * entrySet 的迭代器
        */
    public final void forEach(Consumer<? super Map.Entry<K, V>> action) {
        HashMap.Node<K, V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (HashMap.Node<K, V> e = tab[i]; e != null; e = e.next)
                    action.accept(e);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

# HashMap.replace()

这个是 HashMap 覆盖掉 JDK8 版本中 的替换方法，将制定的 K-V 映射替换掉。这个方法也会匹配 Value 的值是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
@Override
public boolean replace(K key, V oldValue, V newValue) {
    HashMap.Node<K, V> e;
    V v;
    if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

这个也是覆盖 JDK8 版本中 Map 的方法，返回原来的值。

1
2
3
4
5
6
7
8
9
10
11
@Override
public V replace(K key, V value) {
    HashMap.Node<K, V> e;
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

# HashMap.forEach()

这个也是一个常用的方法，实现也比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 @Override
public void forEach(BiConsumer<? super K, ? super V> action) {
    HashMap.Node<K, V>[] tab;
    if (action == null)
        throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        for (int i = 0; i < tab.length; ++i) {
            for (HashMap.Node<K, V> e = tab[i]; e != null; e = e.next)
                action.accept(e.key, e.value);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

# HashMap.clear()

清空方法也是很简单的，逐一置空 null HashMap 的每个 bin

1
2
3
4
5
6
7
8
9
public void clear() {
    HashMap.Node<K, V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

# 问题解答

  • 如果我的 HashMap 的初始大小设置为 [3|9|12] , 第一次扩容的时候，容量变为了多少？是如何进行扩容的？
  • (有毒的问题) 假设 Hash 表的长度是 32, 已知某一个 bin 中的链表长度为 7, 如果新增一个元素还是在该 bin 中的时，会进行什么操作？ resize 还是 treeifyBin ? 假设完成这个操作后该 bin 中元素数量没变，又新增一个元素还是到该 bin 中，这时进行什么操作？

# 总结

  • 表中允许 null 的键和 null 值。
  • 线程不同步，
  • 不保证元素的顺序。

# 网上常见面试问题汇总以及参考解答

# 冷门知识点

# JDK 变更历史说明

# 课后娱乐

  • java 实现红黑树
  • 自定义实现 hashMap。

# 参考文档 & 答谢

# 感受

  • 注释：新字段要加注释标注此字段的作用，该字段是什么含义。

阅读之前记录

1. 图解。遇到问题，画图说明。
2. 一定要有自己的理解。
3. 对比其他版本 JDK。

# 最后

期望与你一起遇见更好的自己

期望与你一起遇见更好的自己

更新于 阅读次数 次

请我喝[咖啡]~(￣▽￣)~*

方小白 微信支付

微信支付

方小白 支付宝

支付宝

方小白 numberpay

numberpay