ハッシュにもとづいた探索 / ハッシュ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<Integer>[] 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<Integer>[] generateHashedTable(Integer[] arr) {
@SuppressWarnings("unchecked")
LinkedList<Integer>[] listTable = (LinkedList<Integer>[]) new LinkedList[TABLE_SIZE];
for (Integer v : arr) {
int h = generateHash(v);
if (listTable[h] == null) {
listTable[h] = new LinkedList<>();
}
LinkedList<Integer> list = listTable[h];
list.add(v);
}
return listTable;
}
private static boolean search(LinkedList<Integer>[] listTable, Integer searchNum) {
int h = generateHash(searchNum);
LinkedList<Integer> 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;
}
}

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

📚 おすすめの書籍

🖥 サーバについて

このブログでは「Cloud Garage」さんのDev Assist Program(開発者向けインスタンス無償提供制度)でお借りしたサーバで技術検証しています。 Dev Assist Programは、開発者や開発コミュニティ、スタートアップ企業の方が1GBメモリのインスタンス3台を1年間無料で借りれる心強い制度です!(有償でも1,480円/月と格安)