1. 概要

ハッシュはコンピュータサイエンスの基本的な概念です。

Javaでは、効率的なハッシュアルゴリズムが、 HashMap (この詳細な article をチェック)やHashSetなどの最も人気のあるコレクションの背後にあります。

このチュートリアルでは、 hashCode()がどのように機能するか、コレクションでどのように再生されるか、および正しく実装する方法に焦点を当てます。

2. データ構造でのhashCode()の使用

コレクションに対する最も単純な操作は、特定の状況では非効率になる可能性があります。

説明のために、これは線形検索をトリガーしますが、これは巨大なリストには非常に効果的ではありません。

List<String> words = Arrays.asList("Welcome", "to", "Baeldung");
if (words.contains("Baeldung")) {
    System.out.println("Baeldung is in the list");
}

Javaは、この問題を具体的に処理するための多数のデータ構造を提供します。 たとえば、いくつかのMapインターフェイスの実装はハッシュテーブルです。

ハッシュテーブルを使用する場合、これらのコレクションはhashCode()メソッドを使用して特定のキーのハッシュ値を計算します。次に、アクセス操作がはるかに効率的になるように、この値を内部的に使用してデータを格納します。

3. hashCode()のしくみを理解する

簡単に言えば、 hashCode()は、ハッシュアルゴリズムによって生成された整数値を返します。

等しいオブジェクト( equals()による)は、同じハッシュコードを返す必要があります。 異なるオブジェクトが異なるハッシュコードを返す必要はありません。

hashCode()の一般的な契約は次のように述べています。

  • Javaアプリケーションの実行中に同じオブジェクトで複数回呼び出される場合は常に、オブジェクトのequals比較で使用される情報が変更されていない限り、 hashCode()は常に同じ値を返す必要があります。 この値は、アプリケーションのある実行から同じアプリケーションの別の実行まで一貫性を保つ必要はありません。
  • equals(Object)メソッドに従って2つのオブジェクトが等しい場合、2つのオブジェクトのそれぞれで hashCode()メソッドを呼び出すと、同じ値が生成される必要があります。
  • equals(java .lang.Object)メソッドに従って2つのオブジェクトが等しくない場合、2つのオブジェクトのそれぞれで hashCode メソッドを呼び出すと、個別の整数を生成する必要はありません。結果。 ただし、開発者は、等しくないオブジェクトに対して個別の整数結果を生成すると、ハッシュテーブルのパフォーマンスが向上することに注意する必要があります。

「合理的に実用的である限り、クラス Objectによって定義されたhashCode()メソッドは、個別のオブジェクトに対して個別の整数を返します。 (これは通常、オブジェクトの内部アドレスを整数に変換することによって実装されますが、この実装手法はJavaTMプログラミング言語では必要ありません。)」

4. ナイーブなhashCode()の実装

上記のコントラクトに完全に準拠する単純なhashCode()実装は、実際には非常に簡単です。

これを示すために、メソッドのデフォルトの実装をオーバーライドするサンプルUserクラスを定義します。

public class User {

    private long id;
    private String name;
    private String email;

    // standard getters/setters/constructors
        
    @Override
    public int hashCode() {
        return 1;
    }
        
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null) return false;
        if (this.getClass() != o.getClass()) return false;
        User user = (User) o;
        return id == user.id 
          && (name.equals(user.name) 
          && email.equals(user.email));
    }
    
    // getters and setters here
}

User クラスは、それぞれのコントラクトに完全に準拠する equals() hashCode()の両方のカスタム実装を提供します。 さらに、 hashCode()が固定値を返すことには違法なことは何もありません。

ただし、この実装では、すべてのオブジェクトが同じ単一のバケットに格納されるため、ハッシュテーブルの機能が基本的にゼロに低下します。

このコンテキストでは、ハッシュテーブルルックアップは線形に実行され、実際の利点はありません。 これについてはセクション7で詳しく説明します。

5. hashCode()実装の改善

User クラスのすべてのフィールドを含めて、現在の hashCode()実装を改善し、等しくないオブジェクトに対して異なる結果を生成できるようにします。

@Override
public int hashCode() {
    return (int) id * name.hashCode() * email.hashCode();
}

この基本的なハッシュアルゴリズムは、前のアルゴリズムよりも明らかに優れています。 これは、nameおよびemailフィールドとidのハッシュコードを乗算するだけでオブジェクトのハッシュコードを計算するためです。

一般的に、 equals()の実装と一貫性を保つ限り、これは妥当な hashCode()の実装であると言えます。

6. 標準のhashCode()の実装

ハッシュコードの計算に使用するハッシュアルゴリズムが優れているほど、ハッシュテーブルのパフォーマンスが向上します。

2つの素数を使用して、計算されたハッシュコードにさらに一意性を追加する「標準」実装を見てみましょう。

@Override
public int hashCode() {
    int hash = 7;
    hash = 31 * hash + (int) id;
    hash = 31 * hash + (name == null ? 0 : name.hashCode());
    hash = 31 * hash + (email == null ? 0 : email.hashCode());
    return hash;
}

hashCode()メソッドと equals()メソッドが果たす役割を理解する必要がありますが、毎回最初から実装する必要はありません。 これは、ほとんどのIDEがカスタム hashCode()および equals()実装を生成できるためです。 また、Java 7以降、快適なハッシュのための Objects.hash()ユーティリティメソッドがあります。

Objects.hash(name, email)

IntelliJ IDEA は、次の実装を生成します。

@Override
public int hashCode() {
    int result = (int) (id ^ (id >>> 32));
    result = 31 * result + name.hashCode();
    result = 31 * result + email.hashCode();
    return result;
}

そして、Eclipseはこれを生成します。

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((email == null) ? 0 : email.hashCode());
    result = prime * result + (int) (id ^ (id >>> 32));
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    return result;
}

上記のIDEベースのhashCode()実装に加えて、たとえば Lombok を使用して、効率的な実装を自動的に生成することもできます。

この場合、lombok-maven依存関係をpom.xmlに追加する必要があります。

<dependency>
    <groupId>org.projectlombok</groupId>
    <artifactId>lombok-maven</artifactId>
    <version>1.16.18.0</version>
    <type>pom</type>
</dependency>

Userクラスに@EqualsAndHashCodeで注釈を付けるだけで十分です。

@EqualsAndHashCode 
public class User {
    // fields and methods here
}

同様に、 Apache Commons LangのHashCodeBuilderクラスhashCode()実装を生成する場合は、pomファイルに commons-langMaven依存関係を含めます。 :

<dependency>
    <groupId>commons-lang</groupId>
    <artifactId>commons-lang</artifactId>
    <version>2.6</version>
</dependency>

また、 hashCode()は次のように実装できます。

public class User {
    public int hashCode() {
        return new HashCodeBuilder(17, 37).
        append(id).
        append(name).
        append(email).
        toHashCode();
    }
}

一般に、 hashCode()の実装に関しては、普遍的なレシピはありません。 JoshuaBlochの効果的なJavaを読むことを強くお勧めします。 効率的なハッシュアルゴリズムを実装するための完全なガイドラインのリストを提供します。

ここで、これらの実装はすべて、何らかの形で番号31を使用していることに注意してください。 これは、31が優れた特性を持っているためです。 その乗算は、標準の乗算よりも高速なビット単位のシフトに置き換えることができます。

31 * i == (i << 5) - i

7. ハッシュ衝突の処理

ハッシュテーブルの固有の動作は、これらのデータ構造の関連する側面をもたらします。効率的なハッシュアルゴリズムを使用しても、2つ以上のオブジェクトが等しくない場合でも同じハッシュコードを持つ可能性があります。 したがって、ハッシュテーブルキーが異なっていても、ハッシュコードは同じバケットを指します。

この状況は一般にハッシュ衝突として知られており、それを処理するためのさまざまな方法が存在し、それぞれに長所と短所があります。 JavaのHashMapは、衝突を処理するために個別の連鎖方法を使用します。

「2つ以上のオブジェクトが同じバケットを指している場合、それらは単にリンクリストに格納されます。 このような場合、ハッシュテーブルはリンクリストの配列であり、同じハッシュを持つ各オブジェクトは、配列のバケットインデックスでリンクリストに追加されます。

最悪の場合、複数のバケットにリンクリストがバインドされ、リスト内のオブジェクトの取得が直線的に実行されます。」

ハッシュ衝突の方法論は、 hashCode()を効率的に実装することが非常に重要である理由を一言で示しています

Java 8は、HashMap実装に興味深い拡張機能をもたらしました。 バケットサイズが特定のしきい値を超えると、ツリーマップがリンクリストに置き換わります。 これにより、悲観的な O(n)の代わりに、 O( logn ルックアップを実現できます。

8. 簡単なアプリケーションの作成

次に、標準の hashCode()実装の機能をテストします。

いくつかのUserオブジェクトをHashMapに追加し、 SLF4J を使用して、メソッドが呼び出されるたびにコンソールにメッセージを記録する単純なJavaアプリケーションを作成しましょう。 。

サンプルアプリケーションのエントリポイントは次のとおりです。

public class Application {

    public static void main(String[] args) {
        Map<User, User> users = new HashMap<>();
        User user1 = new User(1L, "John", "john@domain.com");
        User user2 = new User(2L, "Jennifer", "jennifer@domain.com");
        User user3 = new User(3L, "Mary", "mary@domain.com");

        users.put(user1, user1);
        users.put(user2, user2);
        users.put(user3, user3);
        if (users.containsKey(user1)) {
            System.out.print("User found in the collection");
        }
    }
}

そして、これは hashCode()の実装です。

public class User {

    // ...

    public int hashCode() {
        int hash = 7;
        hash = 31 * hash + (int) id;
        hash = 31 * hash + (name == null ? 0 : name.hashCode());
        hash = 31 * hash + (email == null ? 0 : email.hashCode());
        logger.info("hashCode() called - Computed hash: " + hash);
        return hash;
    }
}

ここで重要なのは、オブジェクトがハッシュマップに格納され、 containsKey()メソッドでチェックされるたびに、 hashCode()が呼び出され、計算されたハッシュコードが出力されることです。コンソールに出て:

[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -282948472
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -1540702691
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819
User found in the collection

9. 結論

効率的なhashCode()実装を作成するには、いくつかの数学的概念を組み合わせる必要があることは明らかです(つまり、 素数と任意の数)、論理的および基本的な数学演算。

とにかく、これらの手法にまったく頼ることなく、 hashCode()を効果的に実装できます。 ハッシュアルゴリズムが等しくないオブジェクトに対して異なるハッシュコードを生成し、それが equals()の実装と一致していることを確認する必要があります。

いつものように、この記事に示されているすべてのコード例は、GitHubから入手できます。