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


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


🍄 概要

hash-based-search-algorithm

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

🚕 特徴

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

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

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

hash-based-search-java-hashcode-sample

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

  • ハッシュ表の計算 => ハッシュ表のサイズなので定数
  • ハッシュ値を添え字として、表の要素を取り出す => 定数
  • 衝突があった時に、指定された値を見つける => 最悪時は線形探査で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のヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります!

📚 おすすめの書籍