ハッシュ法とは
ハッシュ(hash)法とは、大量のデータを高速に検索・格納するための手法です。
データはハッシュテーブルという表に格納されます。流れとしては
- キーをハッシュ関数にかけてハッシュ値を取得
- そのハッシュ値を配列のインデックスとしてデータを格納
- 検索時は同じキーをハッシュ関数にかけて対応するデータにアクセス
これらを順番に学籍番号を例にして説明します。ほとんどの大学では生徒のデータを学籍番号をキー(一意の番号)として管理していると思います。
下の表のような生徒のデータを管理したいと考えています。
学籍番号 |
氏名 | 学部 |
|---|---|---|
| 52244245 | 田中太郎 | 経済学部 |
| 52322344 | 渡辺花子 | 商学部 |
| 53322233 | 鈴木一郎 | 工学部 |
まずキーの学籍番号が52244245をハッシュ関数にかけることで、ハッシュ値を得ます。( hash(52244245)=3 )
そのハッシュ値(3)を配列のインデックスとして氏名、学部などのデータを格納します。検索時も同様に学籍番号をハッシュ関数にかけることでハッシュ値をインデックスとして配列にアクセスすることでデータを見ることができます。
ハッシュ関数の最も単純な例として恒等写像があります。(hash(k) = k)
学籍番号が52244245の場合、配列のインデックスが52244245の場所にデータを格納します。ただ、この場合さまざまな問題が発生します。
①メモリ効率の問題
学籍番号は通常、年度や学部、学科ごとに規則性があり、連番になっていません。キャンパスで学籍番号"1"の生徒を見たことがありますか？ないですよね。つまり、あなたの学籍番号が52244245であったとしても、52244245名の生徒は存在しないということになります。0~52244245のうち使われていない数字はかなりあるのです。ですので、学籍番号を直接配列のインデックスにすれば、配列の多くの部分が未使用になり、メモリの無駄使いになってしまいます。
②安全性とプライバシーの問題
学籍番号を直接インデックスにすると、データ構造が予測されやすくなり、不正アクセスのリスクが高まる可能性があります。
例えば、攻撃者が学籍番号の規則を知っている場合、無作為に試すことで他人のデータを取得できるかもしれません。
③データ管理の柔軟性
大学の運営方針が変わり、学籍番号の形式が変更される可能性があります。
例えば、桁数が増えたり、年度ごとにフォーマットが変わることがあります。
直接インデックス化していると、新しいフォーマットに対応するために大規模な変更が必要になります。
これらの理由から、キー値を圧縮して格納する必要があることがわかります。
それを実現するハッシュ関数の例を二つ挙げます
①キーが整数xの場合
hash(x) = x\ mod\ m
この場合、mはハッシュテーブルのサイズとなります。
②キーが文字列の場合
hash(s) = \sum_{i=0}^n c^i ord(s[i])\ mod\ m
s: 文字列（例："abc"）
k: 文字列の長さ
c: 適切な係数（通常、素数が選ばれる）
ord(): 文字のASCIIコードを取得する関数
m: ハッシュテーブルのサイズ
これらのハッシュ関数を用いた場合、異なるキーに同じハッシュ値が割り当てられる衝突が起こる可能性があります。
衝突が起こった際の解決策は主にチェイン法と開番地法があります。
チェイン法
チェイン法は同じハッシュ値を持つ複数の要素を線形リストを用いて接続する方法です。ハッシュテーブルの各インデックスはデータを保持するのではなく、線形リストの先頭ポインタを格納しています。新しいデータが衝突した場合はそのインデックスのリストの先頭に新しいノードを格納します。検索時はそのリストを順に走査して目的のキーを見つけます。
開番地法（Open Addressing）
開番地法（Open Addressing）とは、ハッシュテーブルにデータを直接格納し、衝突が発生した場合は、別の空き場所を探しデータを格納する方法です。
この手法では、追加のデータ構造（リンクリストなど）を使用せずに、ハッシュテーブルの中でデータの再配置を行うのが特徴です。
別の空き場所を見つける手法として線形走査（Linear Probing)があります。線形走査とは衝突が発生した場合に、次のインデックス(+1)を順に調べ、空きスロットを探す手法です。
ただし、線形走査の問題点としてクラスタリング問題があります。クラスタリングとは連続した空きスロットを埋めてしまうことで、次に挿入する場合に多くのスロットを調べる必要が出てきてしまう。その結果、検索、挿入効率が下がることになります。
このクラスタリングを避ける方法として、インデックスを(h + i^2)にして走査する二次走査法（Quadratic Probing）、別のハッシュ関数を用いて(h + i*g(x))とする二重ハッシュ法（Double Hashing）があります。これらを用いることで、データの分布をより均一にすることができます。