前言

在上一篇 Java 中HashMap详解(含HashTable, ConcurrentHashMap)  中提到在map.put(key, value)的过程中，计算完key的hash值， 是通过hash & (n-1)来得出该元素在Node数组中的下标的，其中n是Node数组的长度。 其实我们更容易想到的是hash % n，这样刚好会得到0~n-1之间的数字，可以用作数组下标。那么为何此处是用的位运算呢？

结论

先说结论。 这里有一个前提，那就是HashMap中Node数组的长度始终保持是2^n， 比如默认的16， 如果创建HashMap的时候指定了初始的capacity,而这个capacity可能不是2^n, 会在内部转化一下，得到一个大于这个capacity的最小的2^n的数字来初始化数组。 每次扩容的时候也是进行2倍的扩容。

在这个前提下，hash & (n-1) 与 hash % n 是等价的。 而位运算更快一些。

论证

先来看一组数字：

此处我们可以看到规律，2^m的二进制就是1的后面加上m个0, 而2^m -1的二进制就是0的后面加上m个1.

下面我们来看 hash % n（求余数）的运算：

首先看hash/n，由于n=2^m， 我们先看hash/2的情况，这样一来就简单了，因为我们都知道，二进制的情况下，一个数字除以2其实就是右移一位，在左边加一个0，右边移出去一位。如果觉得不好理解，就类比十进制的数字除以10的情况，是一样的。举一反三一下，hash/4的情况自然就是右移2位，由于n=2^m， 其实hash/n的操作就是右移m位。

右移之后我们得到的是hash/n的整除，那么余数呢？其实就是我们移出去的数字。

举个例子，假设hash = 18, n=4,我们知道18/4=4 , 18%4 =2,看看按照我们上面的运算是否会得到相同的结果：

18=10010， 4=2^2

通过运算可以很容易的验证18/4 = 00100 = 4 ， 而18%4 = 10 = 2， 是正确的。

现在假设Node数组进行了扩容n=8，再来看一下：