java - 为什么HashMap使用长度减1来计算索引？

Question

我正在分析jdk7中HashMap的源码，发现当我们调用put()添加元素的方法，会使用indexFor()计算索引并将元素存储到数组中，方法如下。

现在我想知道为什么它使用 h & (length-1) 来获取索引？它是用于获取更多随机数组索引吗？我们可以使用 length 或 length-2(如果存在)来代替吗？

谁能帮我理解这一点？提前致谢!

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

Answer 1

Is it used for to get more random array index?

没有

Can we use length or length-2(if exists) instead?

没有

这只是一个数学技巧。要将 HashMap 到[0, L)范围，您需要计算hash % L。除法的成本可能很高，因此开发人员选择利用数字以二进制存储的方式。这仅适用于 2 的幂，因为仅设置了一位，减去 1 会设置所有较低有效位并取消设置原始位。将其与我们的散列进行二进制与运算具有与计算模相同的结果，比我们可以处理的更重要的每一位都被丢弃。