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

Question

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

score 460 · Accepted Answer

最適な実装は? それは使用パターンに依存するため、難しい質問です。

Josh Blochの「 Effective Java in Item 8」(第 2 版)では、ほぼすべての場合に妥当な適切な実装が提案されています。著者がそのアプローチが優れている理由を説明しているので、そこを調べるのが最善の方法です。

ショートバージョン

を作成し、ゼロ以外のint result値を割り当てます。
メソッドでテストされるすべてのフィールド について、次の方法でハッシュコードを計算します。fequals()c
- フィールド f が a の場合boolean: calculate (f ? 0 : 1);
- フィールド f がbyte、char、shortまたはの場合int: calculate (int)f;
- フィールド f が a の場合long: calculate (int)(f ^ (f >>> 32));
- フィールド f が a の場合float: calculate Float.floatToIntBits(f);
- フィールド f が a の場合:すべての long 値と同様に戻り値をdouble計算して処理します。Double.doubleToLongBits(f)
- フィールド f がオブジェクトの場合: メソッドの結果を使用するか、 hashCode()if の場合は 0を使用しf == nullます。
- フィールド f が配列の場合: すべてのフィールドを個別の要素として見て、再帰的にハッシュ値を計算し、次に説明するように値を結合します。
ハッシュ値cをresult次のように結合します。
```
result = 37 * result + c
```
戻るresult

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

score 151 · Accepted Answer

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

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

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

score 59 · Accepted Answer

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

score 17 · Accepted Answer

まず、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（）値を持っている必要があります

最後に、優れたハッシュ関数は、理想的なハッシュ関数に近づくように努める必要があります。

score 12 · Accepted Answer

about8.blogspot.com、あなたは言った

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

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

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

しかし

A.hashcode が B.hascode と等しい場合、A が B と等しくなければならないという意味ではありません

score 7 · Accepted Answer

Apache Commons Langには、 Effective Javahashcode()とequals()ロジックの適切な実装があります。HashCodeBuilderとEqualsBuilderを確認してください。

score 7 · Accepted Answer

Eclipse を使用する場合は、以下を生成equals()しhashCode()て使用できます。

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

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

score 6 · Accepted Answer

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

how-do-i-create-a-hash-table-in-java、特にjGuru FAQエントリの質問を検討すると、ハッシュコードを判断できる他の基準は次のとおりです。

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

score 4 · Accepted Answer

私があなたの質問を正しく理解していれば、あなたはカスタムコレクションクラス (つまり、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;
   }

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

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

score 2 · Accepted Answer

ApacheCommonsEqualsBuilderおよびHashCodeBuilderでリフレクションメソッドを使用します。

score 2 · Accepted Answer

@ 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をスキップしてください。醜いです。）

score 2 · Accepted Answer

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

score 2 · Accepted Answer

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

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

score 1 · Accepted Answer

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

score 1 · Accepted Answer

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

score 1 · Accepted Answer

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

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 のようなものを使用します。

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

score 0 · Accepted Answer

When combining hash values, I usually use the combining method that's used in the boost c++ library, namely:

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

This does a fairly good job of ensuring an even distribution. For some discussion of how this formula works, see the StackOverflow post: Magic number in boost::hash_combine

There's a good discussion of different hash functions at: http://burtleburtle.net/bob/hash/doobs.html

score -1 · Accepted Answer

単純なクラスの場合、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() と equals() の一貫性を保つことです: equals() が 2 つのオブジェクトに対して true を返す場合、hashCode() は同じ値を返す必要があります。equals() が false を返す場合、hashCode() は異なる値を返す必要があります。

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

20 に答える 20

ショートバージョン

Related

Reference