2

这是.HashMap

它提供了用于获取 bin 索引的代码：

private int getIndex(K key)
{
    int hash = key.hashCode() % nodes.length;
    if (hash < 0)
        hash += nodes.length;
    return hash;
}

为了确保散列值不大于表的大小，用户提供的散列函数的结果以表的长度为模。我们需要索引为非负数，但如果左操作数（哈希值）为负数，则取模运算符 (%) 将返回负数，因此我们必须对其进行测试并使其为非负数。

如果hash结果是非常大的负值，hash += nodes.length则循环中的加法可能需要大量处理。

我认为应该有O(1)它的算法（与hash价值无关）。

如果是这样，如何实现？

4

2 回答 2

3

它不能是一个很大的负数。

的结果anything % nodes.length总是小于nodes.length绝对值，所以你需要一个if，而不是一个循环。这正是代码的作用：

if (hash < 0) /* `if', not `while' */
    hash += nodes.length;
于 2012-11-28T09:33:36.723 回答
1

这不是HashMap在现实中使用的方法。

272       /**
273        * Returns index for hash code h.
274        */
275       static int indexFor(int h, int length) {
276           return h & (length-1);
277       }

这是有效的，因为length总是 2 的幂，这与无符号的相同 % length

如果 hash 结果是非常大的负值，则循环中添加的 hash += nodes.length 可能需要大量处理。

此时的哈希值必须介于两者之间-length+1，length-1因此它不能是一个非常大的负值，并且如果这样做，代码将无法工作。无论如何，无论价值有多大，成本总是一样的。

于 2012-11-28T09:49:09.003 回答