java - 摆脱 bin 索引计算中的循环

Question

这是一个 implementation of HashMap .

它提供了获取 bin 索引的代码:

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) 算法(独立于 hash 值)。

如果可以，如何实现？

Answer 1

不能是很大的负数。

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

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