由于近期忙着搬家，又偷懒了几个礼拜！
其实我很早以前就想写一篇关于HashMap的面试专题。对于JAVA求职者来说，HashMap可谓是集合类的重中之重，甚至你在复习的时候，其他集合类都不用看，专攻HashMap即可。
然而，鉴于网上大部分的关于HashMap的面试方向文章，烟哥看过后都不是太满意。因此，斗胆尝试也写一篇关于HashMap的面试专题文章!
此题可以组成如下连环炮来问
你看过HashMap源码嘛，知道原理嘛?
为什么用数组+链表？
hash冲突你还知道哪些解决办法？
我用LinkedList代替数组结构可以么?
既然是可以的,为什么HashMap不用LinkedList,而选用数组?
你看过HashMap源码嘛，知道原理嘛?
针对这个问题，嗯，当然是必须看过HashMap源码。至于原理，下面那张图很清楚了:
HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。
只是在JDK1.8中，链表长度大于8的时候，链表会转成红黑树！
为什么用数组+链表？
数组是用来确定桶的位置，利用元素的key的hash值对数组长度取模得到.
链表是用来解决hash冲突问题，当出现hash值一样的情形，就在数组上的对应位置形成一条链表。
ps:这里的hash值并不是指hashcode，而是将hashcode高低十六位异或过的。至于为什么要这么做，继续往下看。
hash冲突你还知道哪些解决办法？
比较出名的有四种(1)开放定址法(2)链地址法(3)再哈希法(4)公共溢出区域法
ps:大家有兴趣拓展的，自己去搜一下就懂了，这个就不拓展了！
我用LinkedList代替数组结构可以么?
这里我稍微说明一下，此题的意思是，源码中是这样的
ps：Entry就是一个链表节点。
那我用下面这样表示
是否可行?
答案很明显，必须是可以的。
既然是可以的,为什么HashMap不用LinkedList,而选用数组?
因为用数组效率最高！
在HashMap中，定位桶的位置是利用元素的key的哈希值对数组长度取模得到。此时，我们已得到桶的位置。显然数组的查找效率比LinkedList大。
那ArrayList，底层也是数组，查找也快啊，为啥不用ArrayList?
(烟哥写到这里的时候，不禁觉得自己真有想法，自己把自己问死了，还好我灵机一动想出了答案)
因为采用基本数组结构，扩容机制可以自己定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率高。
而ArrayList的扩容机制是1.5倍扩容，那ArrayList为什么是1.5倍扩容这就不在本文说明了。
此题可以组成如下连环炮来问
HashMap在什么条件下扩容?
为什么扩容是2的n次幂?
为什么为什么要先高16位异或低16位再取模运算?
HashMap在什么条件下扩容?
如果bucket满了(超过load factor*current capacity)，就要resize。
load factor为0.75，为了最大程度避免哈希冲突
current capacity为当前数组大小。
为什么扩容是2的次幂?
HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法； 这个算法实际就是取模，hash%length。
但是，大家都知道这种运算不如位移运算快。
因此，源码中做了优化hash&(length-1)。
也就是说hash%length==hash&(length-1)
那为什么是2的n次方呢？
因为2的n次方实际就是1后面n个0，2的n次方-1，实际就是n个1。
例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞。
而长度为5的时候，3&(5-1)=0 2&(5-1)=0，都在0上，出现碰撞了。
所以，保证容积是2的n次方，是为了保证在做(length-1)的时候，每一位都能&1 ，也就是和1111……1111111进行与运算。
为什么为什么要先高16位异或低16位再取模运算?
我先晒一下，jdk1.8里的hash方法。1.7的比较复杂，咱就不看了。
hashmap这么做，只是为了降低hash冲突的几率。打个比方，
当我们的length为16的时候，哈希码(字符串“abcabcabcabcabc”的key对应的哈希码)对(16-1)与操作，对于多个key生成的hashCode，只要哈希码的后4位为0，不论不论高位怎么变化，最终的结果均为0。
如下图所示
而加上高16位异或低16位的“扰动函数”后，结果如下
可以看到: 扰动函数优化前：1954974080 % 16 = 1954974080 & (16 - 1) = 0 扰动函数优化后：1955003654 % 16 = 1955003654 & (16 - 1) = 6 很显然，减少了碰撞的几率。 (3)讲讲hashmap的get/put的过程?
此题可以组成如下连环炮来问
知道hashmap中put元素的过程是什么样么?
知道hashmap中get元素的过程是什么样么？
你还知道哪些hash算法？
说说String中hashcode的实现?(此题很多大厂问过)