kakts-log

programming について調べたことを整理していきます

Hash-Based サーチアルゴリズム まとめ

今回、多くの要素を持ち、必ずしもソートされていないコレクションに対して特定の値を探す際に効果的なHash-Basedサーチアルゴリズムについてまとめます。
日本語ではハッシュ法による探索アルゴリズムと呼ばれることもあります。

Hash-Basedサーチアルゴリズム

一般的によく知られたアプローチの一つは、hash関数をつかって、検索対象のコレクションの要素内の特徴を使ってハッシュテーブルのインデックスに変換することです。
ハッシュ法によるサーチは、シーケンシャルサーチやバイナリサーチよりも、average-caseでのパフォーマンスがより良いものとなっています。

Hash-Basedサーチにおいて、n個の要素を持つ集合Cは最初にHと呼ばれるハッシュテーブルと、配列構造を持つb個のビンにロードされる。
この前処理はO(n)のパフォーマンスを持つが、 しかし後の検索においてパフォーマンスが向上する。 ハッシュ関数のコンセプトはこのパフォーマンス向上を可能にする。

ハッシュ関数は各要素Ciを整数値hiに変換する決定関数です。
まず、hiを 0<= hi < bと仮定する。 要素をハッシュテーブルに読み込む時、 Ciは H[hi]のビンに格納される。 すべての要素が格納された後、アイテムtを探索する場合は H[hash(t)]のビンの中から要素を探索する

ハッシュ関数は、もし要素CiとCjが同値の場合 hash(Ci) == hash(Cj)となることを保証します。
これは、集合Cの中の要素のうち、ハッシュ値が同じ場合がありうることを意味します。
これはハッシュ衝突として知られ、ハッシュテーブルはこの状況に対応する方法が要求されます。

最もよく知られた解決策として、各ハッシュインデックスにlinked listを保持し、すべてのハッシュ衝突したデータをハッシュテーブルに格納する手法があります。
各ハッシュインデックスが保持するlinked listは線形的にサーチされる必要がありますが、各linked listの要素数は非常に少ないため、探索時間は短くすみます。

下記の疑似コードはハッシュインデックスが衝突した際の linked-listの振る舞いを書いている

  • Uを取りうるハッシュ値の集合とする。 各要素e は Cに属していて、 ハッシュ値 h は Uに属する
  • ハッシュテーブルHはb個のビンを持っている。各ビンは集合Cの中からn個の要素を持つ。
  • ハッシュ関数hashは、集合Cのすべての要素eに対して 0<= h <bとなるハッシュ値hを出力する
Best, Average O(1)
Worst O(n)

// ハッシュテーブルをロードする
loadTable (size, C)
    H = new array of given size
    foreach e in C do
        h = hash(e)
            if H[h] is empty then
            H[h] = new Linked List
            add e to H[h]
    return A
end

// サーチ
search (H, t)
    h = hash(t)
    list = H[h]
    if list is empty then
        return false
    if list contains t then
        return true
    return false
end

Hash-Basedサーチの2つの問題

Hash-Basedサーチを実装するにあたって、主要な問題は2つあります。
- ハッシュ関数のデザイン
- ハッシュ値衝突のハンドリング

綿密に設計されていないハッシュ関数は、ハッシュキーをハッシュテーブルに分配するロジックが良くないため、ハッシュテーブルへの値の格納において、偏りがでてしまいます。
そして、特定のビンに多くの値が格納されるので、ハッシュ衝突が起きる割合が多くなります。
これはhash-basedサーチにおけるパフォーマンスの低下を招きます

input/output

イナリサーチと異なり、Hash-Based searchにおいては、サーチ対象のコレクションCは必ずしもソートされる必要がない。 もしCがソートされていた場合、Cの各要素をハッシュテーブルHに格納するハッシュ関数は、H内部で元のソート情報を保持することがないので意味がない

Hash-Based-Searchにおける入力は、既に作成済みのハッシュテーブルHと、サーチ対象の要素tです。 アルゴリズムは、要素tが、ハッシュ関数を適用した出力値 h = hash(t)として、H[h]のビンに含まれている場合trueを返す。

もし213,557個の英単語の配列があるとして、ある単語を探す場合 バイナリサーチの場合は最大で18回(log(213557) = 17.70)の探索が必要です。 Hash-Based Searchの場合比較回数は、コレクションのサイズというよりも、ハッシュテーブルの各ビンが保持するlinked-listの長さに依存します。

ハッシュ関数について

hash関数を定義するに当たって、ゴールは多くの異なる値を正の数に変換し、各要素を必ずしもユニークにする必要はない ハッシュ化は何十年にも渡って研究されてきているが、その多くの手法はサーチ以外の目的に対しても使うことができる。

例えば、特別なハッシュ関数は暗号化に使われたりする。 サーチにおいては、ハッシュ関数はハッシュテーブルへの値のばらつきが均一であることと、計算時間が短いものが良いです。 → ハッシュ関数の実装については後日まとめます。。。