logo标签列表

Java字符串的hashCode（）一致性

javastringhashcode
146

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：如果您声称答案是“是的，存在这种情况”，请给出一个具体的例子，说明何时“This is a Java string”.hashCode() != 586653468。尽可能具体和明确。 更新2：我们都知道通常依赖于hashCode()的实现细节是不好的。但是，我特别谈论的是String.hashCode() - 因此，请将答案集中在String.hashCode()上。Object.hashCode()在这个问题的背景下完全无关紧要。
2
你真的需要这个功能吗？为什么你需要精确的值？ - Brian Agnew
27
@Brian：我正在尝试理解String.hashCode()方法的合同。 - knorv
3
重点不在于准确理解其运作原理，而在于理解合同及其深层含义。 - mP.
47
谢谢您的回复，但我认为这是由我决定的。 - knorv
为什么要给第一个字符最大的权重？当你想要优化速度以保留额外的计算时，你会存储前一个字符的权重，但前一个字符将来自最后一个字符到第一个字符。这意味着也会有缓存未命中。使用以下算法是否更有效率：s[0] + s[1]*31 + s[2]*31^2 + ... + s[n-1]*31^[n-1]？ - android developer
8个回答
107

我可以看到Java 1.2时期的文档。

虽然通常情况下你不应该依赖于哈希码实现保持不变，但是对于java.lang.String来说，它现在是有文档记录的行为，因此更改它将被视为破坏现有合同。

在可能的情况下，你不应该依赖于哈希码在版本之间保持不变，但在我看来，java.lang.String是一个特殊情况，因为算法已经被指定...当然，前提是你愿意放弃与算法规范之前的版本的兼容性。

9
自 Java 1.2 版本起，String 类的文档行为已被规定。在 API 的 v1.1 中，String 类的哈希码计算未被指定。 - Martin OConnor
在这种情况下，我们最好自己编写哈希代码，对吧伙计？ - Felype
@Felype：很抱歉，我真的不知道你在这里想说什么。 - Jon Skeet
@JonSkeet 我的意思是，在这种情况下，我们或许可以编写自己的代码来生成我们自己的哈希值，以确保可移植性。对吗？ - Felype
1
大多数Java代码在1.4之前的版本中无法运行。可以安全地假定它是一致的。 - J-16 SDiZ
显示剩余2条评论
20

关于JDK 1.0和1.1以及>=1.2版本的hashCode函数，我找到了一些信息：

在JDK 1.0.x和1.1.x中，长字符串的hashCode函数是通过抽样每个第n个字符来运行的。这基本上保证了你会有许多字符串散列到相同的值，从而减缓哈希表查找速度。在JDK 1.2中，该函数已经改进为将结果乘以31，然后按顺序添加下一个字符。这样做可能会更慢，但更能避免冲突。 来源：http://mindprod.com/jgloss/hashcode.html

另外，因为您似乎需要一个数字：使用CRC32或MD5代替hashCode，您就可以放心使用--不需要讨论，也不需要担忧。

8
不要依赖散列码等于某个特定值。只要它在同一次执行中返回一致的结果即可。 API文档如下所述：
hashCode的一般契约是： - 在Java应用程序的同一次执行期间多次调用hashCode时，只要对象上用于equals比较的信息未被修改，hashCode方法必须一致地返回相同的整数。该整数不需要在应用程序的一个执行与另一个执行之间保持一致。
编辑： 由于String.hashCode()的javadoc指定了如何计算字符串的哈希码，任何违反此规定的行为都将违反公共API规范。
1
你的回答是有效的，但并没有回答具体提出的问题。 - knorv
7
这是通用哈希码合同 - 但是针对字符串的特定合同详细说明了算法，并且在我看来有效地覆盖了这个通用合同。 - Jon Skeet
6

如上所述，通常情况下您不应该依赖于类的哈希码保持不变。请注意，即使在相同的虚拟机上运行相同的应用程序，也可能会产生不同的哈希值。据我所知，Sun JVM 的哈希函数在每次运行时都计算相同的哈希值，但这并不是有保障的。

请注意，这不是理论上的问题。在 JDK1.2 中，java.lang.String 的哈希函数已更改（旧的哈希函数对层次结构字符串（如 URL 或文件名）存在问题，因为它倾向于为仅在末尾不同的字符串生成相同的哈希值）。

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

5
在JDK 1.2之前的文档中是否规定了该算法？如果没有，情况就不同了。现在算法已经在文档中明确规定了，因此更改它将会破坏公共契约。 - Jon Skeet
我记得它是1.1。原始（较差）算法已记录。不正确。文档化的算法实际上会抛出ArrayIndexOutOfBoundsException异常。 - Tom Hawtin - tackline
@Jon Skeet： 啊，我不知道String.hashCode()的算法是有文档记录的。当然，这改变了情况。我已经更新了我的评论。 - sleske
3
只回答你的问题，不继续讨论。Apache Harmony JDK实现似乎使用了不同的算法，至少它看起来完全不同：

Sun 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;
}

Apache Harmony

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;
}

请随意自行检查...

23
我认为他们只是在优化代码，让它看起来更酷。毕竟，“(multiplier << 5) - multiplier” 等于 31 * multiplier… - unwind
好的，我太懒了，没有检查。谢谢！ - ReneS
1
但为了明确我的观点...永远不要依赖哈希码，因为哈希码是内部的东西。 - ReneS
1
“offset”、“count”和“hashCode”的变量是什么意思？我猜“hashCode”被用作缓存值，以避免未来的计算，而“count”是字符数，但“offset”是什么？假设我希望使用此代码使其一致，给定一个字符串，我该怎么做？ - android developer
1
@androiddeveloper 现在这是一个有趣的问题 - 尽管根据您的用户名，我应该已经猜到了。从Android文档来看，合同是相同的：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 除非我弄错了，这是因为Android使用Sun的String对象实现而没有进行更改。 - Kartik Chugh
显示剩余6条评论
3

另一个需要担心的问题是Java早期/晚期版本实现的可能变化。我认为实现细节并没有确定下来，因此将来升级到某个未来的Java版本可能会导致问题。

最重要的是，我不会依赖于hashCode()的实现。

也许你可以强调你想通过这种机制解决什么问题，这将突出更合适的方法。

1
感谢您的回答。您能否给出具体的例子，说明“这是Java字符串”。hashCode（）！= 586653468？ - knorv
1
不好意思。我的观点是，你在测试的所有东西可能按照你想要的方式运行。但这仍然不能保证。所以如果你正在处理一个（比如）短期项目，在这个项目中你掌控着VM等，那么上述方法可能适用于你。但在更广泛的世界里，你不能依靠它。 - Brian Agnew
2
将来的Java版本升级可能会导致问题。将来的Java版本升级可能会完全删除hashCode方法。或者使其始终为字符串返回0。这是不兼容的更改。问题是Sun ^HOracle ^HThe JCP是否认为这是一项破坏性的更改，因此值得避免。由于算法在合同中，人们希望他们会考虑到这一点。 - Steve Jessop
@SteveJessop嗯，由于对字符串的switch语句编译为依赖于特定固定哈希码的代码，因此对String哈希码算法的更改肯定会破坏现有的代码... - Holger
2
如果你担心更改会导致虚拟机不兼容，只需将现有的哈希码实现复制到自己的实用程序类中，并使用它来生成你的哈希码。
我本来也想这么说。虽然其他答案回答了问题，但编写单独的hashCode函数可能是解决knorv问题的适当方法。 - Nick
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。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接