HashMap源码解析二

由于 HashMap 的源码过于精简，所以我将会把分析写入代码注释中。

put 过程

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with key, or
 *         null if there was no mapping for key.
 *         (A null return can also indicate that the map
 *         previously associated null with key.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这里第一步是调用了 hash() 方法，然后再使用 putVal() 方法插入值。

hash()

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这个方法很简短，但他中间的东西可不少。

一开始 key == null 时直接返回0，这就是为啥 HashMap允许key为null。key为null时，会一直存储在table的第一个位置上。

然后他调用了 Object 的本地方法hashCode()，获得了hash值 h 。

后面的 (h >>> 16) 这步操作是将 h 的高16位移动到了低16位。

接着 h 和 h >>> 16 做了一次异或运算(^)。

这里我们也可以验证了，一些人说 HashMap有两次hash 的原由，第一次是调用Object 的本地hashCode()方法，第二次是用这个hash值再次进行异或运算。

其实这里使用 ^ 而不使用 & 或者 | 是有原因的，我们看看三个运算符号的计算：

&：1 & 1 = 1		1 & 0 = 0		0 & 1 = 0		0 & 0 = 0		
|：1 | 1 = 1		1 | 0 = 1		0 | 1 = 1		0 | 0 = 0	
^：1 ^ 1 = 0		1 ^ 0 = 1		0 ^ 1 = 1		0 ^ 0 = 0	
1
2
3

大家可以看到 & 和 | 的运算结果并不是均匀的，&的结果更偏向于0 ，|的结果更偏向于1。所以如果使用这个两个运算符号计算，会让我们的 hash 值变得不那么散列，会加大hash冲突。

只有 ^ 的计算结果是均匀的，二次计算的时候让hash值依旧是最大程度的散列开。

putVal()

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
// 第四个参数 onlyIfAbsent 如果是 true，那么存在该 key 时更改现有值
// 第五个参数 evict 我们这里不关心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 第一次 put 值的时候，会触发下面的 resize()，初始化数组长度
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 找到具体的数组下标，如果此位置没有值，则创建一个新的 Node 并放置在这个位置就可以了
    // 这里的(n - 1) & hash 相当于做了求余运算，运算结果就是 table 上具体的 index
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {// 到这就说明数组该位置有数据了，要开始处理冲突了
        Node<K,V> e; K k;
        // 首先判断该位置的第一个数据和我们要插入的数据是否有相同的hash和key值，如果是，则先记录这个节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode) // 如果该节点是代表红黑树的节点，调用红黑树的插值方法
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { // 到这里，说明数组该位置上是一个链表类型
            for (int binCount = 0; ; ++binCount) {
                // 如果遍历到末尾，则在尾部追加该元素结点(Java7 是插入到链表的最前面)
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // TREEIFY_THRESHOLD 为 8，所以，如果新插入的值是链表中的第 8 个
                    // 会调用 treeifyBin() 方法，也就是将链表转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果在该链表中找到了有相同hash和key值的节点。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 停止遍历，此时e已经记录了该结点(在上面的if判断中的 e = p.next)
                    break;
                p = e;
            }
        }
        // e!=null 说明存记录到具有相同key的节点
        // 下面这个 if 其实就是进行 "值覆盖"，然后返回旧值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // 这个是空函数，可以由用户根据需要覆盖
            return oldValue;
        }
    }
    ++modCount;
    // 如果 HashMap 由于新插入这个值导致 size 已经达到了阈值，需要进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); // 这个是空函数，可以由用户根据需要覆盖
    return null;
}
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

扩容

resize() 方法用于初始化数组或数组扩容，每次扩容后，容量为原来的 2 倍，并进行数据迁移。

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0; // Cap 可以理解为数组长度，Thr 则是HashMap的实际存储大小
    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) // 对应使用 new HashMap(int initialCapacity) 初始化后，第一次put的时候
        newCap = oldThr;
    else {// 对应使用 new HashMap() 初始化后，第一次 put 的时候
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) { // 对应使用 new HashMap(int initialCapacity) 初始化后，第一次put的时候
        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; // 如果是初始化数组，到这里就结束了，返回 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;
                // 如果是红黑树，则调用split()方法
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    // 这块是处理链表的情况，
                    // 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序
                    // loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 这个if可能理解起来很模糊，我们下面单独分析分析
                        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;
                        // 第二条链表的新的位置是 j + oldCap
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
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

大家可能对上面的 (e.hash & oldCap) == 0 有点疑惑，为什么这样就可以判断是放在原位置。

正常来说应该要使用上方的 e.hash & (newCap - 1) 来判断新位置。

我们先用e.hash & (newCap - 1) 举一个例子：

我们有一个hash值为：0001 0010 1100 (十进制：300)
容量为16时索引位置： 0001 0010 1100 ^ 0000 0000 1111 = 0000 0000 1100 (十进制：12)
容量为32时索引位置： 0001 0010 1100 ^ 0000 0001 1111 = 0000 0000 1100 (十进制：12)
容量为64时索引位置： 0001 0010 1100 ^ 0000 0011 1111 = 0000 0010 1100 (十进制：44(12+32))
容量为128时索引位置：0001 0010 1100 ^ 0000 0111 1111 = 0000 0010 1100 (十进制：44)
1
2
3
4
5

我们发现容量32->64时，位置发生了改变。

这两个**(newCap - 1)**的区别在于，扩容后新增加的1是倒数第六个位置，刚好hash值的倒数第六个值也是1，所以发生了位置改变。

其他两次都是因为扩容后，(newCap - 1)新增加的1的位置，hash值与之对应的位置上确实0，所以没有发生位置改变。

所以关键的地方就在于 **(newCap - 1)**新增的1的位置，和hash值与之对应位置上的数做位于运算，该位置的值是否等于1，等于1就位置改变，等于0就放在原位置。

而容量为32的 **(newCap - 1)**怎么取得他新增1后的值呢，那就是直接取容量值： oldCap=32

(newCap-1)    = 0001 1111(2)
oldCap=32(10) = 0010 0000(2)
hash值   = 0001 0010 1100(2)
1
2
3

这个时候我们只用将oldCap 和 hash值做一次判断就知道是否需要改变位置了

当然，由于转换成10进制做判断后，000…0001000…000这种数会变成大于0的数，所以源码中用的if( …==0){} else{}，而不是if( …==0){} else if(…==1){}。

所以这里使用了 (e.hash & oldCap) == 0 去代替 e.hash & (newCap - 1) 是完全没有问题的。