前言

写这篇文章的目的是因为我大学四年的室友，龙哥在培训java，刚好最近学习HashMap，于是我写一篇文章来模拟他以后面试被问到HashMap的场景；另外就是因为HashMap的使用确实广泛，深受面试官的喜爱，大厂的面试官也有很多会用HashMap来考察你的基础到底如何。

面试经过

**面试官：**我们开始吧，看发型就知道是老程序员了，自我介绍一下吧。

**龙哥：**我叫龙哥，刚过完三十大寿。平时喜欢打篮球，优势是身体好，可以996。

**面试官：**嗯，还不错嘛。都30了，集合框架肯定熟悉吧，我们先从HashMap开始吧，简单的说一下内部的数据结构是怎么样的吧？

**龙哥：**大航子果然没有骗我，HashMap果然是开头菜，幸好我连夜让他给我培训了一番（内心狂喜中…），咳咳，HashMap嘛，在jdk7是数组+链表，jdk8数据结构做了升级，变成了数组+链表+红黑树了。

**面试官：**哦？这傻小子笑啥呢，，，看我探探你的底。嗯，那你说说为什么这么设计，以及jdk8为什么要做出这种升级呢？

**龙哥：**是这个样子的，Map这种集合容器，最主要的应用就是想通过一个key最快的时间找到对应的value，事实上这个时间复杂度接近为O(1)，那么怎么样才能实现这么快的速度呢？于是就引入了数组，数组可以理解为内存中一块连续的内存空间，且每一小块空间都有自己的索引，通过这个索引就能直接找到对应空间的值。

那么是想一下，我通过某种算法，可以直接把key和数组中的某个索引对应上，我放也放到这个索引里面，取也直接取这个索引去取，是不是依赖数组的特性，我就可以用O(1)的时间复杂度快速定位到我想要的值了。

**面试官：**嗯嗯嗯，有点意思，那链表和红黑树又是怎么回事？

龙哥：瞧给你急的，猴急猴急的，我接着说。在把key映射成数组索引值这件事情上，期望的不同的key映射到不同的数组索引值中，但是天不遂人愿，就比如我之前励志想成为优秀的数学老师，奈何教育减重，，，咳咳，远了、远了，继续哈。但是天不遂人愿，总有可能两个key好巧不巧就映射成了同一个数组索引值，这就是哈希碰撞，那么碰撞之后就有两种情况了，一是同一个key，我就要把原有的key的值覆盖掉，二就是真的是好巧不巧，两个key算出来的真就是一样的，那就只能把两个key和value放到同一个数组索引的内存里面，也就自然而然形成了链表，当然，如果碰撞的越来越多，这个链表就会越来越长，长。

**面试官：**咳咳，禁止开车，好好说。

**龙哥：**不是说链表过长么，于是，红黑树就出来了，就是解决jdk7中，链表可能过长的情况。那么为什么红黑树就能解决呢？要从链表和红黑树的查找效率说起。链表这种数据结构是不需要连续的内存空间的，内部通常是持有了下一个节点的引用，所以，链表要查询出某一个元素，就要从头节点开始查，不是的话，再去看next是不是，直到next为null才能确定整条链表没有我想要的元素，在最坏情况下，链表的长度是n，就是遍历n次才能找到元素，所以，链表的时间复杂度为O(n)。

这种的查询速度如果数据多了是不可以容忍的，要知道HashMap这个工具用的地方有多少，所以jdk8做出了优化，如果链表的长度大于了8，达到了9，就变成红黑树，当然还要满足整个hash表中的元素达到了64，之所以条件比较苛刻，是因为链表转数组本身就很耗性能，不到万不得已，万万使不得啊。红黑树这种数据结构首先是二叉搜索树，二叉搜索树就满足了查找的时间复杂度是O(lgn)，是一种折半查找，折半查找的效率就很恐怖了，一次排除一半的数据，就算你有100W数据，查找固定的数，也只需要20次，就是这么拽，而红黑树在有二叉搜索树的查询效率的前提下，又保证了树的平衡。所以链表在上述情况下会进化成红黑树，当然，又进化也有退化，退化的节点就是同一个哈希桶中的元素数小于6，就会从红黑树变回链表。之所以中间留了个7，就是为了防止频繁的树化、链表话、树化、链表化。

面试官：（我天，这算是这几天来最会说的了，大航子不来，恐怕没人能限制的了他了）那你说下，这个key是怎么转换成数组索引的呢？

龙哥：（这个问题，嘿嘿嘿，show，time），我们都知道在java中所有的对象继承自Object，而Object类里面有一个方法。

这个方法可以返回一个32位的数字，当然，这个32位的数字是不能直接去当数组的索引的，因为一般情况下不会有那么大的数组。所以这个hashcode肯定是要经过某种转换，如果数组的长度是16的话，应该转换成为的值在0到15之间，才能保证落在数组的某一个索引值里面。这种的实现方式，常规的能想到的是取模。但是我们都知道，在计算机中，位运算的效率是最高的，于是，这个公式是这个样子的 (n - 1) & hash ，这种运算的结果和取模不一定相同（有很多博客说相同是错误的）。至于这么做为什么就能达到和取模一样的效果的呢？我们还是拿16举例。

再加上位运算的速度相当快，所以HashMap是采用这种方式寻找数组索引的。好吧，你问我具体快多少？我曾经对相同的100W样本做过取模和位运算，大概快了几十倍把。

**面试官：**哦？有破绽，看我坑他一把。这么说，我明白了，是用对象的hashcode然后&数组的长度啊。

龙哥：不是的不是的，（急了），公式(n - 1) & hash 中的hash不是直接用到hashcode，这个jdk7和jdk8还是不同的，我们先来看看jdk7和jdk8的代码。

我们可以看到，jdk8的相对简单一点，做了1次异或操作，而jdk7做了四次。而且都是向低位做异或操作，这是为了什么呢？那是因为在计算put的元素应该放到哪个哈希桶中，也就是数组中的哪一个位置的时候。刚才说了，是通过公式 (n - 1) & hash 计算的，而&运算的特性是两位同时为“1”，结果才为“1”，否则为0。而我们数组的长度一般不会特别大，所以hash值中的高位的特性会用不到，所以为了更加分散，将高位和低位的特性融合，使得元素更容易分散到不同的哈希桶中，避免哈希碰撞的发生。这就叫扰动函数。至于jdk8为什么只异或一次，可能是开发人员觉得这样就够分散了吧。

**面试官：**嗯嗯，不错不错，那我懂了，先取得key的hashcode，然后扰动函数高位低位特性融合，最后算出在数组中的索引，就比如我数组长度为14，就会所引出0到13的值，这回没错了把？

龙哥：（mmmmm，，，你咋老给我挖坑，我虽然秃但是并不强啊，你老把我当琦玉可还行）不是的面试官，数组的长度只会是2的整数倍，不是有14这种情况发生的。

**面试官：**略加思索，不对把，我年轻的时候new过一个HashMap，构造函数里面就是扔的14啊，没有报错啊（内心os，这看你怎么接）。

**龙哥：**是这样的，虽然你给构造函数的是14，但是HashMap帮你转换成了离14最近的而得整数倍的数字，如果你是14就会变成16（也是数组长度的默认值），但是你给的是32，已经是2的整数倍了，就还是32。具体怎么做的呢？

因为int是32位的，所以只要经过五次的或运算就能从最高位到最低位都变成1，之所以先减一，就是为了防止传入32的情况，如果不减一就会变成64的。

面试官：（我怎么感觉场子hold不住了）嗯，之前我们公司，有一次线上cpu100%，好像和HashMap有关，你知道怎么发生的么？

龙哥： 那咱们公司（呸，不要脸，是你们公司），当时一定是用的jdk1.7，jdk1.7是采用的头插法会造成链表成环，jdk8是尾插发，就不会了。

面试官： 详细说说。

龙哥： 是这样的，这是jdk7的扩容代码。

jdk7的大体流程是这样子，在单线程下，遍历老数组的所有节点，并且遍历每一个节点下链表的所有节点。重新hash计算在新数组中的位置，然后将这个节点的next指针指向原本新数组中对应位置的节点，自己成为新数组那个位置上的头节点，就是把原有节点顶下去的过程。

在单线程情况下是没有问题的，但是多线程请款下就有可能造成您说的cpu100%，因为成了死循环，按理说不应该在多线程情况下使用HashMap，但是造成cpu100%还是太过严重了，所以jdk8才变成了尾插法。那造成死循环的原因，还是根据扩容的代码，走一遍就知道了。
假设原HashMap是这个样子的（图中数组长度不准确，应该是2的整数倍，这里省空间，大家记得区分）。

这时候，t1、t2两个线程同时请求扩容，t1，执行到了下图这里被cpu释放了执行权。

此时t1、t2都有自己扩容之后的数组，此时t2完成扩容，值得注意的是，t1、t2的数组不是一个，但是数组中的链表对象引用的都是一个。

这时候t1从睡梦中醒来了，它会主要做这三步操作。

操作完了之后是这个样子的。

进第二次循环，这时候，e指针和next指针都是b。再走那三步。

这时候，e和next还都是b，但是t1线程下，索引2的位置的头节点由a，变成了b，然后执行了这么一段代码，e.next = newTable[i];，把a的next指向b，当当当当，环出来了。

于是，a的next是b，b的next是a，a的next是b，b的next是a，a的next是b，b的next是a，cpu就这么执行啊执行啊，没完没了，就100%了。

面试官： 好了好了，说的还算详细，看来源码没少看啊，刚才你说jdk7要重新rehash，jdk8也是这样了呗？

龙哥： 不是的，不是的，当然不是的。

面试官： 好好说话，挺大岁数了，别卖萌。

龙哥： 好的哈，jdk8避免了扩容之后重新的rehash计算，因为jdk8计算在数组中的位置的方式是 hash &（n - 1） ，n是2的整数。举个例子，如果n是16的时候，（n-1）也就是15的二进制就是1111；如果n是32的时候，那么（n-1）也就是31的二进制就是11111，可以看出，二者的差别就是31比15的高位多了一个1。对于整个 hash &（n - 1） 的结果来看，因为&的运算逻辑是相同的二进制位都是1就是1，一个是0就是0。那么，n等于16和32的运算结果的是否相同就取决于hashcode第五位到底是0还是1，如果是0的话，同一个hashcode对于 hash &（n - 1），n=16、n=32的运算结果就是相同的；如果如果是1的话，同一个hashcode对于 hash &（n - 1） ，n=16、n=32的运算结果就是多了一个16（就是扩容前的容量），因为，n-1的最高位置的1代表的数字，就是n/2的结果。

面试官： 嗯，那jdk8之后HashMap是不是就线程安全了。

龙哥： 不是的，jdk8只是不会发生链表成环的情况，但是在put操作的时候，会出现元素被覆盖的情况，并且size++也是有线程安全问题的，如果要考虑多线程的情况下使用，建议使用ConcurrentHashMap，里面有分段锁，所谓分段锁，jdk7中ConcurrentHashMap外面有一个Segment数组，这个Segment继承了ReentrantLock，我们就可以对每一个Segment单独上锁，既能保证线程安全，锁的粒度又不会太大，性能又不会太差，，，

面试官： 停停停，今天主要面试HashMap，最后问一个简单的问题，数组什么时候会扩容。

龙哥： 我不会啊，，，， （回家之后问大航子，大航子：有一个东西叫负载因子，默认是0.75，但是科学家前辈算出来的0.69几才是最完美的值。这个值是用来在空间和时间上取得平衡，比如原来数组长度是16，那么达到 16 *0.75=12 就会扩容了，一般扩容是原有数组的两倍。龙哥，你好棒！）

面试官： 好了你先回家吧，我们改天再面。

龙哥： 别别别，我还会很多，你问问我AQS啥的啊，mysql原理我都懂得。

面试官： 滚

龙哥： 好嘞！！！！

---

总结

hashmap的知识点还是比较多的，想要多理解，源码还是要多看看的。

常见的比较有深度的HashMap的面试题，应该在这次模拟面试中，龙哥都经历过了。

最后，感谢大家的观看，我是大航子，有问题，欢迎留言哈。