Java HashMap设计思想探究

最近本来想写一个HashMap相关的博客，捋一捋源码，算是对这两年开发经验的一个小考试。但是源码看着看着，博客写着写着发现HashMap的设计有一些不仔细思考可能不会理解的点。所以最终觉得写这么一篇博客，说一说我理解的HashMap的设计思想，代码基于JDK1.7和JDK1.8。
以下文章默认读者已经对诸如hash code，数组、链表、哈希表、桶之类的概念，以及HashMap的结构有一定的了解，否则一些我没有详述的部分可能会看不懂。

查找速度快，这是我们使用HashMap储存数据的原因，也是HashMap使用哈希表结构的原因：哈希表查找的时间复杂度是O(1)，而结构相似的数组（代表类如ArrayList）查找的时间复杂度是O(n)。因为哈希表在插入与查找之前，都对key进行了一次Hash计算，因此才能在查找时快速定位到元素（key-value组成的键值对）在数组中所处的位置——这是一种典型的用CPU计算资源换取查询效率的设计。
但单纯的哈希表并不完美，因为会面临哈希冲突。我们知道HashMap的哈希表确定元素位置的方式是用哈希值对数组长度取余，而两个不同的key虽然他们大概率哈希值不同（在hashCode()方法写得没有问题的情况下），它们对数组长度取余后的值却可能相同——只要两个哈希值相差整数个数组长度——此时两个元素被定位到了数组的同一个位置，也就是发生了哈希冲突。
为了应对哈希冲突，HashMap的设计者将数组中一个索引位置设计为一个容器而不是一个键值对。这个容器在JDK1.7中叫bucket-桶，在JDK1.8中叫bin-箱子，它们在概念上差不多，都是数组上同一个索引位置下所有键值对的集合，只不过JDK1.7和JDK1.8在实现上所采用的数据结构不完全相同，JDK1.7是链表，JDK1.8是链表+红黑树。下文中为了方便，将它们统称为“桶”。桶的出现使得数组发生了横向扩展，发生哈希冲突了也没有关系，往桶里放就行。下图分别是JDK1.7和JDK1.8中HashMap的结构：（图片来源见水印）


前面说了，在桶的具体实现上，JDK1.7的HashMap用的是链表法（chaining)，也就是将发生哈希冲突位置的元素组成一个链表。由于链表遍历的时间复杂度是O(n)，链表过长肯定会降低插入和查找的效率。但是我们需要首先讨论以下实际情况：

• 在哈希算法没有问题，哈希值分布得足够均匀的情况下，每个桶里元素的数量是符合泊松分布的，某个桶中元素数量特别多的概率其实是很低的（这点后面会说明），这也就意味着即使发生了哈希冲突，在插入和查找时需要遍历的链表长度其实不会特别长，至少相比数组的长度，链表的长度是很小的。比起遍历整个数组，遍历一条长度往往只有个位数的链表，其花费的时间资源是可以接受的——其实在这种情况下，数组+链表结构的HashMap已经趋于完善，没有多大的优化空间了。
• 如果哈希算法有问题，哈希值的分布不够均匀，发生哈希冲的概率会大增，链表的长度也会指数级增加，此时插入和查找效率也会剧烈下降。而JDK1.7的HashMap并没有对此种情况做专门优化。

原因可以这样描述：为实现得比较烂的hashCode()方法做一个兜底。如果被用作key的类其hashCode()方法实现得不够好，hash值不够分散，就会造成哈希冲突次数增加，链表长度过长，降低查找和插入效率。JDK1.8的HashMap将将链表改为链表 + 红黑树便是专门为此种情况而做的专门优化——只要你写的hashCode()方法不是烂得无可救药，你用JDK1.8的HashMap就不至于性能烂到不可接受。JDK1.8的HashMap类源码中有一段Implementation notes，里面详细介绍了在JDK1.8版本中对HashMap类进行重构时一些设计上的考量，以下是原文节选及我做的简单翻译：

This map usually acts as a binned (bucketed) hash table, but when bins get too large, they are transformed into bins of TreeNodes, each structured similarly to those in java.util.TreeMap. Most methods try to use normal bins, but relay to TreeNode methods when applicable (simply by checking instanceof a node). Bins of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. However, since the vast majority of bins in normal use are not overpopulated, checking for existence of tree bins may be delayed in the course of table methods.
Tree bins (i.e., bins whose elements are all TreeNodes) are ordered primarily by hashCode, but in the case of ties, if two elements are of the same “class C implements Comparable”, type then their compareTo method is used for ordering. (We conservatively check generic types via reflection to validate this – see method comparableClassFor). The added complexity of tree bins is worthwhile in providing worst-case O(log n) operations when keys either have distinct hashes or are orderable, Thus, performance degrades gracefully under accidental or malicious usages in which hashCode() methods return values that are poorly distributed, as well as those in which many keys share a hashCode, so long as they are also Comparable. (If neither of these apply, we may waste about a factor of two in time and space compared to taking no precautions. But the only known cases stem from poor user programming practices that are already so slow that this makes little difference.)

这个Map一般是由一个容器化的哈希表组成（原文：binned (bucketed) hash table），当某个容器中的元素过多时，这个容器就会转变成由树节点组成的容器，其结构类似于java.util.TreeMap中的bins。大部分的方法会尝试使用普通容器，但是通过检查节点的类型，如果里面已经是树节点，则会适用树节点的方法。由树节点组成的容器在使用上就跟普通容器一样并且可以从普通容器转化而来，但是树节点组成的容器在内部被放入过多元素时仍然可以保持较好的查询速度。当然，因为绝大多数的容器在正常使用时都不会被放入太多元素，在哈希表的方法中，检查树化容器是否存在的行为可能会被延迟。
树化容器（比如那些所有元素都是树节点的容器）中的元素主要按照hashCode排序，但是在两个元素属于同一个实现了Comparable接口的类，那么将会使用compareTo()方法来决定它们的顺序（我们比较谨慎的使用了反射来确定它们的泛型——详见comparableClassFor()方法）。引入树化容器而增加的复杂度是值得的，即使key们没有独特的hashCode或者不能相互比较大小（没有实现Comparable接口），在最坏的情况下也能提供O(log n)的查找效率。因此，在意外或者恶意的使用了实现得很糟糕的hashCode()方法，使得返回的hashCode非常不均匀或者很多key返回相同的hashCode，只要这些key可以直接比较大小，那么性能的下降就不至于太过惨烈。（如果hashCode()方法实现得很糟糕并且同时key们也无法直接比较大小，相比于什么也不做（也就是JDK1.7的实现）我们将会多浪费2倍的时间和内存。不过会发生这种事情唯一已知的情形是来自于使用者糟糕的编程实践，在这种情况下，原本的实现方式就已经很慢了，再慢一点也没差。）

HashMap的设计者已经把自己的意图展现得非常清楚了：
HashMap是提供给开发者的基础容器，无法限制使用者到底用什么类作为key。在JDK1.7的HashMap中，如果某个比较菜的程序员在编程时用了某个hashCode()方法实现得很糟糕的类作为HashMap的key——比如返回的hashCode值只在1~10000之间变化而不是和正常的hashCode一样覆盖整个int取值范围——那么HashMap中的元素必然会在一部分桶上聚集。如果HashMap里面的元素数量一多，比如几十万个，那么插入/查找的效率将会灾难性地降低（从理论的O(1)降到O(n)，如果每个链表长度是几万，等于效率降低了几万倍）。
而在JDK1.8的HashMap中，设计者为这部分菜鸟程序员做了兜底：在链表过长时，会被转化成红黑树，而红黑树的查找效率是O(log n)，这一下就把效率的降低程度从几万倍缓解到了几十倍（ l o g 2 500000 ≈ 18.9 log_2 500000approx18.9 log2​500000≈18.9）。

从上面的分析，我们可以侧面了解到：其实JDK1.8对HashMap的重构只是提高了查找效率的下限，但对于高手程序员来说（比如这篇文章的读者），一般都是使用String作为HashMap的key吧？我相信你们不会犯上述错误，那么对于我们来说，其实JDK1.8的HashMap并没有为我们带来多少查找效率上的提高。

顺便提一下，如果一个类要作为HashMap的key，那么这个类必须重写equals()和hashCode()方法，这是一个基本守则。如果不重写，那么用这个类作为key导致结果将不是效率的降低，而是彻底的错误——你根本没法正确地从HashMap中存取元素。这其中的原理网上很多文章有写，我就不赘述了。

注意这里说的“效率没有提高”并不是指的红黑树的查找效率相比链表没有提高，而是说，在正常使用的情况下，HashMap中链表转成红黑树的概率极低，在绝大部分情况下，发生哈希冲突时，HashMap仍然是遍历链表而不是在查询红黑树，进而在统计上，JDK1.8的HashMap并没有比JDK1.7的HashMap有效率上的提升。
那么，在正常使用的情况下，链表转成红黑树的概率是多少呢？——答案同样在Implementation notes中

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) /factorial(k)). The first values are:
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million

由于树节点的大小大约是普通节点的2倍，我们只会在容器中包含足够多的节点时才使用它们（TREEIFY_THRESHOLD）。并且当容器变得太小时（因为remove或者扩容）它们又会被转化回普通容器。在使用分布得很好的（well-distributed）用户自定义hashCode时，树状容器是极少使用的。事实上，在随机的hashCode下，在扩容阈值为默认的0.75时，容器中节点数量的概率符合参数为0.5的泊松分布，尽管由于扩容粒度的问题，使得结果有很大的方差。不考虑方差的情况下，链表长度k和其出现概率的关系满足这个公式：(exp(-0.5) * pow(0.5, k) /factorial(k))

上面的公式写成更易读的形式是这样的：

① P(X=k)= e − 0.5 × 0. 5 k k ! e^{-0.5} times 0.5^kover k! k!e−0.5×0.5k​ （k代表一个容器中节点的个数）

Implementation notes已经为我们做了计算：当k=8时， P ( X = k ) ≈ 0.00000006 P(X=k)approx0.00000006 P(X=k)≈0.00000006，即容器中有8个节点的概率只有1亿分之6，而JDK1.8的HashMap只有在链表长度>8时才会转化为红黑树（当然也可以说设计者专门选了8这个值以确保在正常情况下只有极低的概率会被转化成红黑树）。正因为HashMap中的链表转成红黑树的概率低于千万分之一，我才会说JDK1.8中HashMap的红黑树设计对查询效率几乎没有影响。当然，以上结论永远离不开一个前提——作为key的类有一个写的足够好，哈希值分布得足够均匀的hashCode()方法。

接下来，我们再来分析一下上述公式是怎么来的。不了解泊松公式的读者，可以先看下这两篇文章：
如何理解泊松分布？
泊松分布和指数分布：10分钟教程

我们知道，泊松分布的概率密度函数是这样的：
② P(X=k)= e − λ × λ k k ! e^{-λ} times λ^kover k! k!e−λ×λk​ 公式中的参数λ是单位时间(或单位面积)内随机事件的平均发生次数，k代表事件发生的次数。在我们的问题中，λ就是元素落入某个容器中的概率，而k就是容器中元素/节点的个数。
对比公式①与公式②，结合注释，我们可以知道，HashMap的设计者在计算概率时，是将λ设为了0.5——为什么在负载因子等于0.75时，元素落入某个节点的概率是0.5呢？
一开始我也百思不得其解——假设数组长度为n，每次将一个元素放入数组中的随机位置，元素落入某个位置的概率是 1 n 1 over n n1​，负载因数为0.75时，假设进行了0.75n次实验，0.75n次也是在数组长度n下可以进行的最多次实验了，因为超过这个数值就会扩容。此时某个位置上元素数量的期望应该是：
1 n × 0.75 n = 0.75 {1 over n} times 0.75n = 0.75 n1​×0.75n=0.75
按照上面的计算，扩容阈值是多少，则λ就应该是多少。究竟为什么在Implementation notes的计算中，扩容阈值是0.75时，带入的λ是0.5呢？
我在网上又查找了一番，最后找到这篇文章：HashMap的泊松分布，下面照片中的公式给了我不少启发，让我明白了前面的计算问题在哪里。

下面我们重新来梳理一下λ取值的过程：
首先明确λ的含义是单位时间(或单位面积)内随机事件的平均发生次数，或者说数学期望。对若干次独立随机事件来说，这个发生次数就等于实验次数 × times ×每次事件发生的概率。
对于一个数组长度为n的HashMap来说，我们最多能进行0.75n次实验，也就是进行0.75n次put操作。因为第0.75n+1次实验会触发扩容——扩容的条件除了达到扩容阈值之外，还要满足发生Hash冲突，为了简化，我们假设第0.75n+1次实验一定会发生Hash冲突——我们可以将这0.75n次实验分前 0.75 n 2 0.75nover2 20.75n​次实验和后 0.75 n 2 0.75nover2 20.75n​次实验。在前 0.75 n 2 0.75nover2 20.75n​次实验中，数组的长度是 n 2 nover2 2n​，每个元素落入数组中某个位置的概率为 2 n 2over{n} n2​；在后 0.75 n 2 0.75nover2 20.75n​次实验中，数组的长度是n，每个元素落入数组中某个位置的概率为 1 n 1over{n} n1​。于是，我们可以很简单地得到在前后两组实验中，λ的值分别为：
2 n × 0.75 n 2 = 0.75 {2over{n}}times{0.75nover2}=0.75 n2​×20.75n​=0.75 和 1 n × 0.75 n 2 = 0.75 2 {1over{n}}times{0.75nover2}={0.75over 2} n1​×20.75n​=20.75​，
求均值之后结果便是 0.75 2 + 0.75 4 = 9 16 = 0.5625 ≈ 0.5 {0.75over 2} + {0.75over 4} ={9 over 16} = 0.5625 approx 0.5 20.75​+40.75​=169​=0.5625≈0.5
不说计算过程非常不太严谨，仅就最后将0.5625向下取整保留一位小数为0.5这一步，就可以知道最终得到的λ的取值是非常不精确的，这也是为什么HashMap的设计者在Implementation notes里会说在负载因子为0.75时，λ的取值为0.5，但是会有很大的方差:

Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity

但是实际上，由于λ在这里的作用只是用来简略计算发生Hash冲突后链表长度与发生概率的关系，所以这里λ等于0.4、0.5或者0.6影响都不大，不会影响最终的结论——在用作key的类其hash算法设计良好，hash分布均匀的情况下，在某个节点上链表的长度达到8的概率只有千万分之一的量级——HashMap的设计者在前面做了那么多说明，又进行了泊松分布的计算，最终目的就是为了说明将链表转成红黑树的长度阈值设为8的合理性。

最后，总结一下HashMap的整个设计思路

1. 使用Hash表作为HashMap的主体——HashMap的主体结构是数组。但是单纯的Hash表有Hash冲突的问题
2. 使用横向扩展数组节点的方式解决Hash冲突——HashMap变成了数组+链表的结构
3. 确定一些实现上的细节：数组初始长度、扩容倍数、扩容阈值等——最终为了内存效率、rehash的便利，将数组初始长度定为16，扩容倍数为2，扩容阈值定为了不大也不小的0.75
4. JDK1.8的HashMap为了应对实际使用中出现的问题：用作key的类hash算法设计不良引起Hash冲突剧增，链表长度过长，进而造成的效率降低，为HashMap打了一个补丁——当链表长度>8时，将链表转成红黑树。

为了说明取8这一链表转红黑树阈值的合理性，作者特意在Implementation notes里进行了解释：在hash算法设计良好的前提下，链表长度的分布概率符合泊松分布，经计算，链表长度达到8的概率只有千万分之一。换言之，如果我们用String做HashMap的key，在绝大部分情况下HashMap中的链表都不会转成红黑树，JDK1.8打的这个补丁可以等同于不存在。而如果我们用自己写的类做HashMap的key，如果不幸这个类的hash算法写得不够好，便会有大概率在某些节点出现链表长度远大于8的情况，这时JDK1.8的补丁便可以发挥作用，将链表转成红黑树，让HashMap的查找效率不至于降低到太差的地步（链表时是O(n)，红黑树时是O(log n)的时间复杂度）