1概要

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

Javaでは、


https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.htmlのように、効率的なハッシュアルゴリズムが利用可能な最も人気のあるコレクションの一部を支えています。

（

HashMap

の詳細については、リンクを確認してください:/java-hashmap[この記事]）および


https://docs.oracle.com/javase/7/docs/api/java/util/HashSet

.html[ハッシュセット].__

この記事では、

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

インターフェース実装はhttps://en.wikipedia.org/wiki/Hash__table[ハッシュテーブル]です。

ハッシュテーブルを使用する場合、これらのコレクションは__hashCode（）メソッドを使用して特定のキーのハッシュ値を計算し、データを格納するためにこの値を内部的に使用するので、アクセス操作ははるかに効率的です。


3

hashCode（）

の機能を理解する

簡単に言うと、

hashCode（）

はハッシュアルゴリズムによって生成された整数値を返します。

等しいオブジェクトは（

equals（）

に従って）同じハッシュコードを返す必要があります。オブジェクトごとに異なるハッシュコードを返す必要はありません。


hashCode（）

の一般規約は次のように述べています。

  • それが同じオブジェクトに対して2回以上呼び出されるときはいつでも

Javaアプリケーションの実行では、オブジェクトの等価比較で使用される情報が変更されていない限り、

hashCode（）

は常に同じ値を返す必要があります。この値は、アプリケーションの実行ごとに同じアプリケーションの実行ごとに一貫性を保つ必要はありません。


  • equals（Object）

    メソッドに従って2つのオブジェクトが等しい場合、

次に、2つのオブジェクトのそれぞれで

hashCode（）

メソッドを呼び出すと、同じ値が生成されます。

  • 2つのオブジェクトが次のように等しくない場合は必須ではありません



equals(java.lang.Object)


メソッドを呼び出してから呼び出します。 2つのオブジェクトそれぞれの

hashCode

メソッドは、異なる整数結果を生成する必要があります。ただし、開発者は、等しくないオブジェクトに対して個別の整数結果を生成すると、ハッシュテーブルのパフォーマンスが向上することに注意する必要があります。

合理的に実用的である限り、クラス

Object

によって定義された__hashCode（）メソッドは、異なるオブジェクトに対して異なる整数を返します。 （これは、通常、オブジェクトの内部アドレスを整数に変換することによって実施されるが、この実施技術は、Ｊａｖａ（登録商標）プログラミング言語では必要とされない。）。


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（）

が固定値を返すことに違法なものはありません。

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

これに関連して、ハッシュテーブル検索は直線的に実行され、私たちに本当の利点を与えることはありません。


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

そしてhttps://www.eclipse.org/downloads/?[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（）

実装に加えて、例えばhttps://projectlombok.org/features/EqualsAndHashCode[Lombok]を使用して効率的な実装を自動的に生成することもできます。この場合、https://search.maven.org/classic/#search%7Cga%7C1%7Clombok[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
}

同様に、https://commons.apache.org/proper/commons-lang/apidocs/org/apache/commons/lang3/builder/HashCodeBuilder.html[Apache Commons Langの

HashCodeBuilder

クラス]に

hashCode（）

を生成させる場合も同様です。

commons-lang

Mavenの依存関係は、pomファイルに含める必要があります。 

<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（）を実装する際に従うべき普遍的なレシピはありません。

Joshua Bloch’s Effective Java

を読むことを強くお勧めします。効率的なハッシュアルゴリズムを実装するための/joshua-bloch-effect-java-chapter-3[完全なガイドライン]。

ここで注目に値するのは、これらのすべての実装が何らかの形で31番を利用するということです – これは31が良い性質を持っているためです – その乗算は標準的な乗算より速いビットシフトに置き換えることができます。 

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


7. ハッシュ衝突の処理

ハッシュテーブルの本質的な振る舞いは、これらのデータ構造に関連した側面を提起します。たとえ効率的なハッシュアルゴリズムであっても、2つ以上のオブジェクトが等しくなくても同じハッシュコードを持つことがあります。したがって、それらのハッシュコードは、異なるハッシュテーブルキーを持っていても、同じバケットを指します。

このような状況は一般にハッシュ衝突として知られており、https://www.kullabs.com/classes/subjects/units/lessons/notes/note-detail/3888[処理するためのさまざまな方法があります]。長所と短所。 Javaの

HashMap

は、衝突を処理するためにhttps://en.wikipedia.org/wiki/Hash

table#Separate

chaining

with

linked__listsを使用しています。

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

  • 最悪の場合、いくつかのバケットにはリンクリストがバインドされ、リスト内のオブジェクトの検索は線形的に実行されます。

ハッシュ衝突方法論は、__hashCode（）を効率的に実装することがなぜ重要なのかを簡単に説明しています。

Java 8は興味深いhttp://openjdk.java.net/jeps/180[

HashMap

実装の強化]をもたらしました – バケットサイズが特定のしきい値を超えると、リンクリストはツリーマップに置き換えられます。これにより、悲観的な

O（n）

の代わりに

__O（


logn

）__ルックアップを実現できます。


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

標準の

hashCode（）実装の機能をテストするために、

User

オブジェクトを

HashMap__に追加し、リンクを使用する単純なJavaアプリケーションを作成しましょう。/slf4j-with-log4j2-logback[SLF4J]メソッドが呼び出された時間。

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

public class Application {

    public static void main(String[]args) {
        Map<User, User> users = new HashMap<>();
        User user1 = new User(1L, "John", "[email protected]");
        User user2 = new User(2L, "Jennifer", "[email protected]");
        User user3 = new User(3L, "Mary", "[email protected]");

        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（）を効率的に実装するには、いくつかの数学的概念（素数と任意の数）、論理的および基本的な数学的操作を組み合わせる必要があることは明らかです。

にもかかわらず、ハッシュアルゴリズムが異なるオブジェクトに対して異なるハッシュコードを生成し、

equals（）

の実装と一致している限り、

hashCode（）

をこれらのテクニックにまったく頼らずに効果的に実装することは完全に可能です。

いつものように、この記事で示したすべてのコード例はhttps://github.com/eugenp/tutorials/tree/master/core-java-lang-oop[GitHubで利用可能]です。