45

The code of the equals method in class String is

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

I have a question - why does this method not use hashCode() ?

As far as I know, hashCode() can compare two strings rapidly.

UPDATE: I know, that two unequal strings, can have same hashes. But two equal strings have equal hashes. So, by using hashCode(), we can immediately see that two strings are unequal.

I'm simply thinking that using hashCode() can be a good filter in equals.

UPDATE 2: Here some code, about we are talking here.

It is an example how String method equals can look like

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の開発者によって検討されています。なぜそれが含まれていなかったのか、私は様々なメッセージの中で見つけることができませんでした。拡張機能はバグデータベースにもリストされています。

つまり、提案された変更の1つは次のとおりです。

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

これは、多くのユースケースにとって良い考えです。

ただし、あらゆる種類のアプリケーションで広く使用されている基礎クラスとして、作成者は、この追加のチェックが平均してパフォーマンスを節約または低下させることができるかどうかを実際には知りません。

ハッシュコードが等しいことがわかった後String.equals()、大部分がハッシュマップで呼び出されると推測するので、ハッシュコードを再度テストしても意味がありません。

US ASCIIのような小さな文字セットを使用しても、2つのランダムな文字列を比較することを検討すると、ハッシュが異なる可能性が高く、1文字目では文字ごとの比較が失敗します。したがって、ハッシュをチェックするのは無駄になります。

于 2013-01-10T17:17:23.793 に答える
2

私の知る限り、次のチェックを文字列に追加できます。これは、ハッシュ コードが設定されていてそれらが異なる場合、文字列が等しくないことを確認します。

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

文字列ハッシュ コードは、無料で自動的に利用できるわけではありません。ハッシュ コードに依存するためには、両方の文字列を計算してから比較する必要があります。衝突が発生する可能性があるため、ハッシュ コードが等しい場合は、2 番目の文字ごとの比較が必要です。

String は、通常のプログラマーには不変に見えますが、計算されたハッシュコードを格納するためのプライベート フィールドがあります。ただし、このフィールドはハッシュコードが最初に要求されたときにのみ計算されます。こちらの文字列ソースコードからわかるように:

 private int hash;

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

したがって、最初にハッシュコードを計算することが理にかなっていることは明らかではありません。あなたの特定のケース（おそらく、非常に長い文字列の同じインスタンスが何度も互いに比較される可能性があります）では、それでもプロファイルである可能性があります。

于 2013-01-10T16:30:18.920 に答える
0

私が思うに、hashCode() は 2 つの文字列の比較をより迅速に行うことができます。

引数？

この提案に対する反論:

  • その他の操作

hashcode()fromStringは String 内のすべての文字にアクセスする必要があり2、すべての文字に対して計算を行う必要があります。そのため、文字操作 (ロード、乗算、ルックアップ/ロード、乗算、ストア)
を含む文字列が必要です。2 つの文字列を比較するため、2 回です。(わかりました、1 つのストアと 1 つのロードは、合理的な実装では実際にはカウントされません。)最良の場合、これにより、長さとおよびの 2 つの文字列に対する操作 の合計が作成されます。最悪の場合は. 間のどこかの平均、おそらく。n5*n
10*xmnx=min(m,n)10*xx=m=n(m*n)/2

現在は、最良の場合の操作における実装の必要性に等しくなります3。2負荷、1比較します。最悪なのは3*x、長さ および の 2 つの文字列に対するm操作nですx=m=n。平均は、おそらく の間のどこかにあります3*(m*n)/2。

  • ハッシュをキャッシュしても、何かを保存していることは明らかではありません

使用パターンを分析する必要があります。ほとんどの場合、equals を複数回ではなく 1 回だけ要求する可能性があります。何度も尋ねたとしても、キャッシュによる時間の節約には十分ではありません。

速度に直接反対するわけではありませんが、それでも良い反論があります。

  • 直感に反する

一部hash(a)==hash(b)のa!=b. これを読んでいる人 (およびハッシュについての知識を持っている人) は、そこで何が起こっているのか不思議に思うでしょう。

  • 悪い例/予期しない動作につながる

SO に関する次の質問はすでに確認できます。:)

于 2013-01-10T18:01:58.943 に答える
0

ハッシュ コードが文字列の内容全体を考慮する場合、n 文字の文字列のハッシュ コードを計算するには n 操作が必要です。長い弦の場合、それはたくさんあります。2 つの文字列を比較するには、同じ場合は n 回の操作が必要であり、ハッシュの計算より長くはありません。しかし、文字列が異なる場合は、違いがはるかに早く見つかる可能性があります。

通常、文字列ハッシュ関数は、非常に長い文字列のすべての文字を考慮しません。その場合、2 つの文字列を比較すると、最初にハッシュ関数で使用される文字を比較でき、少なくともハッシュをチェックするのと同じくらい高速です。しかし、これらの文字に違いがなければ、ハッシュ値は同じになるため、とにかく文字列全体を比較する必要があります。

概要: 優れた文字列比較は決して遅くはありませんが、多くの場合、ハッシュを比較する (およびハッシュが一致する場合に文字列を比較する) よりもはるかに高速です。

于 2014-03-27T12:30:28.010 に答える