为什么在字符串的equals方法不使用哈希?(Why does the equals method

2019-07-18 01:42发布

的代码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()方法,马上就可以看到这两个字符串是不平等的。

我只是想,使用hashCode()方法可以在一个良好的过滤 equals

更新2:这里是一些代码,对我们这里所说的。

这是一个例子字符串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;
}

Answer 1:

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

  1. String散列码懒洋洋地计算,虽然他们使用“后卫”的价值。 如果你比较具有长寿命的字符串(例如,他们可能不得不计算的哈希码),这是没有问题的。 否则,你不得不拥有两种计算哈希码(潜在的昂贵),或忽略检查时的哈希码还没有计算呢。 如果你有很多短命的字符串,你会比你更经常将使用它忽略了检查。
  2. 在现实世界中,大多数的琴弦在它们前几个字符不同,所以你不会保存首先检查哈希码得多。 有,当然,例外(如URL),但同样,在现实世界中编程他们很少发生。


Answer 2:

这个问题实际上已经由JDK的开发者考虑。 我不能在找到各种消息 ,为什么它没有被包括在内。 增强也列在bug数据库 。

即,所提议的改变中的一个是:

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;



Answer 3:

1)计算的hashCode未必比直接比较字符串更快。

2)如果哈希码是相等的,该字符串可以仍然是不相等



Answer 4:

这对于许多用例是一个好主意。

然而,作为被广泛用于各种应用的基础类,笔者真的不知道这个额外的检查是否可以保存或损害的平均表现。

我要去猜测,多数String.equals()中的一个HashMap被调用时,哈希码一直被称为是相等 ,所以测试的散列码又是毫无意义的。

如果我们考虑比较2个随机字符串,即使有小的字符集如美国ASCII,它很可能哈希值是不同的,并且在第1字符字符逐字符比较失败。 所以它会检查哈希的浪费。



Answer 5:

据我所知,下面的检查可以添加到字符串。 此检查,如果哈希码设置,他们是不同的,那么字符串可以不相等。

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


Answer 6:

字符串哈希码是不是免费和自动。 为了依靠散列码,它必须被计算为两个字符串,然后才可以进行比较。 由于冲突是可能的,如果哈希码是相等的第二字符逐字符的比较是必要的。

虽然字符串出现通常的程序员为不可变的,它也有私有字段来存储它的哈希码一旦被计算出来。 然而,当首先需要哈希码本场只计算。 正如你可以从字符串源代码看这里 :

 private int hash;

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

因此,它是不是很明显,这是有道理的,首先计算哈希码。 针对您的特殊情况下,它可能仍然是(也许很长串的相同的情况下,彼此真的很多倍):轮廓。



Answer 7:

因为我认为,hashCode()方法可以使两个字符串比较快。

参数?

反对这项提议参数:

  • 更多操作

hashcode()String在字符串来访问每个字符和必须做2为每个字符计算。
因此,我们需要用一个字符串n字符5*n的操作(负载,乘法,查找/负载,乘法,商店)。 两次,因为我们比较两个字符串。 (好吧,一个商店和一个负载并不真正指望在一个合理的实现。)
为最好的情况下,这使得总的10*x为两个字符串长度的操作mnx=min(m,n) 最坏的情况是10*xx=m=n 。 之间,也许平均某处(m*n)/2

该电流等于在最好的情况下实施需要3操作。 2负荷, 1比较。 最差的是3*x为两个字符串长度的操作mnx=m=n 。 平均是某处也许之间, 3*(m*n)/2

  • 即使我们缓存哈希,目前尚不清楚的是我们保存的东西

我们来分析使用模式。 这可能是大部分的时间,我们只要求一个时间平等,而不是多次。 即使我们问多次,它可能是不够的有积蓄时间从缓存。

不是直接针对速度,但还是不错的反驳:

  • 直觉

我们不希望在平等的散列码,因为我们知道肯定hash(a)==hash(b)对于一些a!=b 。 每个人都在阅读本(约散列知识)将不知道正在发生的事情在那里。

  • 导致坏榜样/意外的行为

我已经可以看到这样一个问题:“我有一些十亿次‘A’的String为什么会采取永远把它与平等()对‘B’比较?” :)



Answer 8:

如果散列码取串的全部内容进去,然后计算具有n个字符的字符串的哈希码需要n个操作。 对于长字符串,这是一个很大。 比较两个字符串需要n个作业,如果它们是相同的,不超过计算散列更长。 但是,如果字符串不同,那么不同的是很可能被更早很多找到。

字符串散列函数通常不考虑很长的字符串中的所有字符。 在这种情况下,如果我比较两个字符串我可以先比较由哈希函数中使用的字符,我至少快检查哈希值。 但是,如果在这些字符没有区别,那么散列值将是相同的,所以我必须在满弦反正比较。

摘要:一个好的字符串比较是永远慢,但往往比较哈希值(和比较字符串时哈希匹配)快很多。



文章来源: Why does the equals method in String not use hash?