Walt You - 知行合一

Java 8 中 HashMap的改进点

2019-05-16

Java 8 中,对 HashMap 做了一些优化,就是会在链表过长的时候,将链表转为红黑树。 来仔细看看是怎么改的,以及为什么这么改。


前言

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)。

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

  1. 链表的长度大于等于 8
  2. 当前 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 才会不辞辛苦的变来变去。


Content