前言

Java 8 提出了很多新特性，比如stream、lambda、接口的 defualt 方法、Optional等。同时也对常用的集合做了优化，如今天要谈的 HashMap。

链表时代

Java 8 之前的 HashMap，其实就是一个 Node 数组，数组中存放着一个链表的头部元素或者为空。链表的设计初衷是为了存放位置冲突的 Node。可以把 Node 看作是 <key, value> 对。

为什么会位置冲突呢？这就要了解 HashMap 是怎么put <key, value> 对。当 put 某个 <key, value> 对时，它会计算 key 的 hash 值，然后对当前 HashMap 的长度取模，最后得到这个 <key, value> 对在数组中的位置。用代码来描述如下：

int index = hash(key) / map.size

有时候不同的key，会产生相同的hash值，又有时候不同的key，虽然hash值不同，但是对当前 HashMap 的长度取模后，就一样了。那么必然有可能有多个 <key, value> 对，会得到相同的下标。这个时候该怎么办呢？

Java 8 之前的做法，就是把所有的键值对当作是一个链表中的一个node。位置冲突后，直接两行代码解决冲突：

inputNode.next = map_array[index]; 
map_array[index] = inputNode.next;

新来的 inputNode 不关心本来这个位置上有多少个node，它一来，直接当老大，指定自己的next等于原有链表的头部节点，然后把自己放在 map 的 array中。

这个动作的学名就叫做“头插法”。因为它都是直接将新增节点插入链表的头部。这个方法的写入速度很快，时间复杂度为O(1) ，但是查找速度就不行了，时间复杂度为 O(n)。

所以如果假设map长度为 m，放入元素数量为 n，那么get 方法的时间复杂度就是 O(n / m)，因为假设所有元素可以均匀分布，那么数组的每一位上的链表长度应该为 n/m 。

引入红黑树

经过上面的回忆，可以知道链表的查询的时间复杂度太高，所以在 Java 8 中，引入了链表长度过长时将其转变为红黑树的操作。

什么是红黑树？

是个约束条件很多的树。具体定义可以自行搜索学习，比如这里，我们这里只关心它的时间复杂度。

因为许多前人的努力，构建出了红黑树，使得它可以在 O(logN) 的时间内完成查找、增加、删除等操作。

这比起链表的O(n) 查找复杂度快了不少。

什么时候发生转变？

链表变为红黑树

参考 Java 8 HashMap 的源码，可以看出在put的时候，先判断数组里放的是链表还是红黑树。

如果是红黑树，直接insert 这个 Node 到树中即可。如果是链表，就循环找到这个链表的最后一个元素，同时也会记录这个链表的长度，接着把这个 Node 放在这个链表的最后。

这就和 Java 7 的头插法不一样了，而是“尾插法”，这一步是为什么呢？我觉得其实是因为头插法虽然写入快速，但是它并不能获取当前链表的长度。那么在之后要判断是否需要转为红黑树时，就不得不再遍历一遍链表来获取长度，不如一开始就遍历它。

在这个 Node 放在链表的末尾之后，会新增一个判断条件，看看链表的长度是否大于等于 8 ，如果大于等于8，就调用链表转树的函数，名为 treeifyBin。

然后 treeifyBin 会先判断一下当前 map 的长度是否小于64，如果是，那就 resize map，也就是扩容，否则才进行链表转红黑树的操作。加上这个条件，也是为了避免有太多的 nodes 在同一个位置上（jdk里叫做 bin）。

总结一下，其实链表变红黑树有两个条件：

链表的长度大于等于 8
当前 map 的长度大于64

红黑树变为链表

map有put方法，也有remove方法。那么某个位置上的 node 数量会增加，也会减小。但是在remove node的时候，红黑树是不会往链表上转的。 （我一开始是这样子以为的）

看了源码之后，发现只有在重新 resize map 的时候，才会取判断红黑树的 node 数量是否低于等于6，如果低于等于6，那么树就会重新退化为链表。

问题与思考

看到这里，不禁想问，为什么要转来转去呢？这不是浪费时间吗？为什么不从头到尾采取单一数据结构呢？为什么选择长度大于等于8，链表变树，长度小于等于6 ，树变链表呢？

其实就是因为一个词：效率。

回归到链表和红黑树这两种数据结构上，链表的平均查询时间复杂度为 N / 2，红黑树为 logN。注意平均查询时间复杂度与时间复杂度是两个概念，不要混淆，参考这里。

所以套用回那两个数字 8 和 6，就可以发现，树变链表时，平均查询时间复杂度为 6/ 2 = 3 ；链表变树时，平均查询时间复杂度为 log 8 = 3。也就是说长度大于等于8，红黑树平均查询时间复杂度比较低，长度小于等于6，链表的平均查询时间复杂度比较低。所以 Java 8 中的 HashMap 才会不辞辛苦的变来变去。

Java 8 中 HashMap的改进点

前言