java - 哈希图中的indexFor？

Question

只是想Java HashMap通过查看代码来了解它的工作原理。添加元素时，会发生以下情况：

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

indexO f的实现是：

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

我无法理解 indexOf 方法中的技巧。谁能解释一下？

谢谢。

Answer 1

这是因为 JavaHashMaps总是有一个容量，即桶的数量，是 2 的幂。让我们使用 256 的容量，即 0x100，但它可以使用 2 的任何幂。从 2 的幂中减去 1 产生需要的确切位掩码按位和哈希来获得正确的桶索引，范围0为length - 1.

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

例如，257 (0x101) 的哈希值与 0xFF 进行按位与运算，得到存储桶编号 1。