45

equalsString 类中方法的代码是

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()，我们可以立即看到两个字符串不相等。

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

更新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;
}
4

8 回答 8

40

哈希码可能是对不平等的第一轮检查。但是，它提出了一些权衡。

  1. String哈希码是惰性计算的，尽管它们确实使用了“保护”值。如果您正在比较具有长生命周期的字符串（即，它们可能已经计算了哈希码），这不是问题。否则，您要么计算哈希码（可能很昂贵），要么在尚未计算哈希码时忽略检查。如果你有很多短命的字符串，你会更频繁地忽略检查而不是使用它。
  2. 在现实世界中，大多数字符串的前几个字符不同，因此首先检查哈希码不会节省太多。当然，也有例外（例如 URL），但同样，在现实世界的编程中它们很少发生。
于 2013-01-10T16:34:01.983 回答
15

这个问题其实已经被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;。

于 2013-01-10T16:43:43.080 回答
7

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

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

于 2013-01-10T16:21:52.313 回答
4

This can be a good idea for many use cases.

However, as a foundation class that is widely used in all kinds of applications, the author really has no idea whether this extra checking can save or hurt performance on average.

I'm gonna guess that the majority of String.equals() are invoked in a Hashmap, after the hash codes has been known to be equal, so testing hash codes again is pointless.

If we consider comparing 2 random strings, even with a small char set like US ASCII, it is very likely that the hashes are different, and char-by-char comparison fails on 1st char. So it'll be a waste to check hashes.

于 2013-01-10T17:17:23.793 回答
2

AFAIK，以下检查可以添加到字符串。这将检查是否设置了哈希码并且它们不同，那么字符串不能相等。

if (hash != 0 && anotherString.hash != 0 && hash != anotherString.hash)
    return false;
if (hash32 != 0 && anotherString.hash32 != 0 && hash32 != anotherString.hash32)
    return false;
于 2013-01-10T16:54:12.017 回答
0

字符串哈希码不是免费和自动可用的。为了依赖哈希码，必须对两个字符串都计算它，然后才能进行比较。由于可能发生冲突，如果哈希码相等，则需要进行第二次逐字符比较。

虽然对于普通程序员来说 String 看起来是不可变的，但它确实有一个私有字段来存储它的哈希码，一旦它被计算出来。但是，仅当首次需要哈希码时才计算此字段。从这里的字符串源代码可以看出：

 private int hash;

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

因此，首先计算哈希码是否有意义并不明显。对于您的特定情况（可能非常长的字符串的相同实例相互比较了很多次），它仍然可能是：profile.

于 2013-01-10T16:30:18.920 回答
0

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

字符串散列函数通常不会考虑非常长的字符串的所有字符。在这种情况下，如果我比较两个字符串，我可以首先比较散列函数使用的字符，而且我至少和检查散列一样快。但是如果这些字符没有区别，那么哈希值将是相同的，所以无论如何我必须比较完整的字符串。

总结：一个好的字符串比较永远不会慢，但通常比比较散列（以及在散列匹配时比较字符串）快得多。

于 2014-03-27T12:30:28.010 回答
0

我认为， hashCode() 可以更快地比较两个字符串。

论据？

反对该提议的论点：

  • 更多操作

hashcode()fromString必须访问字符串中的每个字符，并且必须2对每个字符进行计算。
所以我们需要一个带有n字符5*n操作（加载、乘法、查找/加载、乘法、存储）的字符串。两次，因为我们比较了两个字符串。（好吧，一个存储和一个加载并没有真正计入合理的实现。）
对于最好的情况，这使得对10*x长度为mandn的两个字符串的操作总数x=min(m,n)。最坏的情况10*x是x=m=n. 平均介于两者之间，也许(m*n)/2。

当前等于在最佳情况下3操作的实现需求。2加载，1比较。最糟糕的是3*x对长度为m和n的两个字符串的操作x=m=n。平均值介于两者之间，也许3*(m*n)/2。

  • 即使我们缓存了哈希，也不清楚我们是否保存了一些东西

我们必须分析使用模式。可能大多数时候，我们只会要求一次相等，而不是多次。即使我们多次询问，从缓存中节省时间也是不够的。

不直接反对速度，但仍然很好的反驳：

  • 反直观

我们不希望在 equals 中使用哈希码，因为我们肯定知道hash(a)==hash(b)对于某些a!=b. 每个阅读本文（以及有关散列的知识）的人都会想知道那里发生了什么。

  • 导致不良示例/意外行为

我已经可以看到关于 SO 的下一个问题：“我有一个包含数十亿次 'a' 的字符串。为什么将它与 equal() 与 'b' 进行比较需要很长时间？” :)

于 2013-01-10T18:01:58.943 回答