我是程序员，我有强迫症，HashMap我要面到100分！

“小冤家，你干嘛，像个傻瓜，大大地眼，看着我，眨巴眨巴……”。不是作者“戏精附身”，作者想带你找回上篇文章的余温。

这张图表达的是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思想的代码片段，而且只考虑了桶中元素为链表的情况。面试的时候，更多的知识点可以通过面对面交流的方式补充给面试官。