为什么String类中的equals方法不使用哈希(hash)？

Question

String类中equals方法的代码如下：

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = offset;
            int j = anotherString.offset;
            while (n-- != 0) {
                if (v1[i++] != v2[j++])
                    return false;
            }
            return true;
        }
    }
    return false;
}

我有一个问题-为什么这个方法不使用hashCode()？

据我所知，hashCode()可以快速比较两个字符串。

更新：我知道，两个不相等的字符串可能具有相同的散列值。但是，两个相等的字符串具有相等的散列值。因此，通过使用hashCode()，我们可以立即看出两个字符串是否不相等。

我只是认为在equals中使用hashCode()可以成为一个良好的过滤器。

更新2：这里是一些我们正在讨论的代码示例。

这是一个String方法equals可能看起来像的示例

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        if (hashCode() == anotherString.hashCode()){
            int n = count;
            if (n == anotherString.count) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = offset;
                int j = anotherString.offset;
                while (n-- != 0) {
                    if (v1[i++] != v2[j++])
                        return false;
                }
                return true;
            }
        }else{
            return false;
        }
    }
    return false;
}

- Mary Ryllo

---

两个完全不同的字符串可能具有相同的哈希码。哈希码由表示为最大值为2^31的整数，那么在世界上是否真的存在足够多的不同字符串，使得它们可以通过哈希码唯一地识别？ - BalusC

如果已经进行了设置，那么这将使其更快（可能还没有设置）。检查起来并不难，所以我也不明白为什么没有检查。 - Peter Lawrey

@BalusC 如果哈希码已设置且不同，则仍需进行完整的相等性检查或取消哈希码。 - Peter Lawrey

如果字符串不相等，这种方法的效率会降低，而我敢打赌这种情况比比较相等的字符串更常见。 - BalusC

如果按照那种方式实现，我很确定节约的成本不会引起任何人的注意，但是却需要在一个必须是100%牢固稳定的类中进行更多测试。在您绝对确定它将产生真正的影响之前，永远不要以性能换取简单。 - Bill K

Answer 1

哈希码可以作为第一轮不等检查。然而，这样做会有一些权衡。

1. String 的哈希码是懒计算的，虽然它们使用了“保护”值。如果你比较寿命长的字符串（即它们可能已经计算出哈希码），那么这不是问题。否则，你要么计算哈希码（可能很昂贵），要么在哈希码尚未计算时忽略检查。如果你有很多短暂存在的字符串，那么你会更经常地忽略检查而不是使用它。
2. 在现实世界中，大多数字符串在前几个字符上就不同了，因此你不会通过首先检查哈希码来节省太多时间。当然，也有例外情况（如URL），但在真实的编程中频率较低。

- parsifal

---

实际情况是，大多数字符串在前几个字符上就已经不同了，因此先检查哈希码不能节省太多时间。这只是一个模棱两可的措辞，可能会让初学者感到困惑。有关"weasel word"的解释，请参见http://en.wikipedia.org/wiki/Weasel_word。 - Sedat Kapanoglu

@ssg - 不，这是承认没有绝对的事情，并且设计的一部分是找出常见情况并为其进行优化。当然，这也意味着如果你为不常见的情况进行优化，你将不得不接受你所做的决定。这是初学者应该早期学习的内容。 - parsifal

听起来你只是把个人观点当作事实来陈述。你关于答案中的常见情况的断言与你的评论“每个人都应该找出自己的常见情况”相矛盾。 - Sedat Kapanoglu

@ssg - 如果你对我依靠自己的经验来评论感到不满，那么我要指出，在涉及到“String”时，我是借鉴了Gosling、Bloch、Lea等人的经验。我只是运用自己的经验来理解他们所做的权衡。 - parsifal

你在回答中的陈述听起来不像是基于实现决策假设的事实。相反，它听起来像是你有一个科学的、经验证实的普遍适用于一切的事实。这就是狡猾之处。我认为这会给初学者带来误导。得出这样的捷径结论是很危险的。我原以为你是建议初学者去研究，但你说你没有这么说过。所以现在这个声明更加危险了。 - Sedat Kapanoglu

Answer 2

这个问题实际上已经被JDK的开发人员考虑过了。在各种消息中我没有找到为什么它没有被包含的原因。这个增强功能还在错误数据库中列出。

也就是说，其中一个建议的更改是：

public boolean equals(Object anObject) {
    if (this == anObject) // 1st check identitiy
        return true;
    if (anObject instanceof String) { // 2nd check type
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) { // 3rd check lengths
            if (n != 0) { // 4th avoid loading registers from members if length == 0
                int h1 = hash, h2 = anotherString.hash;
                if (h1 != 0 && h2 != 0 && h1 != h2) // 5th check the hashes
                    return false;

还有一种讨论是使用 == 来比较字符串 (即如果两个字符串都是被池化的: if (this != anotherString) return false;)。

- assylias

---

@MaryRyllo 添加了一个到错误数据库的链接。 - assylias

哇，他们说建议很合理！ - Audrius Meškauskas

@AudriusMeškauskas 你为什么认为它们不是呢？它只增加了3个整数比较，可以节省整个O(n)循环。 - assylias

天哪，那个错误报告真是不可思议。让我头晕目眩。我希望@Tom Hawtin - tackline能回答这个问题！ - kevinarpe

Answer 3

1) 计算hashCode可能不比直接比较字符串快。

2) 如果hashCode相等，字符串仍然可能不相等。

- MrSmith42

---

我知道关于#2的事情。请看我的更新。我们只计算一次hashCode，但可以多次调用equals方法。 - Mary Ryllo

@assylias：如果hashCode已经被计算过了，那么先比较它们可能是一个好主意，只有在hashCode相等的情况下才比较字符串。但是如果两个字符串的hashCodes之前没有被计算过，直接比较字符串会更快。 - MrSmith42

我不确定为什么这个答案会得到这么多赞 - 目前有一个提案正在等待批准，该提案详细说明了问题中的更改 - 如果它显然是有害的，那么它就会被拒绝... - assylias

@assylias：我的回答并不意味着添加hashCode比较是一个坏主意。它只列出了可能导致当前设计决策的原因。 - MrSmith42

Answer 4

这对许多用例来说可能是个好主意。

然而，作为一种广泛应用于各种应用程序的基础类，作者真的不知道这种额外检查是否会平均节约或损害性能。

我猜大多数String.equals()在哈希映射中被调用，在哈希码相等之后，再次测试哈希码是没有意义的。

如果我们考虑比较两个随机字符串，即使使用像美国ASCII这样的小字符集，哈希值也很可能不同，并且逐个字符比较会在第一个字符上失败。因此，检查哈希值将是浪费时间。

- irreputable

Answer 5

据我所知，可以在String类中添加以下检查。如果哈希码已设置且不同，则这些字符串不相等。

if (hash != 0 && anotherString.hash != 0 && hash != anotherString.hash)
    return false;
if (hash32 != 0 && anotherString.hash32 != 0 && hash32 != anotherString.hash32)
    return false;

- Peter Lawrey

---

我认为，如果分析表明这些情况经常匹配（因此额外的代码平均提高了方法的速度），将其添加到当前实现可能是一个好主意。 - MrSmith42

哦，四年前提交的。:P - Peter Lawrey

@PeterLawrey 不确定为什么几个月前他们推出重新设计的字符串类时它没有被关闭（无论是积极还是消极）。 - assylias

Answer 6

字符串哈希码不是免费和自动提供的。为了依赖哈希码，必须对两个字符串进行计算，然后才能进行比较。由于可能存在碰撞，如果哈希码相等，则需要第二个逐个字符的比较。

尽管对于通常的程序员来说，String看起来是不可变的，但它确实有一个私有字段来存储其哈希码一旦计算出来。但是，只有在第一次需要哈希码时才会计算此字段。正如您可以从String源代码here中看到的那样：

 private int hash;

 public int hashCode() {
      int h = hash;
      if (h == 0) {
         ...
         hash = h;  
      }
      return h;
 }

因此，首先计算哈希码并不明显是有意义的。对于您特定的情况（也许同一实例的非常长的字符串需要进行大量比较），仍然可能是：进行性能分析。

- Audrius Meškauskas

---

可以先检查两个字符串的哈希码是否可用，如果可用则进行比较，否则继续使用正常算法。 - assylias

问题是为什么String＃equals不使用String＃hashcode加速测试。 - assylias

Answer 7

如果哈希码考虑了字符串的全部内容，那么计算一个长度为n的字符串的哈希码需要n次操作。对于长字符串来说，这是很多的。如果两个字符串相同，则比较它们需要n次操作，不会比计算哈希码更慢。但是，如果这些字符串不同，那么差异很可能会更早地被发现。

字符串哈希函数通常不考虑非常长的字符串中的所有字符。在这种情况下，如果我比较两个字符串，我可以先比较哈希函数使用的字符，这样至少与检查哈希值一样快。但是，如果这些字符没有任何区别，那么哈希值将是相同的，因此我仍然必须比较完整的字符串。

总结：良好的字符串比较永远不会比比较哈希值（以及在哈希值匹配时比较字符串）更慢，而且通常要快得多。

- gnasher729

---

该建议不需要计算哈希码 - 它仅在已经计算（并缓存）的情况下比较它们。 - assylias

Answer 8

据我所知，hashCode() 可以更快地比较两个字符串。

反对意见：

- 更多的操作

String 的 hashcode() 方法必须访问字符串中的每个字符，并且对于每个字符需要进行 2 次计算。因此，对于一个长度为 n 的字符串，我们需要进行 5n 次操作（加载、乘法、查找/加载、乘法、存储）。由于我们要比较两个字符串，所以需要进行两次这样的操作（好吧，在合理的实现中，一次存储和一次加载并不真正计入操作次数）。对于最好的情况，对于长度为 m 和 n 的两个字符串，总共需要进行 10x 次操作，其中 x=min(m,n)。最坏的情况是 x=m=n，需要进行 10x 次操作。平均情况介于两者之间，可能是 (m*n)/2。

当前等于实现在最好的情况下需要 3 次操作。 2 次加载，1 次比较。最坏的情况是两个长度为 m 和 n 的字符串需要 3*x 次操作，其中 x=m=n。平均情况介于两者之间，可能是 3*(m*n)/2。

• 即使我们缓存了哈希值，也不清楚是否会节省时间。

我们必须分析使用模式。很可能大部分时间，我们只会一次询问 equals，而不是多次。即使我们多次询问，缓存也可能无法节省时间。

虽然不直接针对速度，但仍然是好的反驳理由：

• 反直觉

我们不希望在 equals 中看到哈希码，因为我们可以确定某些 a!=b 时 hash(a)==hash(b)。阅读此文的每个人（以及了解哈希的知识）都会想知道发生了什么。

• 导致错误的示例/意外行为

我已经能够预见下一个SO的问题：“ 我有一个字符串，其中有数十亿次的 'a'。为什么使用equal()与 'b'进行比较需要花费很长时间？”:)

- tb-

---

这个问题不是关于在调用equals时计算哈希码，而是检查哈希码是否已经被计算过，如果已经计算过，则使用它，如果没有，则继续使用通常的方法。在你最新的例子中，额外的惩罚将是几个机器指令 if (hash == 0 /*即尚未计算*/) goto usual method;。 - assylias