java - 消除 bin 索引计算中的循环

Question

这是一个implementation of HashMap .

它提供了用于获取垃圾箱索引的代码:

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

To make sure the hash value is not bigger than the size of the table, the result of the user provided hash function is used modulo the length of the table. We need the index to be non-negative, but the modulus operator (%) will return a negative number if the left operand (the hash value) is negative, so we have to test for it and make it non-negative.

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

我认为应该有一个O(1)算法(独立于哈希值)。

如果可以，如何实现？

Answer 1

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

anything %nodes.length 的结果绝对值始终小于 nodes.length，因此您需要一个 if，不是循环。这正是代码的作用:

if (hash < 0) /* `if', not `while' */
    hash += nodes.length;