ハッシュ

ハッシュの意義

配列は、複数の固定的なデータを表すことに優れていますが、 その並び順がソートされていない場合に、検索に時間が掛かります。 また、ソートされた配列を用いて検索時間を短縮したとしても、 その配列に、新たに要素を追加/挿入しようとした場合に、毎回配列の再定義を行う必要があります。 しかし上記のプロセスを何度も繰り返していたのでは、プログラムのパフォーマンスが低下してしまいます。 そこでこの問題を解決あるいは軽減するために考え出されたアルゴリズムが ハッシュです。

ハッシュの基本アルゴリズム

ハッシュには、チェイン法とオープンアドレス法の2つが存在しますが、 どちらにも依存しない部分の説明を記述します。

ハッシュは、まず最初に領域を確保します。 今回は25個(アルファベットの字数だけ)確保していますが、ここではとりあえず0番目から6番目までを見ていきます。

      key      value
    +--------+-------+
(0) | empty  | empty |
    +--------+-------+
(1) | empty  | empty |
    +--------+-------+
(2) | empty  | empty |
    +--------+-------+
(3) | empty  | empty |
    +--------+-------+
(4) | empty  | empty |
    +--------+-------+
(5) | empty  | empty |
    +--------+-------+
(6) | empty  | empty |
    +--------+-------+

ハッシュは、値を格納する際に、値をサーチするためのキーというものを同時に格納します。 例えば、以下のキーと値のペアを定義したとします。

• name="Albert", tel="855-69-7889"
• name="Ciel", tel="854-37-4645"
• name="Edy", tel="450-69-8887"

そして格納する際に、キーの値をもとに、どこに格納するかを決定します。 例えば、今回のルールとして、先頭文字のアルファベットが'A'ならば0番に、'B'ならば1番に、'C'ならば2番に、 といったぐあいに格納することにします。 このような、格納場所を決定するルールのことをハッシュ関数といい、 ハッシュ関数によって決定された、0番目とか1番目といった、 場所を示す数値をハッシュ値といいます。 ハッシュ関数は一般的に、ハッシュの実装者が、そのキーに適切なようにルールを決定します。 今回のハッシュ関数に基づいて値を格納すると、以下のようになります。 nameをキー、telを値として格納しています。

      key      value
    +--------+-------------+
(0) | Albert | 855-69-7889 |
    +--------+-------------+
(1) | empty  | empty       |
    +--------+-------------+
(2) | Ciel   | 854-37-4645 |
    +--------+-------------+
(3) | empty  | empty       |
    +--------+-------------+
(4) | Edy    | 450-69-8887 |
    +--------+-------------+
(5) | empty  | empty       |
    +--------+-------------+
(6) | empty  | empty       |
    +--------+-------------+

この状態で、例えばEdyの電話番号を検索したいとします。 Eはハッシュ関数でハッシュ値に変換すると、4となり、4番目の値を参照すると、Edyの電話番号がすぐにわかります。 配列の検索のように、0番目から順に、keyがEdyかどうかを比較していく必要はありません。

問題点

上記のハッシュの説明は、そのままではプログラミングで即使用するわけにはいきません。 例えば、

name="Eric", tel="255-696-3641"

というキーと値を先ほどのハッシュに格納しようとすると、Edyと衝突してしまいます。 どちらもハッシュ関数で計算すると、4番目となってしまうからです。 つまり、ハッシュ関数で計算した結果が同じ結果になるキーについては、格納できないという欠陥があるのです。 この欠陥を補った、実用可能なハッシュ法が、 チェインハッシュ法とオープンアドレスハッシュ法です。