ハッシュにもとづいた探索 / ハッシュBased Search | アルゴリズム [AOJ ALDS1_4_A][Java]

今回は、『探索 1 | アルゴリズムとデータ構造
』をハッシュにもとづいた探索(ハッシュBased Search)で解いた場合のサンプルコードです。

🏀 概要

まず、ハッシュ関数にもとづいて、検索対象をハッシュ表に変換する
検索要素をハッシュ値とハッシュ表を突き合わせて検索を行う

🎃 特徴

2分木探索は集合が整列している必要があるが、ハッシュ-Based Searchは整列の必要はない
ハッシュ-Based Searchの設計と、衝突をどう扱うかがこの探索では重要となる
要素が文字列の場合は比較コストが高いので、ハッシュ値のほうがコストが低くすむ
ハッシュ関数が均等に分散できるなら、計算量はO(1)となる
ハッシュ表の生成コストが高いので、コストが生成 < 検索となるような状況で有効そう

🎳 計算時間の傾向サンプル

2の18乗の1次元配列に対して、213,557語の単語のハッシュテーブルを作る
JavaのStringクラスの hashCode を使った場合
- 配列の半分近い区画が空になる
- 空でなで場合は平均して1.46個の要素が入る。最大で7個の文字が入る
より効率的なハッシュテーブルを作るためには複雑なハッシュ関数が必要になる

😎 ハッシュ表での要素探索の成分

ハッシュ表の計算 => ハッシュ表のサイズなので定数
ハッシュ値を添え字として、表の要素を取り出す => 定数
衝突があった時に、指定された値を見つける => 最悪時は線形探査でO(n)。

🗻 Javaコード

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

class Main {
    static final int TABLE_SIZE = 10;

    public static void main(String[] args) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(r.readLine());
        String[] str = r.readLine().split(" ");

        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }

        LinkedList[] listTable = generateHashedTable(arr);

        int q = Integer.parseInt(r.readLine());
        String[] str2 = r.readLine().split(" ");

        Integer[] arr2 = new Integer[q];
        for(int i = 0; i < q; i++) {
            arr2[i] = Integer.parseInt(str2[i]);
        }

        int count = 0;
        for(Integer v: arr2) {
            if (search(listTable, v)) {
                count ++;
            }
        }

        System.out.println(count);
    }

    private static LinkedList[] generateHashedTable(Integer[] arr) {
        @SuppressWarnings("unchecked")
        LinkedList[] listTable = (LinkedList[]) new LinkedList[TABLE_SIZE];

        for (Integer v : arr) {
            int h = generateHash(v);
            if (listTable[h] == null) {
                listTable[h] = new LinkedList<>();
            }

            LinkedList list = listTable[h];
            list.add(v);
        }

        return listTable;
    }

    private static boolean search(LinkedList[] listTable, Integer searchNum) {
        int h = generateHash(searchNum);

        LinkedList list = listTable[h];
        if (list == null) { return false; }

        return list.contains(searchNum);
    }

    private static int generateHash(Integer v) {
        int h = v.hashCode();
        if (h < 0) {  h = 0 - h; }
        return h % TABLE_SIZE;
    }
}