チェインハッシュ法

チェインハッシュ法について解説します。 ハッシュについての基本的な事柄については、こちらに載せてあります。

チェインハッシュ法は、ハッシュで問題となっていた、 計算したキーのハッシュ値が同じになる要素については、格納できないという問題を、 同じハッシュ値のものを格納するとき、チェインのようにつないで格納する ことで解決することから、チェインという名前になっています。

まず例として、ハッシュで格納したハッシュの状態を見てください。

      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       |
    +--------+-------------+

ハッシュでは、ハッシュ値が0番になる要素と、ハッシュ値が2番になる要素、 それにハッシュ値が4番になる要素は、 もうこのハッシュに格納することができないという問題がありました。 しかし、チェインハッシュ法は、ハッシュ値が同じになってしまった場合、 同じ場所にさらに格納するという方法で、この問題を解決しています。

      key      value
    +--------+-------------+
(0) | Albert | 855-69-7889 |
    +--------+-------------+
(1) | empty  | empty       |
    +--------+-------------+
(2) | Ciel   | 854-37-4645 |
    +--------+-------------+
(3) | empty  | empty       |
    +--------+-------------+-------+-------------+-------+-------------+
(4) | Edy    | 450-69-8887 | Eric  | 786-88-1272 | E.T   | 454-12-3691 |
    +--------+-------------+-------+-------------+-------+-------------+
(5) | empty  | empty       |
    +--------+-------------+
(6) | empty  | empty       |
    +--------+-------------+

Edyと同じハッシュ値になるEricは、Edyの後ろに要素を追加し、さらにE.Tは、Ericの後ろに要素を追加しています。 こうすることで、ハッシュ値が重複するキーについても、いくらでも格納することができるようになります。

問題点

しかし、チェインハッシュ法には、問題が1つあります。 例えば、Cielの電話番号を調べたいと思った場合、 'C'はさきほど決めたハッシュ関数に照らしてハッシュ値を求めると、 2番目に格納されていることがすぐにわかりますが、 E.Tの電話番号を調べたいと思ったときに、ハッシュ値が4番目であることはすぐにわかりますが、 4番目にはEdyとEricとE.Tの3人分の要素が格納されています。 この中からE.Tを見つけるには、順番に「Edy、これ違う、Eric、これ違う、E.T、これだ！」 というように検索するしかありません。 これにより、ハッシュ値が重複すればするほど、検索するのに時間が掛かることになります。

この問題を解決しようとしたのが、オープンアドレスハッシュ法です。