2018-04-26（hashmap对数组长度取模）

在学习hashmap原码时候，发现一个很有趣的事情，
hashmap是由数组和链表组成，而在put时候首先要确定key应该插入到数组中位子
之前学习时候记得是用key的hashcode对数组长度取模，也就是用key.hashcode() % length

但是今天查看原码发现并不是像我想的那么通过key.hashcode() % length该方法确定数组中位置

而是采用如下代码

 static int indexFor(int h, int length) {
        return h & (length-1);
    }

当时看到该方法就很奇怪，为什么不是我理解的方式呢？
按道理不应该是如下代码吗

 static int indexFor(int h, int length) {
        return h % length;
    }

后来发现原来 h & (length-1) 和 h % length 在某种情况下是等价的。

测试一下

    public static void main(String args[]) {
        System.out.println("19 & 15 = " + (19 & 15));
        System.out.println("19 % 16 = " + (19 % 16));
        
        System.out.println("30 & 15 = " + (30 & 15));
        System.out.println("30 % 16 = " + (30 % 16));
        
        
        System.out.println("25 & 7 = " + (25 & 7));
        System.out.println("25 % 8 = " + (25 % 8));
        
        
        System.out.println("25 & 9 = " + (25 & 9));
        System.out.println("25 % 10 = " + (25 % 10));
    }

运算结果如下:

19 & 15 = 3
19 % 16 = 3
30 & 15 = 14
30 % 16 = 14
25 & 7 = 1
25 % 8 = 1
25 & 9 = 9
25 % 10 = 5

通过测试我们发现如果
k & (len -1) 和 k % len 加入len为2的n次幂时，他们计算结果是相同的。
而我们知道hashmap的初始容量为16, 每次扩容都是len*2。 所以hash的容量肯定是2的n次幂，所以用return h & (length-1)该方法计算也就相当于对容量取模