在学习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)该方法计算也就相当于对容量取模
网友评论