走进Java Map家族 (1) - HashMap实现原理分析
在java世界里，有一个古老而神秘的家族——map。从底层架构到上层应用，他们活跃于世界的每一个角落。但是，每次出现时，他们都戴着一张冷硬的面具（接口），深深隐藏着自己的内心。所有人都认识他们，却并非每个人都理解他们。在这个热闹的世界中，map们活得光荣却孤独……这个系列博文，就将尝试透过接口的伪装，走进每个家族成员的内心世界，聆听家族内部的动人传说……
注：各种map在不同的jdk中有不同的实现。如无特别声明，本文只针对当前（2019年3月）最新的openjdk(13-ea)的实现
一、从hashmap开始
好了，上面都是扯淡，目的是为了让气氛更加尴尬……
第一个介绍的map成员是hashmap，因为它应用最广，实现也最简单——简单到我一直在纠结要不要单独为它写一篇文章。代码在这里
hashmap将键值对存储于若干个bin中。所谓bin（或者叫bucket、桶），是一个可以保存多个键值对的数据结构。初始状态下，一个bin就是一个链表。具体代码如下
static class node<k,v> implements map.entry<k,v> {
final int hash;
final k key;
v value;
node<k,v> next;
}
transient node<k,v>[] table;
node类是链表的元素。变量table是一个链表的数组，或者说是bin的数组。hashmap所有的数据就保存在table中。（或许你注意到了transient关键字。hashmap并不直接序列化table变量，而是重写了writeobject和readobject处理数据的序列化）
当向hashmap中put数据时，首先计算key的hashcode，根据hashcode找到它所属的bin，然后将键值对放入bin中，也就是插入到链表的末尾。可见，有相同hashcode的两个key，一定会放入同一个bin中，这种现象叫hash冲突（hash collision）。而get的过程也一样，计算key的hashcode并找到对应的bin，然后在bin中搜索包含相同key的node。
以上是hashmap的基本实现原理。
二、扩容(resize)与树化(treeify)
可见，put和get消耗的时间与链表长度是o(n)的关系。如果数据量太大，每一个链表都会很长；或者运气太差，大部分数据都集中于一个bin中，这时hashmap的性能就会迅速下降。怎么办呢？
有两种思路，要么是缩短链表长度，要么是提高bin的搜索速度。hashmap的具体策略也是从这两方面入手。每次put数据时，都记录map中整体的数据量，以及链表的长度，然后
（1）当整体数据量超过bin的数量的3/4时，增加bin的数量，这个过程叫扩容(resize)。扩容后，各条数据都要重新计算它属于哪个bin，这叫做rehash。这样，有些数据移动到新的bin中，各个bin的链表长度就会缩短。
（2）当某个链表很长（超过7），而bin的数量很少（小于等于64个），也会扩容，以缩短链表。
（3）当某个链表长度超过7，而bin的数量大于64个，就将这个bin由链表转变为红黑树，提高搜索速度。这个过程叫做树化(treeify)。树化是在jdk 1.8才实现的。
为什么不一开始就使用树呢？个人理解，这是出于时间-空间的综合考量。当数据量很小时，树的搜索速度并不明显优于链表，而占用的空间却比链表多，因此初始选择是链表，遇到性能瓶颈也优先选择扩容。
而当bin足够多时，继续扩容就会出现问题：
（1）继续扩容也会增加空间占用（而且占用的是连续空间。还记得table是一个数组吗？）。相比于树化，扩容不再具有空间上的优势。
（2）resize之后要对所有的数据做rehash，当数据量很大时，rehash的性能负担远高于对单个bin做树化。
可以说，扩容改变所有数据的分布方式，是一种针对整体的优化方案；树化只改变单个bin的结构，是针对局部的优化方案。如果bin很多却依然存在很长的链表，说明整体优化方案对于某个bin不起作用，这可能是hashcode分布不均匀导致的。继续扩容徒然增加空间，效果却不见得理想。这时，就该采用局部优化方案，也就是树化了。
以上纯属个人理解与猜测，仅供参考。
最后说一点，bin的数量并非到了64之后就不再增长了。根据策略（1），只要整体数据量足够多，就会扩容。不过，扩容也不是无限的，毕竟数组太大了也会造成问题。bin的最大数量是2的30次方，或者写成1<<<30。
三、hashcode与扩容策略
如何根据hashcode找到数据所属的bin？每次扩容增大多少？如何rehash？这几个问题互相关联。
最简单的方案当然是取余。假设bin的数量为n，key的hashcode为h，那么key所属的bin就是第h%n个。而扩容可以任意增加bin的数量。比如扩容后的bin有n+m个，rehash时某个key所属的bin是第h%(n+m)个。
这种方法可以实现功能，但性能不好，rehash阶段会非常耗时。而且有可能两个bin中的数据被rehash到同一个bin中，从而构建了一个比以前更长的链表。而openjdk采用的方法则颇具技巧性，充分利用了高效的位运算。
/****开始说正事的分割线****/
openjdk要求bin的数量必须是2的整数幂，即1<<<n个（乘以2和左移一位等价，乘以n个2和左移n位等价）。初始状态n=4，即bin的初始数量是2的4次方，或者是1左移四位的结果，也就是16个。
有了这个要求，许多事情就变得简单了。
如何resize呢？为了保证上述条件成立，每次扩容，bin的数量都变为2倍。如果当前bin的数量为1<<<n，扩容一次后bin的数量是1<<<(n+1)。
一个key应该属于哪个bin呢？如果key的hashcode是h，bin的数量是b=1<<<n，则key所属的bin是第h^(b-1)个。也就是截取了hashcode最后的n位，如下图所示
这种计算bin的方式与取余的结果实际是相同的。但是它利用了位运算，效率高于取余。而且这种方式对rehash很友好。
扩容之后，bin的数量是b'=1<<<(n+1)=b<<<1 。rehash前，key所属的bin是b1=h^(b-1)，它是hashcode截取后n位的结果；rehash之后，key所属的bin是b2=h^(b'- 1)，他是hashcode截取后n+1位的结果。可见，rehash前后的差异只在hashcode的第n+1位，也就是h^b'的结果。因此有
（1）如果h^b'==0，则rehash后这个key的位置不变
（2）如果h^b'==1，则rehash后这个key所属的bin是b2=b1+b。也就是将b1的第n+1位由0变为1
整个rehash过程，全部使用位运算以及一次简单的加法运算，保证了最高效率。而且两个bin的数据不会rehash到同一个bin中，也不会把数据rehash到一个扩容前就存在的bin中，保证了所有的bin在扩容后都不可能变得更长。
最后再说一个问题，hashcode如何计算？方法如下
static final int hash(object key) {
int h;
return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
}
将hashcode()方法的结果的高16位与低16位做and运算。为什么不直接用hashcode()方法的结果呢？openjdk的解释是，开发者可能用double做为key，如果各个浮点数之间差别很小，那么它们的低位将相同。而bin的位置是由hashcode的低n位决定的。这种情况下，大量的数据将进入同一个bin，发生大量hash冲突，严重影响性能。于是，openjdk最终选择了高位低位混淆的方案。据说，这种方案得到的hashcode满足泊松分布（虽然我不知道为什么会满足），分布很均匀。
四、关于树的二三趣事
比起链表，红黑树更复杂，也要处理更多的问题和细节。可能这就是java拖到1.8才实现树化的原因吧。许多关于树的问题并不重要，不影响整体思路，但细细品味很有意思。所以在最后写上一些。
（1）是一棵树，也是链表
树化后，新生成的树其实保持着原有链表的结构和顺序。它既是树，也是链表。树的节点用类treenode表示，贴一段treenode的声明
static final class treenode<k,v> extends linkedhashmap.entry<k,v> {
treenode<k,v> parent; // red-black tree links
treenode<k,v> left;
treenode<k,v> right;
treenode<k,v> prev; // needed to unlink next upon deletion
boolean red;
}
treenode间接继承自链表节点类node，所以它也是链表节点。看到声明中的prev了吗？它不仅是链表，还是双向链表。
这么做意义何在呢？首先是方便遍历，我们大概都写过类似的代码
map<integer, string> m = new hashmap<>();
...
iterator<entry<integer, string>> it = m.entryset().iterator();
while(it.hasnext()) {
it.next();
}
iterator的底层就是沿着链表的顺序遍历的。遍历链表，比遍历一棵树要高效得多。
然后，是方便逆树化(untreeify)。链表太长了会树化成一棵树。可树中的数据量可能因为resize或者remove而减少，数据太少了，树就会逆树化成一个链表。因为链表结构没有丢，逆树化就非常简单了。
（2）根节点在哪？
树的节点类treenode是链表节点类node的子类。因此，树化不用改变table变量的类型
transient node<k,v>[] table;
数组里的node，我们称它为首节点（first node）。它可能表示链表，也可能表示树。如果是链表，首节点当然就是头节点。可如果是树，首节点是哪个节点呢？根节点(root)吗？不一定。
大部分情况下首节点都是红黑树的根节点，因为每次改变树的结构时，都会调用下面的movetofront方法将根移动到table数组里
1 static <k,v> void moveroottofront(node<k,v>[] tab, treenode<k,v> root) {
2 int n;
3 if (root != null && tab != null && (n = tab.length) > 0) {
4 int index = (n - 1) & root.hash;
5 treenode<k,v> first = (treenode<k,v>)tab[index];
6 if (root != first) {
7 node<k,v> rn;
8 tab[index] = root;
9 treenode<k,v> rp = root.prev;
10 if ((rn = root.next) != null)
11 ((treenode<k,v>)rn).prev = rp;
12 if (rp != null)
13 rp.next = rn;
14 if (first != null)
15 first.prev = root;
16 root.next = first;
17 root.prev = null;
18 }
19 assert checkinvariants(root);
20 }
21 }
代码涉及到很多细节，只想了解基本思路的话，无需都看懂。但请注意第8行，root被放到table中。这时，根节点就是首节点了。
但是，有一个例外情况，就是在iterator中remove一个数据时
map<integer, string> m = new hashmap<>(); ... iterator<entry<integer, string>> it = m.entryset().iterator(); it.remove();
为什么呢？注意movetofront方法的第10-17行，改变了一些节点的next和prev指针，也就是改变了链表的顺序。因为root节点必须同时是链表的头节点。但是，（1）中说过，iterator是靠链表遍历的，因此它不能随便改变链表的顺序，也就不会移动root。
这里需要多说一句，虽然单个bin中的数据构成链表，但不同bin的数据却没有联系，而且moveroottofront还会改变链表顺序。因此，hashmap不是一个有序的数据结构。
（3）树中的数据如何比较
红黑树中的数据必须是可以比较的。那么hashmap的树如何比较呢。比较顺序如下：
a. 首先，比较key的hashcode；
b. 如果hashcode相同，检查key是否是comparable的。是的话，直接比较key；
c. 如果key不是comparable的，或者两个key比较结果相同，则比较两个key各自的类的字符创，即 key.getclass().getname()//看看你把jdk逼成什么样了 ；
d. 如果还是相同，就比较两个key的system.identityhashcode。
可见，从第三步起，事情就变得莫名诡异起来了。这也说明了，使用hashmap时，key最好是comparable类型的，对性能有益。
五、最后吐个槽
本文是一篇薄码文，贴的代码很少。因为大多数代码比较长，又涉及诸多细节，不好看也无益于理解整体思路。
但是，从少数的代码中大概可以体会到，openjdk的代码质量真的不高。随处可见魔幻的变量声明和鬼畜的代码格式，就是照着写业务代码有可能会被打死的那种。学习jdk源码的主要目的是了解细节，方便开发。如果抱着参考优秀代码的目的，那你算来错了地方。
当然，这种底层的*，也许开发者更多考虑的是性能和可靠性，至于可读性或许并不那么重要。
上一篇： “但使龙城飞将在，不教胡马渡阴山”，飞将军李广其实没那么伟大！
下一篇： 微信小程序实现页面浮动导航