コレクションの hashCode メソッドの最適な実装

https://stackoverflow.com/questions/113511

02-07-2019
|

質問

最適な実装をどのように決定するか hashCode() コレクションのメソッド (equals メソッドが正しくオーバーライドされていると仮定します) ?

解決

最良の実装?それは使用パターンによって異なるため、難しい質問です。

ほぼすべてのケースにおいて、適切な実装が提案されています。 ジョシュ・ブロックさんの 効果的なJava 項目 8 (第 2 版)。一番良いのは、そのアプローチが良い理由を著者がそこで説明しているので、そこで調べることです。

ショートバージョン

を作成します int result そして割り当てます ゼロ以外の 価値。
のために あらゆる分野 f でテストされました equals() メソッド、ハッシュコードを計算する c による：
- フィールド f が a の場合、 boolean:計算する (f ? 0 : 1);
- フィールド f が a の場合、 byte, char, short または int:計算する (int)f;
- フィールド f が a の場合、 long:計算する (int)(f ^ (f >>> 32));
- フィールド f が a の場合、 float:計算する Float.floatToIntBits(f);
- フィールド f が a の場合、 double:計算する Double.doubleToLongBits(f) そして戻り値を他の長い値と同様に処理します。
- フィールド f が物体:の結果を使用します。 hashCode() メソッドまたは 0 の場合 f == null;
- フィールド f が配列:すべてのフィールドを個別の要素として参照し、ハッシュ値を計算します。 再帰的なファッション 次に説明するように値を組み合わせます。
ハッシュ値を結合する c と result:
```
result = 37 * result + c
```
戻る result

これにより、ほとんどの使用状況でハッシュ値が適切に分散されるはずです。

他のヒント

dmeister が推奨する効果的な Java 実装に満足している場合は、独自のローリングの代わりにライブラリ呼び出しを使用できます。

@Override
public int hashCode() {
    return Objects.hashCode(this.firstName, this.lastName);
}

これにはグアバ (com.google.common.base.Objects.hashCode) または Java 7 の標準ライブラリ (java.util.Objects.hash) ただし、同じように機能します。

Eclipse が提供する非常に優れた機能を使用することをお勧めします。これにより、ビジネスロジックの開発に労力とエネルギーを注ぐことができます。

これとリンクしているのですが、 Android ドキュメント (ウェイバックマシン) そして Github にある自分のコード, 、Java 全般で動作します。私の答えは次の拡張です dマイスターの答えコードだけで、非常に読みやすく、理解しやすくなります。

@Override 
public int hashCode() {

    // Start with a non-zero constant. Prime is preferred
    int result = 17;

    // Include a hash for each field.

    // Primatives

    result = 31 * result + (booleanField ? 1 : 0);                   // 1 bit   » 32-bit

    result = 31 * result + byteField;                                // 8 bits  » 32-bit 
    result = 31 * result + charField;                                // 16 bits » 32-bit
    result = 31 * result + shortField;                               // 16 bits » 32-bit
    result = 31 * result + intField;                                 // 32 bits » 32-bit

    result = 31 * result + (int)(longField ^ (longField >>> 32));    // 64 bits » 32-bit

    result = 31 * result + Float.floatToIntBits(floatField);         // 32 bits » 32-bit

    long doubleFieldBits = Double.doubleToLongBits(doubleField);     // 64 bits (double) » 64-bit (long) » 32-bit (int)
    result = 31 * result + (int)(doubleFieldBits ^ (doubleFieldBits >>> 32));

    // Objects

    result = 31 * result + Arrays.hashCode(arrayField);              // var bits » 32-bit

    result = 31 * result + referenceField.hashCode();                // var bits » 32-bit (non-nullable)   
    result = 31 * result +                                           // var bits » 32-bit (nullable)   
        (nullableReferenceField == null
            ? 0
            : nullableReferenceField.hashCode());

    return result;

}

編集

通常、オーバーライドするときは、 hashcode(...), 、オーバーライドすることもできます equals(...). 。これから実装する人、またはすでに実装している人のために equals, 、ここが良い参考資料です私のGithubから...

@Override
public boolean equals(Object o) {

    // Optimization (not required).
    if (this == o) {
        return true;
    }

    // Return false if the other object has the wrong type, interface, or is null.
    if (!(o instanceof MyType)) {
        return false;
    }

    MyType lhs = (MyType) o; // lhs means "left hand side"

            // Primitive fields
    return     booleanField == lhs.booleanField
            && byteField    == lhs.byteField
            && charField    == lhs.charField
            && shortField   == lhs.shortField
            && intField     == lhs.intField
            && longField    == lhs.longField
            && floatField   == lhs.floatField
            && doubleField  == lhs.doubleField

            // Arrays

            && Arrays.equals(arrayField, lhs.arrayField)

            // Objects

            && referenceField.equals(lhs.referenceField)
            && (nullableReferenceField == null
                        ? lhs.nullableReferenceField == null
                        : nullableReferenceField.equals(lhs.nullableReferenceField));
}

まず、equals が正しく実装されていることを確認してください。から IBM DeveloperWorks の記事:

対称：2 つの参照 a と b の場合、b.equals(a) の場合に限り、a.equals(b)

反射性:すべての非 null 参照の場合、a.equals(a)

推移性:a.equals(b) と b.equals(c) の場合、a.equals(c)

次に、hashCode との関係が連絡先を尊重していることを確認します (同じ記事から)。

hashCode() との一貫性:2 つの等しいオブジェクトは同じ hashCode() 値を持つ必要があります

最後に、優れたハッシュ関数は、理想的なハッシュ関数.

about8.blogspot.com、あなたは言いました

equals() が 2 つのオブジェクトに対して true を返す場合、hashCode() は同じ値を返す必要があります。equals() が false を返した場合、hashCode() は異なる値を返す必要があります

私はあなたに同意できません。2 つのオブジェクトが同じハッシュコードを持っている場合、それらが等しいことを意味する必要はありません。

A が B と等しい場合、A.hashcode は B.hascode と等しくなければなりません

しかし

A.hashcode が B.hascode に等しい場合、A が B に等しい必要があるという意味ではありません

Eclipseを使用する場合は、次のように生成できます。 equals() そして hashCode() 使用:

ソース -> hashCode()とequals()を生成します。

この機能を使用すると、次のように決定できます。 どのフィールド 等価性とハッシュコードの計算に使用すると、Eclipse が対応するメソッドを生成します。

の良い実装があります 効果的なJavaさんの hashcode() そして equals() ロジックイン Apache Commons Lang. 。チェックアウトハッシュコードビルダーそしてイコールビルダー.

他のより詳細な回答（コードの観点から）を完了するための簡単なメモ：

という疑問を考えてみると Javaでハッシュテーブルを作成する方法そして特に jGuru FAQ エントリー, ハッシュコードが判断される他の基準は次のとおりだと思います。

同期 (アルゴは同時アクセスをサポートしていますか)?
フェールセーフ反復 (反復中に変更されるコレクションをアルゴが検出しますか)
null 値 (ハッシュコードはコレクション内の null 値をサポートしますか)

あなたの質問を正しく理解できれば、カスタムコレクションクラス（つまり、Collection インターフェイスから拡張された新しいクラス）、hashCode() メソッドを実装したいとします。

コレクションクラスが AbstractList を拡張している場合は、それについて心配する必要はありません。すべてのオブジェクトを反復処理し、それらの hashCodes() を一緒に追加することで動作する、equals() と hashCode() の実装がすでに存在します。

   public int hashCode() {
      int hashCode = 1;
      Iterator i = iterator();
      while (i.hasNext()) {
        Object obj = i.next();
        hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
      }
  return hashCode;
   }

ここで、特定のクラスのハッシュコードを計算する最良の方法が必要な場合、通常は ^ (ビットごとの排他的論理和) 演算子を使用して、equals メソッドで使用するすべてのフィールドを処理します。

public int hashCode(){
   return intMember ^ (stringField != null ? stringField.hashCode() : 0);
}

@about8 :そこにはかなり深刻なバグがあります。

Zam obj1 = new Zam("foo", "bar", "baz");
Zam obj2 = new Zam("fo", "obar", "baz");

同じハッシュコード

あなたはおそらく次のようなものを望んでいます

public int hashCode() {
    return (getFoo().hashCode() + getBar().hashCode()).toString().hashCode();

(最近では Java で int から直接 hashCode を取得できますか?自動キャストを行っていると思います。その場合は、見苦しいので toString をスキップしてください。)

特にコレクションを求められたので、他の回答でまだ言及されていない側面を追加したいと思います。HashMap は、キーがコレクションに追加された後にそのキーのハッシュコードが変更されることを期待しません。目的全体が無効になってしまうでしょう...

Apache Commons のリフレクションメソッドを使用するイコールビルダーそしてハッシュコードビルダー.

可能な範囲にわたってハッシュ値を均等に分散するハッシュ方法は、適切な実装です。効果的な Java ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=Effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxiZw&hl=ja&sa=X&oi=book_result&resnum=1&ct=result )、そこにはハッシュコードの実装に関する良いヒントがあります (項目 9 だと思います...)。

私はユーティリティメソッドを使用することを好みます クラス Objects からの Google Collections ライブラリ それはコードをきれいに保つのに役立ちます。よく equals そして hashcode メソッドは IDE のテンプレートから作成されているため、読みやすいものではありません。

小さなラッパーを使用しています Arrays.deepHashCode(...) パラメータとして指定された配列を正しく処理するため

public static int hash(final Object... objects) {
    return Arrays.deepHashCode(objects);
}

ここでは、スーパークラスロジックを考慮した別の JDK 1.7 以降のアプローチのデモンストレーションを示します。オブジェクトクラス hashCode() が考慮されており、純粋な JDK 依存関係があり、余分な手動作業がないため、非常に便利だと思います。ご注意ください Objects.hash() null トレラントです。

何も入ってないよ equals() 実装ですが、実際にはもちろん必要になります。

import java.util.Objects;

public class Demo {

    public static class A {

        private final String param1;

        public A(final String param1) {
            this.param1 = param1;
        }

        @Override
        public int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param1);
        }

    }

    public static class B extends A {

        private final String param2;
        private final String param3;

        public B(
            final String param1,
            final String param2,
            final String param3) {

            super(param1);
            this.param2 = param2;
            this.param3 = param3;
        }

        @Override
        public final int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param2,
                this.param3);
        }
    }

    public static void main(String [] args) {

        A a = new A("A");
        B b = new B("A", "B", "C");

        System.out.println("A: " + a.hashCode());
        System.out.println("B: " + b.hashCode());
    }

}

標準の実装は弱いため、これを使用すると不要な衝突が発生します。想像してみてください

class ListPair {
    List<Integer> first;
    List<Integer> second;

    ListPair(List<Integer> first, List<Integer> second) {
        this.first = first;
        this.second = second;
    }

    public int hashCode() {
        return Objects.hashCode(first, second);
    }

    ...
}

今、

new ListPair(List.of(a), List.of(b, c))

そして

new ListPair(List.of(b), List.of(a, c))

同じものを持っています hashCode, 、つまり 31*(a+b) + c に使用される乗数として List.hashCode ここで再利用されます。もちろん、衝突は避けられませんが、不必要な衝突を引き起こすのは単なる...不必要です。

実質的に賢い使い方は何もありません 31. 。情報の損失を避けるために、乗数は奇数でなければなりません (偶数の乗数は少なくとも最上位ビットを失い、4 の倍数は 2 を失います)。任意の奇数の乗数を使用できます。乗算器が小さいと計算が高速になる可能性がありますが (JIT はシフトと加算を使用できます)、最新の Intel/AMD では乗算のレイテンシが 3 サイクルしかないことを考えると、これはほとんど問題になりません。また、乗算器が小さいと、小さい入力に対して衝突が多くなり、問題になる場合があります。

環 Z/(2**32) では素数は意味を持たないため、素数を使用することは無意味です。

したがって、ランダムに選択された大きな奇数を使用することをお勧めします (素数を自由に取ってください)。i86/amd64 CPU は、単一の符号付きバイトに収まるオペランドに短い命令を使用できるため、109 のような乗算器では速度がわずかに向上します。衝突を最小限に抑えるには、0x58a54cf5 などを使用します。

異なる場所で異なる乗算器を使用することは役に立ちますが、おそらく追加の作業を正当化するには十分ではありません。

ハッシュ値を結合するときは、通常、boost C++ ライブラリで使用される結合メソッドを使用します。

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

これは、均一な分布を確保する上でかなりうまく機能します。この式がどのように機能するかについては、StackOverflow の投稿を参照してください。 boost::hash_combine のマジックナンバー

さまざまなハッシュ関数についての詳しい説明は次の場所にあります。 http://burtleburtle.net/bob/hash/doobs.html

単純なクラスの場合、多くの場合、equals() 実装によってチェックされるクラスフィールドに基づいて hashCode() を実装するのが最も簡単です。

public class Zam {
    private String foo;
    private String bar;
    private String somethingElse;

    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        if (obj == null) {
            return false;
        }

        if (getClass() != obj.getClass()) {
            return false;
        }

        Zam otherObj = (Zam)obj;

        if ((getFoo() == null && otherObj.getFoo() == null) || (getFoo() != null && getFoo().equals(otherObj.getFoo()))) {
            if ((getBar() == null && otherObj. getBar() == null) || (getBar() != null && getBar().equals(otherObj. getBar()))) {
                return true;
            }
        }

        return false;
    }

    public int hashCode() {
        return (getFoo() + getBar()).hashCode();
    }

    public String getFoo() {
        return foo;
    }

    public String getBar() {
        return bar;
    }
}

最も重要なことは、 hashCode() とquals() の一貫性を保つことです。equals() が 2 つのオブジェクトに対して true を返す場合、hashCode() は同じ値を返す必要があります。equals() が false を返した場合、hashCode() は異なる値を返す必要があります。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow