面试题：说一说你对HashMap的理解

HashMap的插入与获取

jdk8中，在HashMap里面是一个数组，数组中每个元素都是一个单向链表，如果链表中的元素大于8个并且数组长度大于64以后会转为红黑树，这是为了提升和均衡搜索效率。

在put插入时候，会将key和value封装为一个node，接着调用key的hashCode方法获取到key的哈希码，由于数组长度永远是2的n次方，因此对数组长度取余就相当于hash & length-1，这个结果就是数组下标，获取到下标后会检查这个位置有没有值，如果没有值的话可以直接放入链表中，如果有值的话那么会将key和链表中的元素的key进行equals比较，都是都返回了false，那么会将这个node放入到链表的最后面，如果key和链表中的某个元素equals返回了true，那么就会覆盖。

在get获取时候，也会获取到key的hashCode，再将hashCode转为数组下标，如果下标对应的元素是null的话，就直接返回空。如果当前元素是个链表的话，那么就会使用equals和链表中的元素的key进行比较，如果都返回false那么返回空，如果有一个元素返回了true，那么就把这个元素返回。如果当前元素是红黑树的话，那么使用getTreeNode()方法来搜索key。

HashMap的数组扩容实现

HashMap的数组扩容分为两个部分，第一部分是确定新数组的长度和下次扩容的阈值，第二部分是将原数组的值迁移到新数组中。

新数组的长度是原数组的2倍；

下次扩容的阈值是新数组长度乘以负载因子；

迁移数据的话，在jdk7中，会遍历所有节点，进行hash方法计算新的下标，再插入到新数组中；

在jdk8中进行了优化，因为每次扩展数组都是2倍，所以新位置要么在原来的位置要么在原来位置乘以2。这个数位与会用key的hash值与旧数组的长度进行"与" *** 作。如果结果是0，那么当前元素的桶位置不变。如果不是的话，那么桶的位置就是原位置+原数组长度。

原因是：当数组长度是2的n次方的时候，hash对数组长度取余相当于hash & length-1。假如扩容前容量是16，扩容后32，因为hash()的结果会跟length-1位与运算得到下标，那么hash结果会跟31(二进制是11111)位与，可以想一下hash结果跟15(二进制是1111)位与，如果hash结果的第5位是0的话，那么无论是跟15还是跟32位与的值都是一样的，但是如果第5位是1的话，那么它跟31位与运算的结果将是与15位与运算后的结果再在前面加上1，也就是加上2的4次方也就是16，也就是原位置+原数组长度。

为什么HashMap的数组长度是 2 的 n 次方

hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方。

对2的N次方求余，就预示着数字将向右移N位；这被右移的N位，就是余数。

只要我们再用与运算将这N位保存下来即可，当length是2的n次方的时候，length-1在二进制中就是n个1。

之所以采用hash&(length-1)来取余，而不是直接进行hash%length的原因在于：位运算计算速度更快，更加高效。

为什么的HashMap的加载因子是0.75

HashMap下次扩容的阈值是当前数组大小乘以加载因子。

如果加载因子太大，那么就很难扩容，数据可以放入的数组就很少，也就导致链表的长度很长，查找元素的效率就很低；并且数组少了，那么就会增加哈希冲突可能性，进而导致性能不好。

如果加载因子太小，那么就会经常扩容消耗资源，并且数组会增多，那么就会浪费空间。

0.75是0.5和1的中间值，所以就取的0.75。