HashMap 源码总结

线索：

1. HashMap 结构、理解散列表；

2. 理解散列函数；

3. HashMap 是如何确定下标的；

4. equals 和 hashCode 规范

5. size、capacity、threshold、loadFactor

6. 树化与反树化

7. 谈谈 HashMap 在并发环境可能出现无限循环占用 CPU、size 不准确等诡异的问题。

// 阅读时重点阅读 putVal()，初始化、扩容、树化都与它有关。

1. HashMap 的整体结构：Node<K,V>[] table;

注意，链表并非散列表必要的组成部分，当散列冲突的解决方案采用线性探测或单链表改造为红黑树时，可以没有链表。

散列表是利用数组根据下标随机访问的特性，可以说，没有数组就没有散列表。

通过散列函数映射 key 到数组下标，取余本身就是一个散列函数，x%y=z，可以发现，z 的范围是[0,y-1]。

2. 容量与负载因子。

设计一个散列函数，至少要满足三个要求：

• 散列函数计算得到的散列值是一个非负整数；

  如果 key1 = key2，那 hash(key1) == hash(key2)；

  如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

不过，第三点无法满足，这就是散列冲突。散列冲突无法避免。因为 100 个抽屉放 101 只鸽子，就必然会发生冲突。解决散列冲突的方法有：开发寻址法和链表法。

但无论哪种方法，当散列表中空闲位置不多时，散列冲突的概率就会大大提高。因此，我们要尽可能保证散列表中有一定比例的空闲。而这一点由 负载因子 loadFactor 保证。

我们确保以下公式恒成立：

size < thresholdthreshold = loadFactor * capacityif (++size > threshold)    resize(); // 2倍

可以看到，容量和负载因子决定了可用桶的数量，空桶太多会浪费空间，如果使用的太满则会严重影响操作的性能。极端情况下，假设只有一个桶，那么它就退化成了链表。可以说散列表的好坏与容量、负载因子密切相关。

因此，在实践中，如果能事先知道 HashMap 要存取的键值对数量，可以考虑预先设置合适的容量大小，减少动态扩容的次数，从而提升性能。依据：负载因子 * 容量 > 元素数量；且容量要是 2 的倍数。

而对于负载因子，如果没有特别需求，不要轻易进行更改，因为 JDK 自身的默认负载因子是非常符合通用场景的需求的。

3. HashMap 源码总结。

1. Lazy-Load

Node<K,V>[] table

HashMap 构造器并不初始化数组，对数组的初始化在 resize()中。putàputValàresize()。即，resize()兼顾扩容和对数组的初始化。

2. 总结。

①HashMap 默认 capacity=16，loadFactor=0.75F，因此 threshold=12

②扩容是扩大 2 倍。// newCap = oldCap << 1、newThr = oldThr << 1; // double threshold

③数组搬迁由于 数组容量 变了，因此需要重新计算下标。然后再将旧数组中的元素搬迁到新数组。

④HashMap 解决散列冲突的方法是：链表+红黑树。当某个桶的链表长度超过 TREEIFY_THRESHOLD(默认 8)，且散列表容量超过 MIN_TREEIFY_CAPACITY（64），则会进行树化。当红黑树节点好于 8 个时，又会反树化成链表。

⑤HashMap 为什么要树化？

这本质上是一个安全问题。首先，哈希冲突的对象都会被放到同一个链表中，链表查询的复杂度是 O(N)，严重影响性能。

而在现实中，构造哈希冲突的数据并不困难，恶意代码就可以利用这些数据大量与服务器端交互，导致服务器端 CPU 大量占用，这就构成了哈希碰撞拒绝服务攻击。

而红黑树的增删查的复杂度都是 O(logN)，能提高 HashMap 的性能。而在数据量较小的情况下，红黑树要维护平衡，比起链表，性能上的优势并不明显。

⑥树化相关代码：

static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {p = tab[i = (n - 1) & hash];// p为第一个元素//……Node<K,V> e; K k;for (int binCount = 0; ; ++binCount) {	  if ((e = p.next) == null) {	    p.next = newNode(hash, key, value, null);	    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st	        treeifyBin(tab, hash);	    break;	  }	  p = e;   }}
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) {        //树化改造逻辑    }}
static final int MIN_TREEIFY_CAPACITY = 64;

综合上述代码来看，当 bin 的数量大于 TREEIFY_THRESHOLD 时：// binCount 就是一个桶中节点的数目

• 如果容量小于 MIN_TREEIFY_CAPACITY，只会进行简单的扩容。

• 如果容量大于 MIN_TREEIFY_CAPACITY ，则会进行树化改造。

3. HashMap 如何确定元素的下标。

// putVal(hash(key), key, value, false, true);final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null)    	tab[i] = newNode(hash, key, value, null);
static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

1. 解读 h^(h>>>16);

h>>>16，将 h 无符号右移 16 位。h 是 int 类型，有 32 位，因此相当于是将高位移到低位。

^ 异或：a b 相同，异或为 1；a b 不同，异或为 0

h^(h>>>16);

由于 高位^00…00，还是等于高位，然后是 高位^低位。因此上述步骤本质上只是多了一步 高位与低位异或的操作。即，

h 高位……h 高位^h 低位

2. 解读(n-1) & hash

1AND1=1; 1AND0=0; 0AND0=1

a & b 所得到的值，小于等于 min(a,b)，比如，0011&1101=0001，不会超过 0011

一般来说，hash>(n-1)，因此，(n-1) & hash 得到的结果小于等于(n-1)// 数组下标

3. 为什么要将 h 的高位移动到低位，并对其进行异或操作呢？

如果不这么做，而是直接 &，那么高 16 位所代表的部分特征可能被丢失。// (n-1)<<hash

这是因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞。

而之所以使用异或操作，是因为异或^能更好的保留各部分的特征；而“&”运算得到的值会向 0 靠拢；“|”运算得到的值会向 1 靠拢。