0Pricing
Java Academy · レッスン

hashCode の実装

正しいハッシュ関数を記述します。

「hashCode の実装」はCoddyKit上の無料Java Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはJava Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Java Academyコースには全4レッスンが含まれています。

優れた hashCode の目標

優れた hashCode() には、次の性質があります：

  • 等しいオブジェクトに対して同じ値を返す（契約）。
  • 等しくないオブジェクトを多くの異なる値に分散させる。
  • 計算コストが低い。

常に同じ値を返す粗末な hashCode でも契約は満たしますが、マップが遅い連結リストになってしまいます。

public class Main {
    public static void main(String[] args) {
        // Legal but terrible: every object collides
        System.out.println("constant hashCode is legal but kills performance");
    }
}

一般的なケースでは Objects.hash

最も簡単で正しい方法は Objects.hash(field1, field2, ...) です。

null も処理でき、標準的なアルゴリズムでフィールドを組み合わせます。equals で比較する同じフィールドを使ってください。

import java.util.Objects;

public class Main {
    static class User {
        final String name; final int age;
        User(String name, int age) { this.name = name; this.age = age; }
        @Override public int hashCode() { return Objects.hash(name, age); }
    }
    public static void main(String[] args) {
        User a = new User("Ada", 36);
        User b = new User("Ada", 36);
        System.out.println(a.hashCode() == b.hashCode());
    }
}

定番の31倍乗算

ハッシュを手作業で実装する場合、累積結果に31を掛けて、各フィールドのハッシュを加えるのが標準的なパターンです。

31は奇数の素数です。また、31 * x は (x << 5) - x と同じなので、JVM はこれを最適化できます。

public class Main {
    static class User {
        final String name; final int age;
        User(String name, int age) { this.name = name; this.age = age; }
        @Override public int hashCode() {
            int result = 17;
            result = 31 * result + (name == null ? 0 : name.hashCode());
            result = 31 * result + age;
            return result;
        }
    }
    public static void main(String[] args) {
        System.out.println(new User("Ada", 36).hashCode());
    }
}

プリミティブ型のハッシュ化

各プリミティブ型には、推奨されるハッシュ化方法があります：

  • int：値そのものを使います。
  • long：(int)(value ^ (value >>> 32)) を使います。
  • boolean：1または0を使います。
  • double：Double.hashCode(value) を使います。
public class Main {
    public static void main(String[] args) {
        long id = 4_000_000_000L;
        int longHash = (int) (id ^ (id >>> 32));
        System.out.println("long hash: " + longHash);
        System.out.println("double hash: " + Double.hashCode(3.14));
        System.out.println("bool hash: " + Boolean.hashCode(true));
    }
}

配列のハッシュ化

配列に対して直接 hashCode() を呼び出してはいけません。内容ではなく、同一性にもとづいてハッシュ化されるためです。

1次元配列には Arrays.hashCode(arr) を、ネストした配列には Arrays.deepHashCode(arr) を使ってください。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = {1, 2, 3};
        System.out.println("identity equal: " + (a.hashCode() == b.hashCode()));
        System.out.println("content equal: " + (Arrays.hashCode(a) == Arrays.hashCode(b)));
    }
}

equals と hashCode の整合性を保つ

hashCode() で使うフィールドは、equals() で使うフィールドの部分集合でなければなりません（理想的にはまったく同じフィールドにします）。

equals が hashCode より多くのフィールドを比較する場合、等しいオブジェクトは同じハッシュを持つので問題ありません。ただし、hashCode が equals で無視するフィールドを使うと、契約に違反します。

import java.util.Objects;

public class Main {
    static class Coord {
        final int x, y;
        Coord(int x, int y) { this.x = x; this.y = y; }
        @Override public boolean equals(Object o) {
            return o instanceof Coord c && c.x == x && c.y == y;
        }
        @Override public int hashCode() { return Objects.hash(x, y); }
    }
    public static void main(String[] args) {
        Coord a = new Coord(3, 4), b = new Coord(3, 4);
        System.out.println(a.equals(b) && a.hashCode() == b.hashCode());
    }
}

ハッシュのキャッシュ

ハッシュ化にコストがかかる不変オブジェクトでは、結果をフィールドにキャッシュできます。

String は内部でまさにこの処理を行っています。キャッシュされた値が古くならないよう、オブジェクトが本当に不変である場合にだけ使ってください。

import java.util.Objects;

public class Main {
    static final class Key {
        final String a, b;
        private int hash; // 0 until computed
        Key(String a, String b) { this.a = a; this.b = b; }
        @Override public int hashCode() {
            int h = hash;
            if (h == 0) { h = Objects.hash(a, b); hash = h; }
            return h;
        }
    }
    public static void main(String[] args) {
        Key k = new Key("x", "y");
        System.out.println(k.hashCode());
        System.out.println(k.hashCode());
    }
}

分布が重要です

適切に分散された hashCode は、キーをバケット全体に均等に広げます。ここでは、複数のオブジェクトについて異なるハッシュコードの数を数えます。

異なる値が多いほど衝突が減り、マップは高速になります。

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Main {
    record Pair(int a, int b) {}
    public static void main(String[] args) {
        Set<Integer> hashes = new HashSet<>();
        for (int i = 0; i < 100; i++) {
            hashes.add(Objects.hash(i, i * 7));
        }
        System.out.println("distinct hashes: " + hashes.size());
    }
}

分布が悪い例

乗算せずにフィールドを合計すると衝突が発生します。(1,2) と (2,1) はどちらも3にハッシュされます。

31倍の乗算を使うと順序が結果に影響するため、この対称性が崩れます。

public class Main {
    static int badHash(int a, int b) { return a + b; }
    static int goodHash(int a, int b) { return 31 * a + b; }
    public static void main(String[] args) {
        System.out.println("bad (1,2): " + badHash(1, 2) + ", (2,1): " + badHash(2, 1));
        System.out.println("good (1,2): " + goodHash(1, 2) + ", (2,1): " + goodHash(2, 1));
    }
}

値型にはレコードを優先する

純粋なデータ保持用クラスには、record が正しく、分布のよい hashCode を自動生成します。

独自の意味付けが必要な場合や、レコードを使えない場合にだけ、hashCode を手作業で実装してください。

public class Main {
    record Money(long cents, String currency) {}
    public static void main(String[] args) {
        Money a = new Money(1099, "USD");
        Money b = new Money(1099, "USD");
        System.out.println(a.equals(b));
        System.out.println(a.hashCode() == b.hashCode());
    }
}

すべてを組み合わせる

完全な値クラスとは、不変なフィールド、同じフィールドにもとづく equals と hashCode、そして適切な toString を備えたクラスです。

import java.util.Objects;

public class Main {
    static final class Version {
        final int major, minor, patch;
        Version(int major, int minor, int patch) {
            this.major = major; this.minor = minor; this.patch = patch;
        }
        @Override public boolean equals(Object o) {
            return o instanceof Version v && v.major == major && v.minor == minor && v.patch == patch;
        }
        @Override public int hashCode() { return Objects.hash(major, minor, patch); }
        @Override public String toString() { return major + "." + minor + "." + patch; }
    }
    public static void main(String[] args) {
        Version v = new Version(2, 1, 0);
        System.out.println(v + " hash=" + v.hashCode());
    }
}

理解度チェック

hashCode のスキルを確認してください。

まとめ

hashCode を正しく実装する方法を学びました：

  • 一般的なケースでは Objects.hash(...) を使います。
  • 手作業でハッシュ化する場合は31倍乗算のパターンを使います。
  • 配列にはデフォルトの方法ではなく、Arrays.hashCode を使います。
  • hashCode で使うフィールドを equals と一致させ、レコードを優先してください。

次は、Java 8以降で衝突の多いバケットがどのようにツリー化されるかを見ていきます。

import java.util.Objects;

public class Main {
    public static void main(String[] args) {
        System.out.println("hashCode recap done: " + Objects.hash("done"));
    }
}

よくある質問

「hashCode の実装」レッスンは無料ですか？

はい。「hashCode の実装」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Java Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Java Academyコースには全4レッスンが含まれています。

「hashCode の実装」で何を学びますか？

正しいハッシュ関数を記述します。 ブラウザで直接実行するハンズオンコードでJava Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Java Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのJava Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「hashCode の実装」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このJava Academyレッスンでコードを書いて実行できますか？

はい。すべてのJava Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. HashMap の仕組み
  2. equals/hashCode の契約
  3. hashCode の実装
  4. ツリー化とパフォーマンス
← Java Academyに戻る