从阿里规约谈起 - HashMap 初始化和扩容相关

2019-08-30
阿里规约
Java 源码

引言

日常开发中使用 HashMap 方法如下：

1Map<String, Object> HashMap = new HashMap<>();

但是阿里规约会提示有问题：

未指定初始化容量

由此我们可以看一下 HashMap 初始化和扩容相关。

注：本文涉及了少许 HashMap 基础，由于与主线无关，不详讲。源码均加了些注释，注释无法解释清楚的地方放在源码之后论述。

new

 1public HashMap() {
 2    this.loadFactor = DEFAULT_LOAD_FACTOR;
 3}
 4
 5public HashMap(int initialCapacity, float loadFactor) {
 6    //判断异常
 7    ...
 8    //初始化负载因子
 9    this.loadFactor = loadFactor;
10    //初始化阈值
11    this.threshold = tableSizeFor(initialCapacity);
12}
13
14//十分精巧地实现了求一个数的最近的 2 的幂
15static final int tableSizeFor(int cap) {
16    int n = cap - 1;
17    n |= n >>> 1;
18    n |= n >>> 2;
19    n |= n >>> 4;
20    n |= n >>> 8;
21    n |= n >>> 16;
22    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
23}

出人（我自己）意料的是默认构造函数初始化极其简单，只给负载因子赋值，除了直接传入 map 的构造函数外，最复杂的两个参数的构造函数也只是给负载因子和阈值赋值。并未初始化 bucket 数组。

那么什么时候初始化 bucket 数组的呢？

很容易想到初始化完 HashMap 我们直接使用 put() 操作。

put

 1public V put(K key, V value) {
 2    return putVal(hash(key), key, value, false, true);
 3}
 4
 5final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
 6    Node<K,V>[] tab; Node<K,V> p; int n, i;
 7    //当第一次 put 时，table 尚未初始化，所以 tab 为 null，进行一次 resize() 操作
 8    //后续 put 一般不再走该分支
 9    if ((tab = table) == null || (n = tab.length) == 0)
10        n = (tab = resize()).length;
11    //确定当前 key 在数组中的下标
12    //此处就是经典的当 n 为 2 的幂时，(n - 1) & hash == hash % n 的技巧
13    //如下部分为碰撞和非碰撞时的储存过程，与本文主题不相关，不再详细论述
14    if ((p = tab[i = (n - 1) & hash]) == null)
15        tab[i] = newNode(hash, key, value, null);
16    else {
17        Node<K,V> e; K k;
18        if (p.hash == hash &&
19            ((k = p.key) == key || (key != null && key.equals(k))))
20            e = p;
21        else if (p instanceof TreeNode)
22            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
23        else {
24            for (int binCount = 0; ; ++binCount) {
25                if ((e = p.next) == null) {
26                    p.next = newNode(hash, key, value, null);
27                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
28                        treeifyBin(tab, hash);
29                    break;
30                }
31                if (e.hash == hash &&
32                    ((k = e.key) == key || (key != null && key.equals(k))))
33                    break;
34                p = e;
35            }
36        }
37        if (e != null) { // existing mapping for key
38            V oldValue = e.value;
39            if (!onlyIfAbsent || oldValue == null)
40                e.value = value;
41            afterNodeAccess(e);
42            return oldValue;
43        }
44    }
45    ++modCount;
46    //size 为所有键值对的数量，threshold = capacity * loadFactor
47    //也就是当键值对数量超过了 capacity 的 0.75 倍时，调用 resize() 扩容
48    if (++size > threshold)
49        resize();
50    afterNodeInsertion(evict);
51    return null;
52}
53
54//hash 值并非 key 的 hashCode，而是 hashCode 高低 16 位的异或
55//这样做是为了高低位进行扰动，使得这个 hashCode 能够全部参与对数组索引的计算
56//进一步降低碰撞的概率
57//本文后续提及的 hash 均指 hash(Object key) 之后的值
58static final int hash(Object key) {
59    int h;
60    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
61}

通过 putVal() 我们可知，当第一次执行 put 操作时才会调用 resize() 真正初始化 bucket 数组，当键值对超过了 capacity 的 0.75 倍时，调用 resize() 扩容。

resize

那我们就来看看 resize() 是如何扩容的。

 1final Node<K,V>[] resize() {
 2    Node<K,V>[] oldTab = table;
 3    int oldCap = (oldTab == null) ? 0 : oldTab.length;
 4    int oldThr = threshold;
 5    int newCap, newThr = 0;
 6    //当 table 不为 null 时 oldCap 大于 0，也就是非初始化，单纯扩容
 7    if (oldCap > 0) {
 8        //超过最大值时直接把阈值设成 Integer.MAX_VALUE，不再扩容
 9        //此时可以继续 put 进键值对，因为键相同 hash 值的不同键值对可以继续以链表形式加入存储
10        if (oldCap >= MAXIMUM_CAPACITY) {
11            threshold = Integer.MAX_VALUE;
12            return oldTab;
13        }
14        //否则就扩容 2 倍
15        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
16            newThr = oldThr << 1; // double threshold
17    }
18    //oldCap == 0，但是 oldThr > 0，一般情况下表示带参构造函数初始化
19    else if (oldThr > 0) // initial capacity was placed in threshold
20        newCap = oldThr;
21    //oldCap == 0，oldThr == 0，表示无参构造函数初始化
22    else { // zero initial threshold signifies using defaults
23        newCap = DEFAULT_INITIAL_CAPACITY;
24        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
25    }
26    //初始化新阈值
27    if (newThr == 0) {
28        float ft = (float)newCap * loadFactor;
29        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
30    }
31    threshold = newThr;
32    @SuppressWarnings({"rawtypes","unchecked"})
33        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
34    table = newTab;
35    if (oldTab != null) {
36        //将原来的 bucket 数组元素转移至新 bucket 数组中
37        for (int j = 0; j < oldCap; ++j) {
38            Node<K,V> e;
39            if ((e = oldTab[j]) != null) {
40                oldTab[j] = null;
41                //当 bucket 只存在一个键值对时，直接计算下标索引到新的数组中
42                if (e.next == null)
43                    newTab[e.hash & (newCap - 1)] = e;
44                //当 bucket 存在红黑树时，拆分然后映射（涉及红黑树，不做详解）
45                else if (e instanceof TreeNode)
46                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
47                //当 bucket 存在一条链表时，切分成两条链，需要进一步分析
48                else { // preserve order
49                    Node<K,V> loHead = null, loTail = null;
50                    Node<K,V> hiHead = null, hiTail = null;
51                    Node<K,V> next;
52                    do {
53                        next = e.next;
54                        if ((e.hash & oldCap) == 0) {
55                            if (loTail == null)
56                                loHead = e;
57                            else
58                                loTail.next = e;
59                            loTail = e;
60                        }
61                        else {
62                            if (hiTail == null)
63                                hiHead = e;
64                            else
65                                hiTail.next = e;
66                            hiTail = e;
67                        }
68                    } while ((e = next) != null);
69                    //低链下标不变
70                    if (loTail != null) {
71                        loTail.next = null;
72                        newTab[j] = loHead;
73                    }
74                    //高链下标为原下标+原 bucket 数组长度
75                    if (hiTail != null) {
76                        hiTail.next = null;
77                        newTab[j + oldCap] = hiHead;
78                    }
79                }
80            }
81        }
82    }
83    return newTab;
84}

reszie() 操作对于扩容分为了三种情况

  1. bucket 只有一个键值对时，直接计算新的索引位置并插入键值对
  2. bucket 是红黑树时，调用 split 方法处理。
  3. bucket 是链表时，分成了两条链表，低位链表插入原位置，高位链表插入原索引+原 bucket 数组长度处

详讲第三种：

首先要认知一件事：当 bucket 成链表时，链表每个节点的 hash 值不一定相同，它们成为一条链表只因为该 key 的 hash 值取模后得到的值相同。

第三种情况发生后，有一个特别的优化：(e.hash & oldCap) == 0

当 (e.hash & oldCap) == 0 时插入到原下标位置，否则插入原下标+原 bucket 数组长度处，为何如此插入？如下例子希望可以理解：

扩容前数组长度 n=16，扩容后 n=32。

现在有两个 hash：

  • hash1 = 1111 1111 0000 0101
  • hash2 = 1111 1111 0001 0101
扩容前扩容后
n0000 0000 0001 00000000 0000 0010 0000
n-10000 0000 0000 11110000 0000 0001 1111
hash11111 1111 0000 01011111 1111 0000 0101
数组下标
hash1&(n-1)		0000 0000 0000 0101
=5		0000 0000 0000 0101
=5
扩容前扩容后
n0000 0000 0001 00000000 0000 0010 0000
n-10000 0000 0000 11110000 0000 0001 1111
hash21111 1111 0001 01011111 1111 0001 0101
数组下标
hash2&(n-1)		0000 0000 0000 0101
=5		0000 0000 0001 0101
=5+16

绿色为参与运算的位，红色为由于扩容而增加参与运算的位。

当扩容以后，数组的长度的高位多了一位 1 参与计算索引下标，所以只需要计算 n&hash，如果为 0 时，扩容导致的新增最高位不影响原下标计算结果，否则新下标为原下标+原 bucket 数组长度。使用该算法后不必每个节点都重新计算下标，大大提高了性能。

总结

  • HashMap 初始化时不会初始化 bucket 数组，当第一次 put 时才会初始化，而且会初始化为离传入值的最近的 2 的幂。
  • 当数据量大于 bucket 数组的 75% 时，扩容为原来的 2 倍。
  • 扩容+数据移动是耗费资源的操作，所以我们一开始应该初始化合适的值，防止多次扩容。合适值阿里规约中已经给出：initialCapacity =（需要存储的元素个数 / 负载因子）+ 1。
  • 计算阈值的 tableSizeFor()、计算下标的 hash&(n-1) 取模、扩容时高低链表分别插入的 (e.hash & oldCap) == 0 和计算插入下标设计十分精妙，观之感叹不已！！！
从阿里规约谈起 - Arrays.asList 三坑
从阿里规约谈起 - 禁用 Executors 创建线程池