HashMap扩展问题：为什么容量要保证在2的N次方？

HashMap扩展问题：为什么容量要保证在2的N次方？

先说结论，为了减少哈希碰撞，提高代码效率。

问题1：为什么是2的N次幂而不是3的N次幂或者8的N次幂？

之前我们在这里提到过，在HashMap进行扩容的时候，对于链表中只存在一个Node节点的情况，是通过 e.hash & (newCap - 1) 来计算他在新数组中存储的位置。
而使用2的N次幂的原因则是为了提高 e.hash & (newCap - 1)这一段代码的效率。看例子：

---

|00000000 00000000 00000000 00000101 | ->5
|00000000 00000000 00000000 00000111 | ->7（2的3次幂-1）
|-------------------------------------------------------- |
|00000000 00000000 00000000 00000101 |

2的N次幂保证了在&运算时尽可能的不受容量的影响。

---

如果不是2的N次幂呢？：
|00000000 00000000 00000000 00000101 | ->5
|00000000 00000000 00000000 00010001 | ->9（3的2次幂）
|-------------------------------------------------------- |
|00000000 00000000 00000000 00000001 |

10001的中间那个0，导致了不管上面的数是0还是1，都使结果变成了0，因此增大了哈希冲突的概率。

上面解释了为什么使用的是2的N次幂，为什么不是8的N次幂，16的N次幂是因为2的粒度最小，效率更高。
那么问题又来了，我们不 & 运算，是不是就没有这个问题了？这里就带来了第二个问题

问题2：为什么我们需要使用e.hash & (newCap - 1)

众所周知，有一个1-9一共九个数字，我们想让他均匀的分在3个坑里，是不是每个坑我们期望都是分配3个，因此一个元素在哪一个坑就是 1%3 = 1（第一个坑），2%3 = 2（第二个坑）以此类推。最后得到每个坑均匀分配三个元素。
那么e.hash & (newCap - 1)也是同样的道理，我们想要每个Node节点的e.hash均匀的分配在数组的坑里，我们想做的是 e.hash % capacity(容量），这个公式优化就得到了e.hash & （2的N次方-1）。

固定公式：
    取余(%)操作 : 如果除数是2的幂次则等价于与其除数减一的与(&)操作.

综上所述，源码就采用了e.hash & (newCap - 1)的方式来保证Node节点均匀的分配到数组中。

大家好，我是小羊炒饭。感谢大家的关注，有任何问题可以提出，我们一起学习共同进步。公司的前辈告诉我，想涨工资人情>技术，我不懂人情，所以我想深耕技术，希望有一天能涨工资哈哈。
这一篇就不往下扩展啦，再扩展就只能是往内存方向了，比如为什么1个字节是8位之类的，大家可以自己研究。晚安玛卡巴卡。