如何从散列计算数组索引

Question

我看过有关如何为字符串创建哈希的示例。这是 Java 中的一个示例：

private int getHashCode(String text) {
    int hash = 7;
    for (int i = 0; i < text.length(); i++) {
        hash = hash * 31 + text.charAt(i);
    }

    return hash;
}

这当然可以产生大量的数字。如果我将字符串存储在一个数组中并且我只说 10 个数组项，我如何从哈希码计算数组索引？我当然可以使用 HashMap 来做到这一点，但我想把它作为学习如何从哈希码创建索引的一部分。

Answer 1

您可以使用余数运算符 ( %) 将您的哈希码映射到数组的索引：

int index = obj.getHashCode ("SomeString") % yourArray.length;

当然，您应该能够处理冲突（即两个或多个字符串映射到相同数组索引的情况）。

HashMap 通过在数组的每个索引中存储一个条目实例来处理这种潜在的冲突，该实例可以指向映射到相同索引的下一个条目（从而形成一个链表）。

编辑：

正如下面正确评论的那样，该%运算符不适用于负哈希码。作为替代方案，您可以使用Math.floorMod（在 Java 8 中引入）：

int index = Math.floorMod (obj.getHashCode ("SomeString"), yourArray.length);

无论哈希码的符号如何，这都保证返回非负索引。

或者您可以采用HashMap实施中使用的替代方案。如果数组的长度始终是 2 的幂，则可以使用obj.getHashCode ("SomeString") & (yourArray.length - 1).