ハッシュ探索(1)

ホームアルゴリズム入門講座 > ハッシュ探索(1)

ハッシュ探索(1)

ハッシュ探索の基本データ

ハッシュ探索アルゴリズム

ハッシュ探索は入門講座内でわずかに触れました。基本的な仕組みは簡単です。

一方向性のハッシュ関数 Hash() を用意する
データを用意する際、

index = Hash(value)
配列[index] = value

とする

これにより、index と value が一意的に関連づけられるので、
value を格納する index は常に
index = Hash(value)
であると分かる

ハッシュ関数には剰余がよく用いられます。自分が使うデータの数や特性に応じてハッシュ関数を自作することも簡単にできます。

ハッシュ探索の実装

using System; using System.Text; namespace NewWorld { class MainClass { const int N = 100; public static void Main(string[] args) { string[] source = {"仲間由紀恵","YUI","松嶋菜々子","長澤まさみ","蒼井優","宮崎あおい","持田香織"}; string[] database = DataSet(source); for(int i=0;i

ハッシュ探索アルゴリズムの全ては「ハッシュ関数」によって決定します。ハッシュ関数の作り方は様々ですし、C#のようにクラスの中にハッシュ機能を備えたものがたくさんある場合はそれらを使っても構いません。

今回は文字列のデータベースを操作します。そのため、「文字中のすべての文字の文字コードを加算し、定数 N で割った余り」をハッシュにしています。

ハッシュ探索の問題点

ハッシュ単数の基本データで「実装:単純明快なものから複雑なものまで」と書きました。上のような場合が単純明快な場合ですが、複雑になる場合もあります。

それは「ハッシュが衝突」した場合です。

たとえば、同じハッシュが生成されたにもかかわらず、それに気づかなければ、知らない間にデータが消失している、という現象が起きてしまいます。

この問題を解決するには3つの手段が考えられます。

  1. データテーブルの量を増やすこと
  2. 衝突しにくいハッシュ関数を使うこと
  3. 衝突した場合でも大丈夫なように、データテーブルを複層的にすること

上のハッシュ関数でも、定数 N の値を増やすことで簡単に衝突を防ぐことができます。しかし、その分データテーブルを保存するメモリもたくさん消費してしまいます。

衝突しにくいハッシュ関数は自分で考えることは困難です。すでに多くの研究成果があるので、それを学ぶ方がよいでしょう。割る値に素数を用いるなど、数学的に解析されています。

最後の解決策は、衝突した場合を想定します。2次元配列を用いたり、ジャグ配列を用いたりします。

なお、C#にはハッシュテーブルを利用するための「連想配列」が用意されています。.NET Framework 2.0 から加わったDictionaryクラスを参考にしてください。