java - 如何从哈希计算数组索引

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)。