オープンアドレスハッシュ法

オープンアドレスハッシュ法について解説します。 ハッシュについての基本的な記述については、こちらに載せてあります。

オープンアドレスハッシュ法は、ハッシュで問題となっていた、 計算したキーのハッシュ値が同じになる要素については、格納できないという問題を、 ハッシュ値が衝突してしまった場合、再び計算してハッシュ値を求めなおすことで問題を解決します。

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

      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番になる要素は、 もうこのハッシュに格納することができないという問題がありました。

オープンアドレス法の場合は、例えばEricをハッシュに追加したいと考えたときに、 先ほど決めたハッシュ関数を使ってハッシュ値を求めると、 Edyの位置と重なってしまいますが、 この時、もう一度ハッシュ値を求めなおします。 このことをリハッシュといい、 リハッシュのためのルールをリハッシュ関数といいます。 例えばここでは、リハッシュ関数を、「ハッシュ関数＋1」とします。 すると、Ericを追加したいと思ったときのプロセスは、次のようになります。

• Ericというキーをハッシュ関数で計算すると、4だった。
• しかし、4にはすでにEdyの要素がある。
• リハッシュ関数によって求めなおした結果、5だった。
• 5には何の要素もまだ書き込まれていないので、5に書き込む。

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

このようにオープンアドレスハッシュ法は、何も格納されていないハッシュ値が計算されるまで、 リハッシュの計算を続けることになります。 もしもEricの電話番号を知りたいと思ったときには、

• Ericというキーをハッシュ関数で計算すると4なので、4番目を見てみる。
• しかし4番目はEdyであったので、リハッシュすると5なので、5番目を見てみる。
• 5番目はEricなので、これで電話番号を知ることができる。

ここで、Edyの要素を削除したとします。

      key      value
    +--------+-------------+
(0) | Albert | 855-69-7889 |
    +--------+-------------+
(1) | empty  | empty       |
    +--------+-------------+
(2) | Ciel   | 854-37-4645 |
    +--------+-------------+
(3) | empty  | empty       |
    +--------+-------------+
(4) | empty  | empty       |
    +--------+-------------+
(5) | Eric   | 786-88-1272 |
    +--------+-------------+
(6) | empty  | empty       |
    +--------+-------------+

そしてEricについて検索したいと思います。 Ericからハッシュ関数でハッシュ値を求めると、4となるのですが、4番目はempty(空)となっています。 これではつまり、Ericのデータがハッシュに入っていないということになってしまいます。

この問題が起きないためにも、オープンアドレスハッシュ法の要素を削除したいときには、 削除したい要素位置に、「削除されました」というフラグを付けます。 すると、こうなります。

      key      value
    +--------+-------------+
(0) | Albert | 855-69-7889 |
    +--------+-------------+
(1) | empty  | empty       |
    +--------+-------------+
(2) | Ciel   | 854-37-4645 |
    +--------+-------------+
(3) | empty  | empty       |
    +--------+-------------+
(4) | delete | delete      |
    +--------+-------------+
(5) | Eric   | 786-88-1272 |
    +--------+-------------+
(6) | empty  | empty       |
    +--------+-------------+

この状態ならば、Ericについて調べることができます。

• Ericについて、ハッシュ関数でハッシュ値を求めると、4であったので、4番目を見てみる。
• しかし4番目はdeleteとなっているので、そこで検索を中断しないことにする。
• リハッシュしてみると、5となったので、5番目を見てみる。
• すると、Ericは5番目で見つかる。

問題点

オープンアドレスハッシュ法の問題点は、リハッシュの計算回数が多くなると、 その計算に処理時間をとられる点と、 チェインハッシュ法とは異なり、ハッシュに格納できる要素の数が有限であるという点です。