“小冤家,你干嘛,像个傻瓜,大大地眼,看着我,眨巴眨巴……”。不是作者“戏精附身”,作者想带你找回上篇文章的余温。
这张图表达的是jdk7中HashMap扩容存在的问题。“环形链表”产生的根本原因是,扩容时,新链表采用头插入方式,同时线程间的堆内存是共享的。
hash桶中头结点指向的始终是最后写入的Node节点,导致Node节点的锚点(next)倒置。中途回来的线程,根据之前的锚点,访问现在的Node节点(没有用发展的眼光看问题),导致线程间工作脱节。
关于hash桶、Node节点之类的数据结构,其组织形式就像一颗农作物,好吃的西红柿。
本篇文章主要聚焦的问题,Java8扩容机制,以及手写HashMap方法。
Java8是怎么扩容的?
Java8扩容使用了一个数学诡计,扩容后的hash桶位置,等于扩容前的位置加上原hash桶大小,或者不变。
一起看图梳理这个结论。
我们重点来看图中第2步,取模操作获取桶的位置。历史HashMap写入Node节点时,执行Hash& (length-1)操作,获得的二进制数据为“0110”,即为十进制的6号桶。
扩容后,我们按照重新hash的方式来推演一下。HashMap长度翻倍,二进制表示多了一个bit位,例子中该bit位为“1”。执行Hash& (2*length-1)操作,该bit位的执行结果为“1”。
执行结果十进制来表示,那么新的hash桶的位置,等于历史的hash桶的位置加上历史桶的大小oldCap
,例子中为6+16=32号桶。
经过推演,我们已经看到了这个数学诡计,秘密就在于扩展了一位bit位。可以不用重新hash计算,直接判断bit位吗?可以。
Java8在HashMap扩容时,不再重新计算hash值,而是基于原来的位置,直接判断扩展出的bit位。其为1时,新位置等于原位置+历史桶的大小(oldCap),为0时仍然为原来的位置。
源码如下,其中oldCap,即历史桶的大小,它一般为2的n次方。
还可以看到一个细节,扩容时,不再使用头插入法了,改为使用尾插入法,这样也就避免了Java7中“环形链表”的问题。
手写HashMap的结构
先来回顾下我们的HashMap精髓。
黄色标注的是HashCode,绿色标注的是桶的大小,红色标注的是Hash值。
定义Node节点。
定义一个hash算法。
put一个数据。
get一个数据。
我们这里只是简单的实现一个具有HashMap思想的代码片段,而且只考虑了桶中元素为链表的情况。面试的时候,更多的知识点可以通过面对面交流的方式补充给面试官。
领取专属 10元无门槛券
私享最新 技术干货