由阿里巴巴Java开发规约HashMap条目引发的故事

作者: 阿里云云栖号 | 来源:发表于2017-10-23 10:28 被阅读1177次

大热的《阿里巴巴Java开发规约》中有提到：

【推荐】集合初始化时，指定集合初始值大小。

说明：HashMap使用如下构造方法进行初始化，如果暂时无法确定集合大小，那么指定默认值（16）即可：

看到代码规约这一条的时候，我觉得是不是有点太 low 了，身为开发，大家都知道 HashMap 的原理。

什么？这个要通过插件监测？没必要吧，哪个开发不知道默认大小，何时 resize 啊，然后我和孤尽打赌随机咨询几位同学以下几个问题：

HashMap 默认bucket数组多大？

如果new HashMap<>(19)，bucket数组多大？

HashMap 什么时候开辟bucket数组占用内存？

HashMap 何时扩容？

抽样调查的结果出乎我的意料：

HashMap 默认bucket数组多大？（答案是16，大概一半的同学答错）

如果new HashMap<>(19)，bucket数组多大？（答案是32，大多被咨询同学都不太了解这个点）

HashMap 什么时候开辟bucket数组占用内存？（答案是第一次 put 时，一半同学认为是 new 的时候）

HashMap 何时扩容？（答案是put的元素达到容量乘负载因子的时候，默认16*0.75，有1/4同学中枪）

HashMap 是写代码时最常用的集合类之一，看来大家也不是全都很了解。孤尽乘胜追击又抛出问题：JDK8中 HashMap 和之前 HashMap 有什么不同？

我知道 JDK8 中 HashMap 引入了红黑树来处理哈希碰撞，具体细节和源代码并没有仔细翻过，看来是时候对比翻看下 JDK8 和 JDK7 的 HashMap 源码了。

通过对比翻看源码，先说下结论：

HashMap 在 new 后并不会立即分配bucket数组，而是第一次 put 时初始化，类似 ArrayList 在第一次 add 时分配空间。

HashMap 的 bucket 数组大小一定是2的幂，如果 new 的时候指定了容量且不是2的幂，实际容量会是最接近(大于)指定容量的2的幂，比如 new HashMap<>(19)，比19大且最接近的2的幂是32，实际容量就是32。

HashMap 在 put 的元素数量大于 Capacity * LoadFactor（默认16 * 0.75）之后会进行扩容。

JDK8在哈希碰撞的链表长度达到TREEIFY_THRESHOLD（默认8)后，会把该链表转变成树结构，提高了性能。

JDK8在 resize 的时候，通过巧妙的设计，减少了 rehash 的性能消耗。

存储结构

JDK7 中的 HashMap 还是采用大家所熟悉的数组+链表的结构来存储数据。

JDK8 中的 HashMap 采用了数组+链表或树的结构来存储数据。

重要参数

HashMap中有两个重要的参数，容量(Capacity) 和负载因子(Load factor)

Initial capacityThe capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.

Load factorThe load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

Initial capacity 决定 bucket 的大小，Load factor 决定 bucket 内数据填充比例，基于这两个参数的乘积，HashMap 内部由 threshold 这个变量来表示 HashMap 能放入的元素个数。

Capacity 就是 HashMap 中数组的 length

loadFactor 一般都是使用默认的0.75

threshold 决定能放入的数据量，一般情况下等于 Capacity * LoadFactor

以上参数在 JDK7 和 JDK8中是一致的，接下来会根据实际代码分析。

JDK8 中的 HashMap 实现

new

HashMap 的bucket数组并不会在new 的时候分配，而是在第一次 put 的时候通过 resize() 函数进行分配。

JDK8中 HashMap 的bucket数组大小肯定是2的幂，对于2的幂大小的 bucket，计算下标只需要 hash 后按位与 n-1，比%模运算取余要快。如果你通过 HashMap(int initialCapacity) 构造器传入initialCapacity，会先计算出比initialCapacity大的 2的幂存入 threshold，在第一次 put 的 resize() 初始化中会按照这个2的幂初始化数组大小，此后 resize 扩容也都是每次乘2，这么设计的原因后面会详细讲。

hash

JKD8 中put 和 get 时，对 key 的 hashCode 先用 hash 函数散列下，再计算下标：

具体 hash 代码如下：

由于 h>>>16，高16bit 补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。

按照函数注释，因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且 JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。具体性能提升可以参考Java 8：HashMap的性能提升

put

put函数的思路大致分以下几步：

对key的hashCode()进行hash后计算数组下标index;

如果当前数组table为null，进行resize()初始化；

如果没碰撞直接放到对应下标的bucket里；

如果碰撞了，且节点已经存在，就替换掉 value；

如果碰撞后发现为树结构，挂载到树上。

如果碰撞后为链表，添加到链表尾，并判断链表如果过长(大于等于TREEIFY_THRESHOLD，默认8)，就把链表转换成树结构；

数据 put 后，如果数据量超过threshold，就要resize。

具体代码如下：

resize

resize()用来第一次初始化，或者 put 之后数据超过了threshold后扩容，resize的注释如下：

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.

数组下标计算： index = (table.length - 1) & hash ，由于 table.length 也就是capacity 肯定是2的N次方，使用 & 位运算意味着只是多了最高位，这样就不用重新计算 index，元素要么在原位置，要么在原位置+ oldCapacity。

如果增加的高位为0，resize 后 index 不变，如图所示：

如果增加的高位为1，resize 后 index 增加 oldCap，如图所示：

这个设计的巧妙之处在于，节省了一部分重新计算hash的时间，同时新增的一位为0或1的概率可以认为是均等的，所以在resize 的过程中就将原来碰撞的节点又均匀分布到了两个bucket里。

JDK7 中的 HashMap 实现

new

JDK7 里 HashMap的bucket数组也不会在new 的时候分配，也是在第一次 put 的时候通过 inflateTable() 函数进行分配。

JDK7中 HashMap 的bucket数组大小也一定是2的幂，同样有计算下标简便的优点。如果你通过 HashMap(int initialCapacity) 构造器传入initialCapacity，会先存入 threshold，在第一次 put 时调用 inflateTable() 初始化，会计算出比initialCapacity大的2的幂作为初始化数组的大小，此后 resize 扩容也都是每次乘2。

hash

JKD7 中，bucket数组下标也是按位与计算，但是 hash 函数与 JDK8稍有不同，代码注释如下：

Retrieve object hash code and applies a supplemental hash function to the result hash, which defends against poor quality hash functions. This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower bits. Note: Null keys always map to hash 0, thus index 0.

hash为了防止只有 hashCode() 的低 bit 位参与散列容易碰撞，也采用了位移异或，只不过不是高低16bit，而是如下代码中多次位移异或。

JKD7的 hash 中存在一个开关：hashSeed。开关打开(hashSeed不为0)的时候，对 String 类型的key 采用sun.misc.Hashing.stringHash32的 hash 算法；对非 String 类型的 key，多一次和hashSeed的异或，也可以一定程度上减少碰撞的概率。

JDK 7u40以后，hashSeed 被移除，在 JDK8中也没有再采用，因为stringHash32()的算法基于MurMur哈希，其中hashSeed的产生使用了Romdum.nextInt()实现。Rondom.nextInt()使用AtomicLong，它的操作是CAS的（Compare And Swap）。这个CAS操作当有多个CPU核心时，会存在许多性能问题。因此，这个替代函数在多核处理器中表现出了糟糕的性能。

具体hash 代码如下所示：

hashSeed 默认值是0，也就是默认关闭，任何数字与0异或不变。hashSeed 会在capacity发生变化的时候，通过initHashSeedAsNeeded()函数进行计算。当capacity大于设置值Holder.ALTERNATIVE_HASHING_THRESHOLD后，会通过sun.misc.Hashing.randomHashSeed产生hashSeed 值，这个设定值是通过 JVM的jdk.map.althashing.threshold参数来设置的，具体代码如下：