142

Java String 的 hashCode 值计算为 ( String.hashCode() )：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

是否有任何情况（比如 JVM 版本、供应商等）以下表达式的计算结果为 false？

boolean expression = "This is a Java string".hashCode() == 586653468

更新＃1：如果您声称答案是“是的，存在这种情况” - 那么请给出一个具体示例，说明何时“这是一个 Java 字符串”.hashCode() ！= 586653468。尽量做到具体/具体尽可能。

更新#2：我们都知道依赖 hashCode() 的实现细节通常是不好的。但是，我专门讨论的是 String.hashCode() - 所以请让答案集中在 String.hashCode() 上。Object.hashCode() 在这个问题的上下文中完全不相关。

4

8 回答 8

107

我可以看到早在 Java 1.2 的文档。

虽然确实通常您不应该依赖保持不变的哈希码实现，但它现在已记录在案的行为java.lang.String，因此更改它将被视为违反现有合同。

只要有可能，您不应该依赖在不同版本等之间保持相同的哈希码 - 但在我看来，这java.lang.String是一个特殊情况，仅仅是因为已经指定了算法......只要您愿意放弃与之前版本的兼容性当然，算法是指定的。

于 2009-04-24T09:25:04.463 回答
18

我发现了一些关于 JDK 1.0 和 1.1 和 >= 1.2 的信息：

在 JDK 1.0.x 和 1.1.x 中，长字符串的 hashCode 函数通过对每第 n 个字符进行采样来工作。这很好地保证了您将有许多字符串散列到相同的值，从而减慢了 Hashtable 查找。在 JDK 1.2 中，该函数得到了改进，将目前的结果乘以 31，然后按顺序添加下一个字符。这有点慢，但在避免碰撞方面要好得多。来源： http: //mindprod.com/jgloss/hashcode.html

不同的东西，因为你似乎需要一个数字：使用 CRC32 或 MD5 代替哈希码怎么样，你很高兴 - 没有讨论，也没有后顾之忧......

于 2009-04-24T12:17:35.907 回答
8

您不应依赖等于特定值的哈希码。只是它将在同一执行中返回一致的结果。API 文档说以下内容：

hashCode 的一般合约是：

  • 每当在 Java 应用程序执行期间对同一个对象多次调用它时，hashCode 方法必须始终返回相同的整数，前提是没有修改对象上的 equals 比较中使用的信息。该整数不需要从应用程序的一次执行到同一应用程序的另一次执行保持一致。

编辑 由于 String.hashCode() 的 javadoc 指定了如何计算字符串的哈希码，因此任何违反此规定的行为都将违反公共 API 规范。

于 2009-04-24T09:16:12.207 回答
5

如上所述，一般而言，您不应依赖保持相同的类的哈希码。请注意，即使同一应用程序在同一 VM上的后续运行也可能产生不同的哈希值。AFAIK Sun JVM 的散列函数在每次运行时计算相同的散列，但这并不能保证。

请注意，这不是理论上的。java.lang.String 的散列函数在 JDK1.2中发生了变化（旧的散列在 URL 或文件名等分层字符串方面存在问题，因为它倾向于为仅在末尾不同的字符串生成相同的散列）。

java.lang.String 是一种特殊情况，因为它的 hashCode() 算法（现在）已记录在案，因此您可能可以依赖它。我仍然认为这是不好的做法。如果您需要具有特殊记录属性的哈希算法，只需编写一个 :-)。

于 2009-04-24T09:23:31.423 回答
3

另一个需要担心的（！）问题是 Java 的早期/晚期版本之间的实现可能发生变化。我不相信实现细节是一成不变的，因此升级到未来的Java 版本可能会导致问题。

底线是，我不会依赖hashCode().

也许您可以通过使用此机制突出显示您实际尝试解决的问题，这将突出显示更合适的方法。

于 2009-04-24T09:16:18.697 回答
3

只是为了回答你的问题，而不是继续任何讨论。Apache Harmony JDK 实现似乎使用了不同的算法，至少看起来完全不同：

孙 JDK

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

阿帕奇和谐

public int hashCode() {
    if (hashCode == 0) {
        int hash = 0, multiplier = 1;
        for (int i = offset + count - 1; i >= offset; i--) {
            hash += value[i] * multiplier;
            int shifted = multiplier << 5;
            multiplier = shifted - multiplier;
        }
        hashCode = hash;
    }
    return hashCode;
}

随意检查一下...

于 2009-04-24T11:21:42.047 回答
2

如果您担心更改和可能不兼容的 VM，只需将现有的 hashcode 实现复制到您自己的实用程序类中，然后使用它来生成您的 hashcodes 。

于 2009-04-24T15:27:36.307 回答
1

哈希码将根据字符串中字符的 ASCII 值计算。

这是String类中的实现如下

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                              : StringUTF16.hashCode(value);
    }
    return h;
}

哈希码中的冲突是不可避免的。例如，字符串“Ea”和“FB”给出与 2236 相同的哈希码

于 2019-07-03T06:05:19.597 回答