【Java】HashMap 源码分析

发表于2021-05-08更新于2022-03-14字数统计7.2k阅读时长50分阅读次数

HashMap 结构

本文参考博客：https://juejin.cn/post/6844904111817637901

HashMap 继承自 Map 接口，特点如下：

  • 存储数据是无序的（因为 hash 值是无序的）
  • 插入和查询效率很高，时间复杂度接近 O(1)
  • 线程不安全（若想要保证线程安全，可以使用 Collections 的 synchronizedMap，或者 ConcurrentHashMap）

HashMap 的结构为数组 + 链表 + 红黑树（JDK 1.8）：

红黑树是在 JDK1.8 版本才引入的，目的是加快链表的查询效率

image-20220208162356069

从图中可以看出，HashMap 的底层是一个哈希桶数组 Node<K, V>[] table，数组内存储的是 Node 结构的数据。

数组中每一个桶（bucket）内可以存储多个 Node：

  • JDK 1.7：以链表形式存储
  • JDK 1.8：如果链表很长，那查询效率便会降低，所以自 JDK 1.8 开始便引入了红黑树结构，即当某一个桶内的链表长度超过 8 的时候，链表便会转为红黑树。另外，当链表长度小于 6 的时候，会从红黑树转为链表。

HashMap 采用链地址法，即在数组的每个索引处都是一个链表结构，这样就可以有效解决 Hash 冲突（Hash 碰撞）问题。

HashMap 重要字段

静态常量值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 默认的初始容量为 16 （PS：aka 应该是 as know as）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大容量（容量不够时需要扩容）
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// ======================  红黑树相关  ==========================
// 链表长度为 8 的时候会转为红黑树
static final int TREEIFY_THRESHOLD = 8;

// 长度为 6 的时候会从红黑树转为链表
static final int UNTREEIFY_THRESHOLD = 6;

// 只有桶内数据量大于 64 的时候才会允许转红黑树
static final int MIN_TREEIFY_CAPACITY = 64;

以上几个字段的意义：

  • DEFAULT_INITIAL_CAPACITY：默认的初始容量为 16，代表默认的数组初始化长度为 16（桶的个数）。可以通过构造方法传参自定义该值，而无论自定义传入的值是多少，HashMap 在初始化时都会先将容量值向上取最接近该值的 2 的幂次方值（例如用户输入 20，将被修改为 32）
  • DEFAULT_LOAD_FACTOR：默认的负载因子为 0.75

HashMap 中没有单独维护一个 capacity 的字段，而是在每次 resize() 时根据之前的数组长度更新扩容后的长度（长度乘以 2）。如果没有在构造方法里自定义指定 initialCapacity，则初始化数组时长度会使用默认的 16，否则长度就为最接近自定义 initialCapacity 值的 2 的幂次方值

  • TREEIFY_THRESHOLD：当链表长度为 8 的时候会转为红黑树。但是前提是桶内数据量大于 MIN_TREEIFY_CAPACITY（默认为 64）。意味着如果数据量比较小的时候，优先扩容更加高效
  • UNTREEIFY_THRESHOLD：当链表长度为 6 的时候会从红黑树转为链表

成员变量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Map 中存储的数据量，即 key-value 键值对的数量
transient int size;

// HashMap 内部结构发生变化的次数，即新增、删除数据的时候都会记录，
// 注意：修改某个 key 的值，并不会改变这个 modCount
transient int modCount;

// 重点，代表最多能容纳的数据量，超过该数量就扩容
// 即最多能容纳的 key-value 键值对的数量
int threshold;

// 负载因子，默认为 0.75
// 注意，这个值是可以大于 1 的
final float loadFactor;
  • size：HashMap 中存储的数据量，即 key-value 键值对的数量。该变量将在每次插入一个数据后执行 size++
  • modCount：HashMap 内部结构发生变化的次数，即新增、删除数据的时候都会记录。用于
  • threshold：重要。代表当前长度的数组下最多能容纳的数据量，即 key-value 键值对的数量。当数组内总数据量大于该值时，将执行扩容 resize()。计算公式：threshold = length * loadFactor，其中 length 为当前数组长度（桶的个数）
  • loadFactor：重要。实际负载因子。默认值为 0.75，是基于时间和空间考虑而得的一个比较平衡的点

注意区分数组长度 length 和阈值 threshold 的区别

Node<K,V>

JDK 1.7 的基本结构为 Entry<K,V>。JDK 1.8 后改为 Node<K,V>（因为引入了红黑树）

Node<K,V> 是 HashMap 的一个静态内部类。HashMap 底层是一个 Node[] table。Node 实现了 Entry 接口，所以，Node 本质上就是一个 Key-Value 数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static class Node<K,V> implements Map.Entry<K,V> {
    // key 的 hash 值
    final int hash;
    final K key;
    V value;
    // 记录下一个 Node
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {...}
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() {...}
    public final V setValue(V newValue) {...}
    public final boolean equals(Object o) {...}
}

构造方法

该类共有四个构造方法：

image-20220208172744747

HashMap()

构造一个空的 HashMap，初始容量为 16，负载因子为 0.75。

1
2
3
4
// 构造一个空的 HashMap，初始容量为 16，负载因子为默认值 0.75
public HashMap() {    
    this.loadFactor = DEFAULT_LOAD_FACTOR;  // all other fields defaulted
}

HashMap(int initialCapacity)

构造一个空的 HashMap，并指定初始化容量，负载因子为默认的 0.75。构造函数内部会调用下文紧接着讲到的第三种构造函数。

1
2
3
4
5
// 构造一个空的 HashMap，并指定初始化容量，负载因子采用默认的 0.75
public HashMap(int initialCapacity) {    
    // 调用另一个构造函数
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

HashMap(int initialCapacity, float loadFactor)

构造一个空的 HashMap，并指定初始化容量，指定负载因子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 构造一个空的 HashMap，并指定初始化容量，指定负载因子
public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不为负数
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +  initialCapacity);
    // 初始容量大于最大值时，则取最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 负载因子不能小于 0，并且必须是数字，否则抛异常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    
    this.loadFactor = loadFactor;
    // 向上取 2 的幂次方作为初始容量与阈值（只有初始状态下二者才相等）
    this.threshold = tableSizeFor(initialCapacity);
    
    // 最大容量 MAXIMUM_CAPACITY 为 1 << 30
}

构造函数中会进行一系列的参数判断，并且会进行初始化操作：

  • 如果初始容量小于 0，或者负载因子小于 0 或不为数字时，会抛出 IllegalArgumentException 异常
  • 如果初始容量大于最大值（2^30），则会使用最大容量
  • 设置 threshold，直接调用 tableSizeFor() 方法，该方法会返回一个大于等于指定容量的 2 的幂次方的整数，例如传入 6，则会返回 8；传入 20，则会返回 32

tableSizeFor() 方法的详细解释见下文。另外，直接将得到的值赋给 threshold，难道不应该是这样的操作吗：this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;，其实不然，初始化的动作放在了 put 操作中。

HashMap(Map<? extends K, ? extends V> m)

构造一个非空的 HashMap，保证初始化容量能够完全容下传进来的 Map，另外，负载因子使用的是默认值 0.75。

1
2
3
4
5
6
// 构造一个非空的 HashMap，指定了默认的负载因子 0.75
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 将 Map 中的 key-value 赋值到新的 Map 中去
    putMapEntries(m, false);
}

putMapEntries() 方法是将传递进来的 Map 中的数据全都存入到当前的 HashMap 中去，方法的详解见下文。

HashMap 关键方法

tableSizeFor(int cap)

作用：计算数组的大小。该方法的作用是返回一个大于等于传入的参数的数值，并且返回值会满足以下两点：

  • 返回值是 2 的幂次方
  • 返回值是最接近传入的参数的值

该方法的设计非常巧妙：

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

方法内使用了大量的 “或运算”和 “右移”操作，目的是保证从最高位起的每个 bit 都是 1。

  • 首行 int n = cap - 1; 的作用，是为了防止传入的参数本身就是一个 2 的幂次方，否则会返回两倍于参数的值；
  • n |= n >>> 1; 的作用，是保证倒数第二个高位也是 1，下面的代码类似。
  • 最后一行之前，得到的数类似 0000 1111 这种从第一个高位起全是 1，这样只要加了 1，则返回的数值必然是 2 的幂次方。

一种比较朴素的实现方法是：从左到右遍历 cap，直到遇到第一个 1。那么想要的结果就是：该位的更高一位为 1，其余为全为 0 的数字。例如：

1
2
3
4
5
6
// 原数字
0000 0000 ... 0011 0010 1101
                ↑
// 向上取 2 的幂次方
0000 0000 ... 0100 0000 0000
               ↑

putMapEntries(Map<? extends K, ? extends V> m, boolean evict)

该方法是将参数 m 中的所有数据存入到当前的 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
// 将参数 m 中的所有元素存入到当前的 HashMap 中去
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // 获取 m 中的参数个数（key-value 的数量）
    int s = m.size();
    if (s > 0) {
        // 判断 table 是否被初始化过，否则初始化一遍。（PS：table 是在 put 操作的时候进行初始化的，所以如果当前的 HashMap 没有进行过 put 操作，则当前的 table 并不会被初始化）
        if (table == null) { // pre-size
            // 根据传进来的 map 的元素数量来计算当前 HashMap 需要的容量
            float ft = ((float)s / loadFactor) + 1.0F;
            // 计算而得的容量是不能大于最大容量的
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            // 将计算而得的容量赋值给 threshold，前提是大于当前容量（即不会减小当前的 HashMap 的容量）
            if (t > threshold)
                // 将容量转换为最近的 2 的 幂次方
                threshold = tableSizeFor(t);
        }
        // table 不为空，即已经初始化过了，
        // 如果 m 中的元素数量超过了当前 HashMap 的容量，则要进行扩容
        else if (s > threshold)
            resize();
        // 遍历 m 的每个元素，将它的 key-value 插入到当前的 HashMap 中去
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            // 插入数据（注意，为什么不是 put() 呢，因为 put() 其实也是调用的 putVal() 方法）
            putVal(hash(key), key, value, false, evict);
        }
    }
}

hash(Object key)

HashMap 中的 hash() 方法将调用 key 的 hashCode() 方法得到该对象的哈希值 h，然后将 h 的高 16 位与低 16位进行异或运算。

这样做的目的是：开发人员自定义的 hashCode() 方法得到的哈希值可能不够散列，就会导致数组中某些桶上的节点过多影响性能。因此 HashMap 额外将高位和低位进行混合运算，低位中掺杂了高位的信息，最后生成的 hash 值的随机性会增大（更加散列），从而有效降低哈希冲突的概率。

1
2
3
4
5
static final int hash(Object key) {
    int h; // h = key.hashCode()
    // 高 16 位与低 16 位进行异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在计算得到处理后的哈希值后，后续还需要进行一步“取余”操作，将哈希值均匀分布在数组长度范围内。即将原始范围很大的哈希值映射到数组长度 [0, length - 1] 范围内，从而决定当前 key 放在哪个桶里。

最常用的实现方式是取模运算：hash % length，但是 HashMap 却用了更加巧妙的方式：

1
hash & (length - 1);

其中，length 为当前数组的长度。之所以这样写可以实现该效果是因为： HashMap 会强制将数组长度设置为 2 的幂次方，从而这里的 length 的二进制形式只会有一位为 1，其余位都是 0，那么将其减一后，即可得到低位全是 1，高位全是 0 的形式，那么这样再和 hash 取与运算，就相当于把 hash 的高位给截断了（设置为 0），只留下低位的值，从而将数字的范围限制在了 [0, length - 1]。这也是 capacity/length 要设置为 2 的幂次方的一个原因，只有 length 为 2 的幂次方才可以用这种方式加速运算。

https://juejin.cn/post/6844904111817637901

取模运算

这种方式计算效率显然高于取余操作。

put(K key, V value)

此处介绍的是 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)，因为 put() 其实就是直接调用的 putVal()。

JDK 1.8 源码：

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
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 参数 onlyIfAbsent，true：不修改已存在的 value，false：已存在则进行修改
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // ① 如果当前 table 为空则进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 计算得到索引 i，算法在上文有提到，然后查看索引处是否有数据
    // ② 如果没有数据，则新建一个新的 Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 索引处有数据
    else {
        Node<K,V> e; K k;
        // ③ 索引处的第一个 Node 的  key 和参数 key 是一致的，所以直接修改 value 值即可（修改的动作放在下面）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // ④ 索引处的 bucket 是红黑树，按照红黑树的逻辑进行插入或修改
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // ⑤ 索引处的 bucket 是链表
        else {
            // 遍历链表上面的所有 Node
            for (int binCount = 0; ; ++binCount) {
                // 索引处的 Node 为尾链
                if ((e = p.next) == null) {
                    // 直接新建一个 Node 插在尾链处
                    p.next = newNode(hash, key, value, null);
                    // 判断是否需要转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 链表转换为红黑树，此方法在上文中也有介绍
                        treeifyBin(tab, hash);
                    break;
                }
                // 当前 Node 的 key 值和参数 key 是一致的，即直接修改 value 值即可（修改的动作放在下面）
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 找到了相同 key 的 Node，所以进行修改 vlaue 值即可
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 修改 value 值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 修改操作，直接 return 结束掉代码逻辑
            return oldValue;
        }
    }
    // 记录结构发生变化的次数
    ++modCount;
    // ⑥ 判断是否需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    // 新增的 Node，返回 null
    return null;
}

get(Object key)

此处介绍的是 getNode(int hash, Object key，因为 get() 其实就是直接调用的 getNode()。get() 方法也是比较简单的，就是根据 key 获取 table 的索引，然后再分情况查找拥有相同 key 的 Node。

JDK 1.8 源码

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

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 当前 table 不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断索引处的第一个 Node 的 key 值是否和参数 key 相同，相同则返回该 Node
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 索引处的第一个 Node 不是想要的，则接着查 next
        if ((e = first.next) != null) {
            // bucket 是红黑树结构
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // bucket 是链表结构
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

resize()

resize() 是一个很重要的方法，作用是扩容，从而使得 HashMap 可以存储更多的数据。因为当我们不断向 HashMap 中添加数据时，它总会超过允许存储的数据量上限，所以必然会经历 扩容 这一步操作，但是 HashMap 底层是一个数组，我们都知道数组是无法增大容量的，所以 resize 的过程其实就是新建一个更大容量的数组来存储当前 HashMap 中的数据。

JDK 1.8 源码：

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
final Node<K,V>[] resize() {
    // 当前 table
    Node<K,V>[] oldTab = table;
    // 当前的 table 的大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 当前 table 的 threshold，即允许存储的数据量阀值
    int oldThr = threshold;
    // 新的 table 的大小和阀值暂时初始化为 0
    int newCap, newThr = 0;
    // ① 开始计算新的 table 的大小和阀值
    // a、当前 table 的大小大于 0，则意味着当前的 table 肯定是有数据的
    if (oldCap > 0) {
        // 当前 table 的大小已经到了上线了，还咋扩容，自个儿继续哈希碰撞去吧 
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新的 table 的大小直接翻倍，阀值也直接翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // b、当前的 table 中无数据，但是阀值不为零，说明初始化的时候指定过容量或者阀值，但是没有被 put 过数据，因为在上文中有提到过，此时的阀值就是数组的大小，所以直接把当前的阀值当做新 table 的数组大小即可
    // 回忆一下：threshold = tableSizeFor(t);
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // c、这种情况就代表当前的 table 是调用的空参构造来初始化的，所有的数据都是默认值，所以新的 table 也只要使用默认值即可
    else {  // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新的阀值是 0，那么就简单计算一遍就行了
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // ② 初始化新的 table
    // 这个 newTab 就是新的 table，数组大小就是上面这一堆逻辑所计算出来的
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 遍历当前 table，处理每个下标处的 bucket，将其处理到新的 table 中去
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 释放当前 table 数组的对象引用（for循环后，当前 table 数组不再引用任何对象）
                oldTab[j] = null;
                // a、只有一个 Node，则直接 rehash 赋值即可
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // b、当前的 bucket 是红黑树，直接进行红黑树的 rehash 即可
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // c、当前的 bucket 是链表
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表中的每个 Node，分别判断是否需要进行 rehash 操作
                    // (e.hash & oldCap) == 0 算法是精髓，充分运用了上文提到的 table 大小为 2 的幂次方这一优势，下文会细讲
                    do {
                        next = e.next;
                        // 根据 e.hash & oldCap 算法来判断节点位置是否需要变更
                        // 索引不变
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引 + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原 bucket 位置的尾指针不为空(即还有 node )
                    if (loTail != null) {
                        // 链表末尾必须置为 null
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        // 链表末尾必须置为 null
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

其中，如果桶内节点是链表结构，则遍历链表内每一个节点，使用尾插法移动扩容后的节点位置，并判断该节点的哈希值在原容量的最高位的值是 1 还是 0。这里是利用了容量为 2 的幂次方的特点快速进行计算（也是容量强制修改为 2 的幂次方的原因），节省扩容时重新计算桶位置编号的时间，从而加速扩容速度，并且使得扩容后节点的分布更加散列均匀。

具体原理为：原容量 oldCap 肯定为 2 的幂次方，意味着其只在某一位为 1，其余都是 0。那么在计算 (e.hash & oldCap) 时，就可以利用该特性快速得到节点 e 的 hash 值（保存在 Node 中） 在该位的值是 1 还是 0。例如：

1
2
3
4
5
6
// e.hash
0000 0000 ... 0011 0111 1101
                    ↑
// oldCap
0000 0000 ... 0000 0100 0000
                    ↑

此时发现 e.hash 在该位置上的值为 1。这一位为 1 代表着在扩容后 e 对应的桶编号将变化（若为 0 则不变）。

在扩容后，新的容量 newCap 变为了原来的两倍。此时若再采用前面介绍过的方法 e.hash & (newCap - 1) 计算新的桶编号时，将因为该位值为 1 而使得其桶编号增大 oldCap，变为 j + oldCap（j 为旧编号）。这样就不再需要使用 e.hash & (newCap - 1) 公式重新计算每一个节点的新桶编号，而是可以直接根据 (e.hash & oldCap) 的值是 1 还是 0，决定该节点在扩容后处于原位置还是新位置 j + oldCap。

可以看出，这种方式一方面节省了 rehash 的计算时间，另一方面也保证了扩容后的节点分布是散列均匀的。这也是为什么容量要设置为 2 的幂次方的原因。

HashMap 工作流程

1. 新建 HashMap<K,V>

  • 执行 new HashMap(capacity, loadFactor) 时没有立刻创建 Node 数组（懒加载），而是在第一次调用 put() 方法时再初始化一个长度默认为 16 的 Node 数组
  • 如果构造方法指定了容量 capacity 和负载因子 loadFactor，则构造方法里会先调用 [tableSizeFor(int cap)](#tableSizeFor(int cap)) 方法，将传入的 capacity 向上取最接近的 2 的幂次方值，作为初始化的容量值。
  • 否则默认的初始化容量为 16，负载因子 loadFactor 为 0.75

2. put(key, value)

源码：put(K key, V value)

  • 首先判断 table 是否为空或 table.length == 0：如果是，说明该数组此时是第一次使用，需要进行初始化，创建指定长度的 Node 数组。如果不是，则不需要再做初始化
  • 根据传入的 key 计算 hash 值 hash(Object key)：
    • 首先调用该对象的 hashCode() 方法，得到其自定义的哈希值 h
    • 然后将 h 的高 16 位与低 16位进行异或运算（为了让该 hash 更加散列，防止用户自定义的 hashCode() 不够散列）
    • 将异或后的 h 值进行 h & (length - 1) 操作（效果等效于取余数，效率更高），截取出 h 的低位数字，作为 key 应该进入的桶的编号 i
  • 在 Node 数组中定位到该编号的桶，判断 table[i] 是否为 null：
    • 如果为 null，说明该桶是空的，没有任何节点。此时可以直接插入：令 table[i] = new Node(key, value)
    • 如果不为 null，说明该桶不为空，判断：
      • 如果 table[i] 位置存储的节点内保存的 k 等于 key（引用地址相等或 equals() 成立），则覆盖该位置的节点的 v 为传入的 value。然后方法直接返回旧值 return oldValue，不再进行后面的处理。如果不相等：
      • 如果 table[i] 的类型为 TreeNode，则说明当前桶内存储结构为红黑树。则按照红黑树的插入方法，直接插入当前 key、value
      • 如果 table[i] 的类型为普通 Node，则说明当前桶内存储结构为链表。遍历该链表的每个节点（遍历过程中，统计该桶内的节点个数 binCount）
        • 如果发现某个节点的 k 等于 key，则跳出遍历，将该节点的 v 修改为当前 value。然后方法直接返回旧值 return oldValue，不再进行后面的处理
        • 如果遍历到链表尾部还没发现一个等于 key 的节点，则创建一个节点 new Node(key, value)，并将该节点链接到链表的尾部，作为最后一个节点（尾插法）
        • 完成遍历后，如果 binCount 个数大于 8，且所有节点的个数大于 64，则将该链表转换为红黑树
  • 只有插入新节点后才会来到这里（如果是覆盖原节点值，则之前已经 return oldValue）。
  • 节点插入完成后，当前数组的节点总数加一 ++size，并判断增加后的节点总数是否大于阈值 ++size > threshold（threshold = length * loadFactor）。如果大于，则需要进行扩容 resize()：
    • 计算扩容后的数组大小：将原数组长度乘以 2（仍然是 2 的幂次方）
    • 遍历数组中的每一个桶：
      • 如果桶内第一个节点是当前桶内唯一一个节点，则可以直接 rehash 赋值到新的数组：newTab[e.hash & (newCap - 1)] = e（借助容量 newCap 为 2 的幂次方的特点）
      • 如果桶内节点是红黑树结构 TreeNode，则调用 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap)
      • 如果桶内节点是链表结构 Node，则遍历链表内每一个节点，使用尾插法移动扩容后的节点位置，并判断该节点的哈希值在原容量的最高位的值是 1 还是 0（利用容量为 2 的幂次方的特点快速进行计算）：
        • (e.hash & oldCap) == 0：表明扩容后不需要移动桶编号，还在原编号位置，即 newTab[j] = loHead
        • (e.hash & oldCap) == 1：表明扩容后需要移动桶编号，并且移动后的值为 【原值 + 原容量】： j + oldCap ，即 newTab[j + oldCap] = hiHead
        • 最后分别设置链表的尾部为 null
  • 记录 HashMap 结构发生变化的次数 ++modCount，fail-fast 机制将借由该值判断迭代过程中该哈希表是否被其他线程修改过，若修改过就抛出 ConcurrentModificationException 异常
  • 返回 null（表明是新增而非覆盖）

如果覆盖则返回旧值，如果新增则返回 null

流程图

put 流程

3. get(key)

get(key) 方法比较简单，就是重复上面的部分操作：先计算 hash 值确定桶索引 i，然后根据该桶内节点的类型是红黑树还是链表进行遍历，直到获取到对应的 value 或返回 null（没有找到）

HashMap 1.7 VS 1.8

JDK 1.7 版本的 HashMap：

  • 元素类型为 Entry
  • 【数组 + 链表】结构
  • 当插入新元素时，采用头插法：新元素插入到 Entry<K,V> 数组中某个桶上 table[i]，原本的元素以链表形式连接在新元素的 next 上（高并发下扩容时可能出现循环移动链表节点问题，导致 CPU 运行 100%）
  • 扩容后，链表中的先后顺序颠倒，在头部的节点被保存到了尾部（因为是头插法），在高并发下可能出现**环形链表死循环（循环引用）**问题，导致 CPU 运行 100%

JDK 1.8 版本的 HashMap：

  • 元素类型为 Node
  • 【数组 + 链表 + 红黑树】结构
  • 当插入新元素时，采用尾插法：新元素插入到 Node<K,V> 数组中某个桶上 table[i] 时，将先遍历该桶内链表的节点个数，然后将新元素插入到最后一个节点的 next 上
  • 当插入新元素时发现某个桶内的节点个数大于 8 个，且数组内总节点个数大于 64 时，会将该桶内的节点从链表形式转为红黑树形式。当之后发现红黑树节点个数小于 6 或不平衡时，就会退化回链表结构
  • 扩容后，链表中的先后顺序保持不变，在头部的节点仍然在头部（因为是尾插法）。高并发下不会有环形链表死循环问题。

在并发修改时，两个版本都会出现数据被覆盖的情况。即第一个线程刚在某个桶上创建了节点，就被第二个线程修改了。

HashMap 线程不安全

Jdk7的问题：第一个线程先完成了扩容。但是第二个线程在切换前还拿着扩容后的两个entry的引用。e和next，他还会继续移动的，最终可能会出现循环链表，一直把cpu资源耗尽