ハッシュ法とは

ハッシュ法とは、表を用いた探索法のひとつです。
表に格納されたデータは、レコード構造 になっています。
レコード構造は、以下の表のように レコード と フィールド からなっています。

1行目のレコードの各フィールドには、[名前]、[クラス名]、[所属部活名]のデータが格納されています。

ハッシュ法では、ある特定のフィールドのデータを対象にして探索を行います。
この特定のフィールドのデータを key といいます。

この key を、ハッシュ関数 という演算を用いて データの格納場所を示す値 に変換する方法が、ハッシュ法です。

ハッシュ関数とは

ハッシュ関数には、一般的に以下のような関数が使われます。

h(key) = key\quad mod\quad M

• key 探索対象のフィールドの値
• M 表の大きさ
• h(key) key を M で割った余り（格納場所を示す値 = ハッシュ値）

上記の関数のとおり、表の大きさ と、 目的のデータの値 から、余りを求めるだけで格納場所を見つけられるので、計算量はO(1)（オーダー１）であり、非常に高速な探索法と言えます。

またハッシュ関数は、データの探索だけではなくデータの登録にも使用されます。

データの登録と探索

項目名と内容が結びついているようなデータ（シンボルテーブルなど）の探索に向いています。

衝突と解決策

ハッシュ関数で探索・登録を行なっていると、複数のデータで同じ格納場所を示す値が出てくることがあります。

このような場合の解決策として、チェイン法 と オープンアドレス法 があります。

チェイン法

チェイン法は、同じ格納場所を示すデータを連結リストでつなげていきます。

チェイン法を利用した場合の計算量は、以下のようになります。

O(1) + O\bigl( \frac{n}{M}\bigr) =  \left\{
\begin{array}{ll}
O(1) & (n \ll M) \\
O(n) & (n \gg M)
\end{array}
\right.\\

この方法を用いる際に気をつけるべきことは、「格納するデータ数（ n ）よりも、余裕のあるハッシュ表の大きさ( M )にする必要がある」ということです。

例えば、M = 5 の大きさの表に対して 100個 のデータを格納する場合で考えてみましょう。（ 上記の計算量でいうと、n >> M の場合　）
100個のデータを 5 しか格納場所がない表に納めるとなると、いくつかの格納場所に非常に長い連結リストを作ることになってしまいます。

すると、高速なハッシュ法で格納場所を特定したのちに、連結リストを線形探索で探索しなればいけなくなります。つまり計算量が大きくなってしまうということです。

オープンアドレス法

オープンアドレス法は、格納場所が被ってしまった際に、空いている格納場所が見つかるまで、再ハッシュを行う方法です。

\begin{align}
h_0 &= key\quad mod\quad M\\
\\
h_1 &= (h_0 + 1)\quad mod\quad M\\
h_2 &= (h_1 + 1)\quad mod\quad M\\
h_3 &= (h_2 + 1)\quad mod\quad M\\
\end{align}

しかしオープンアドレス法には問題点があります。
再ハッシュを繰り返していると、連続した格納場所に塊(cluster)が生じやすくなり、塊が増えると再ハッシュする回数も増えてしまうという点です。

塊の発生を避ける方法としては、適当な整数定数（ x ）おきに探索していくという方法が考えられます。

\begin{align}
h_0 &= key\quad mod\quad M\\
\\
h_1 &= (h_0 + x)\quad mod\quad M\\
h_2 &= (h_0 + x)\quad mod\quad M\\
h_3 &= (h_0 + x)\quad mod\quad M\\
\end{align}

しかしこれでも塊の発生は防げません。

以下のように、1回目のハッシュ関数で求められた格納場所を元にするのではなく、ランダムな格納場所を選択して再ハッシュを行う方法もあります。

\begin{align}
h_0 &= key\quad mod\quad M\\
\\
h_1 &= (h_0 + n)\quad mod\quad M\\
h_2 &= (h_0 + m)\quad mod\quad M\\
h_3 &= (h_0 + o)\quad mod\quad M\\
\end{align}