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

・今回は、整数のキーだけの集合
・キーと値の組を扱う場合も同様の方法で実装可能

・ハッシュ関数
・配列

データの追加
・データをキーとしたハッシュ値を計算
・ハッシュ値を添字として配列にデータを格納

データの検索
・データをキーとしたハッシュ値を計算
・ハッシュ値を添字とした位置にデータが保存されているかを確認

・整数n
・n個の文字列 x_1, x_2, …, x_n

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 = 188;
        System.out.println(table.get(H(y)));

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