HashMap底层分析

当我们向HashMap容器中put一个元素时，这个元素会被放到一个Node结点对象中，结点对象又会被放入到数组中，那么结点对象会被放入数组的什么位置呢？这是由key的hash值来决定的。

hash值，是用来确定Node结点对象在Node数组中 存取位置 的一个重要数据。hash值经过**&**与运算后会得到一个索引值，它就是Node结点对象在Node数组中 存取位置。 1. 调用key对象的hashCode()方法，获得key的hashCode值。

2. 根据hashCode值，通过hash算法，计算出hash值。（那么使用什么算法来计算hash值呢？ 既要保证 运算速度快，又要保证 计算出来的hash值能均匀分布在[0，数组长度 - 1]区间内）

3. hash算法实现分为两步：

第一步就是hash()函数，将key的hashCode值 与 key的hashCode值的高16位(无符号右移)，进行^异或运算，得到一个hash值（注意：这个hash值，不是index索引，需要进行第二步计算后得到的才是index索引）

这一步的目的是为了，计算出来的index索引，能均匀分布在[0，数组长度 - 1]区间内。（即是元素分布均匀）。

将第一步中的到的hash值 和 (数组长度 - 1) 进行&运算，得到index索引。(注意：该算法有个前提，约定数组长度必须为2的整数幂。这就是HashMap的容量必须为2的整数幂的原因)

index = hash值 & (数组长度 - 1)

很多hash算法采用的都是取模运算(取余，index = hash % n)，保证得到的索引小于数组长度，并且分布均匀，但cpu在做/除法运算 或 %取余运算时，效率是很低的。所以jdk对改进了算法，首先在约定数组长度必须是2的整数幂，这样通过&与运算同样可以实现取余的效果（&与运算 比 %取模运算 的效率高）。

1. cpu执行 &与运算 的效率比执行 %取余运算高很多，那么HashMap中是如何将%取模运算 转换为 &与运算的呢？

2. 为什么取模运算是用 hash % 数组长度 ，而&与运算是 hash & (数组长度 - 1) 呢？