新・アルゴリズムとデータ構造入門 Java編12: ハッシュ関数とハッシュテーブル

・値を格納するときにハッシュ値が衝突
・データを上書きしてしまう

衝突しないためには
・ハッシュ値が衝突しないようにハッシュ関数を設計したい
・必ずハッシュ値の衝突を回避できるハッシュ関数を作れるとは限らない

対策
・衝突しても、データを削除しないように工夫する

オープンアドレス法
・衝突が解消されるまで、ハッシュ値を再計算

チェイン法
・配列の要素をデータそのものではなくデータのリストにする
・衝突した複数のデータを同じ場所に格納

import java.util.*;

public class Main {

    // ハッシュ関数
    static int H(int x) {
        return x % 10;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // ハッシュテーブルの初期化
        var table = new ArrayList<Integer>();
        for(int i = 0; i < 10; i++){
            table.add(-1);
        }

        int n = sc.nextInt();

        for(int i = 0; i < n; i++){
            int x = sc.nextInt();

            int hash = H(x);

            // データの追加
            table.set(hash, x);
        }

        // データの検索
        int y = 777;
        System.out.println(table.get(H(y)));

        int z = 17;
        System.out.println(table.get(H(z)));
    }
}