在上一篇 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 是 等价的。 而位运算更快一些。
先来看一组数字：
n （格式为2^m=十进制数字=二进制数字） n-1 （格式为2^m – 1=十进制数字=二进制数字） 2^2 = 4 = 100 2^2 – 1 = 3 = 011 2^3 = 8 = 1000 2^3 – 1 = 7 = 0111 2^4 = 16 = 10000 2^4 – 1 = 15 = 01111 2^5 = 32 = 100000 2^5 -1 = 31 = 011111
此处我们可以看到规律，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
1 0 0 1 0 右移2位 0 0 1 0 0 1 0 hash=18 数组长度n=4=2^2 18/4得到的整除 余数18%4
通过运算可以很容易的验证18/4 = 00100 = 4 ， 而18%4 = 10 = 2， 是正确的。
现在假设Node数组进行了扩容n=8，再来看一下：
Original: https://www.cnblogs.com/adeline-tech/p/16701991.html
Author: adeline.pan
Title: HashMap的哈希函数为何用(n – 1) & hash
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/802493/
转载文章受原作者版权保护。转载请注明原作者出处！