(1)hashcode跟2的n次方减一做与运算;
减一为了保证取值范围,与运算可以减少碰撞以及值完全取决于hashcode
这跟生成数组index有关,常规做法是求余(int index=hash%length),使得index在[0,length-1]这个区间,而HashMap的做法是与运算(int index=hash^length-1);
以length=16(2的4次方)为例;
public void test() {
int length = 16;//16为2的4次方,二进制为0001 0000,而length - 1=15,二进制就是0000 1111;
int hashCode = 16;//假设hashCode为16,二进制为是0001 0000
//hashCode^length - 1=0,0000 1111^0001 0000,结果是0,元素存放的下标就是0,这跟hashCode%length(16%16)结果一致
}
length减一目的:使得原来1右边低位都为1、左边高位都为0,那么无论多大的hashCode做与运算,结果都在[0,length-1]之间
不采用求余运算,是因为位运算比较快。
网友评论