为什么HashMap的table 容量（这里记为lenght）是2的n次方？
回答这个问题之前我们先来看位运算，对于任意的int型数n（假设 n>0）。其二进制如1010110001111010。
要求它对一个数的余数，如1010001，额是不是好难，无论十进制还是使用位运算都是非常麻烦的一件事。可是如果要求它对10000的余数，是不是就非常简单。
1010110001111010 = 1010110001110000 +1010
1010110001110000 是10000的整数倍数，余数是1010
1010110001111010 除数（hash）
0000000000010000 被除数(table.lenght)
--------------------------- 求余
0000000000001010 余数(index)
具体做法：将10000-1得到1111，再用1111&1010110001111010。这样得到的数一定是位于[0, length-1]之间的，且是hash值的最后几位，在一定程度上保证了散列度。形如10000...0000这样的二进制数恰好是2的n次方。我认为这就是table 容量为2的n次方的原因。计算简单，效率高，足够散列。
大可能我们都见过类似于这样的解释：如果table 容量不是2的n次方，那么hash & length-1 后，结果不够散列，很容易发生hash冲突，导致大量数据都放到一个节点上。这句话本身确实很对，但是不能作为 table 容量为什么是2的n次方这个问题的解释，只能算是事后诸葛亮的强行解释。也就是说，你已经接受了使用（hash & length-1）这种算法求[0, lenght-1]这样的下标的前提下，所做的解释。其实，table 容量确定后，只要能根据hash值，通过一个算法得出一个[0, length-1]这样的一个下标即可，至于这个下标是不是恰好是余数，不重要，重要的是，计算过程必须足够高效，下标要足够散列，且范围是[0, length-1]。也就是说，如果table 容量不是2的n次方，但是仍然能高效的通过hash值算出一个符合要求的下标，那么也是可以的。
网友评论