HashMap: 为什么(n - 1) & hash结果能始终在

参考博客：

• java学习--高效的除模取余运算(n-1)&hash
• 由HashMap哈希算法引出的求余%和与运算&转换问题

hashMap的数据结构是数组+链表（红黑树）的结构，当存入一个元素的时候首先要解决的是确定这个元素在数组中的位置。源码是通过（数组长度 - 1）& 要存入元素key的hash值来确定位置的。

那么问题来了，为什么(n - 1) & hash结果能保证结果始终在数组的范围之内？

我现在将问题转换一下，假如我们不用源码中的方案，我们怎么来保证要存入的元素一定会落在数组中。答案就是求余运算，用要存入元素的key的hash值对数组长度进行求余，即hash%n 结果肯定会落在数组的范围内。

我们对比下两个方案：

• 源码方案： (n-1)&hash
• 传统求余方案： hash%n
  方案对比
  也就是说，如果数组长度为2的n次幂时，模运算 % 可以变换为按位与 & 运算。那么为什么用(n-1)&hash而不是用hash%n呢，因为在计算机中 & 的效率比 % 高很多。