hashFor中的indexFor？

Question

试着Java HashMap通过查看代码来了解我的工作.添加元素时,会发生以下情况:

1. 得到了密钥的哈希码
2. 在结果上应用哈希函数
3. 方法indexFor应用于结果2.这给出了相应存储桶中的第一个条目.然后迭代桶中的链表 - 找到结束并添加元素.

indexO f 的实现是:

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

我无法理解indexOf方法中的技巧.有人能解释一下吗？

谢谢.

Answer 1

这是因为Java HashMaps总是有一个容量,即桶的数量,作为2的幂.让我们使用256的容量,即0x100,但它可以使用2的任何幂.从2的幂的功率减去1按位所需的精确位掩码 - 并使用散列来获取正确的存储区索引,范围0为length - 1.

256 - 1 = 255
0x100 - 0x1 = 0xFF

例如,257(0x101)的散列以0xFF逐位进行,以产生1的桶数.