ハッシュにもとづいた探索 / ハッシュ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;
    }
}

🐠 (参考) 完全ハッシュ関数

入力に対して、必ず異なるハッシュ値を返すことで直接目的のエントリを探せる関数
完全最小ハッシュ関数とは、完全ハッシュ関数が最小となること
参考リンク
- 完全ハッシュ関数のサンプルソース
- 最小完全ハッシュ関数について

🖥 VULTRおすすめ

「VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります！

酒と泪とRubyとRailsと