ハッシュ法(チェイン法)

あるデータの集合があって、そのデータに要素を追加したり削除しり検索したい場合があります。

例えば、会員表に新たに会員番号Aの人を追加したり、削除したり、検索する場合です。

このように検索だけではなく、「追加」や「削除」を効率的に行えるのがハッシュ法です。

ハッシュ法なしでデータを追加する

あるデータの集合a[i]を考えます。例えば

1,3,4,5,6,7,9

を考えましょう。このデータに2を追加するとします。すると、

1,2,3,4,5,6,7,9

となります。この際、2をa[1]へ代入するために、3,4,5,6,7,9を右にずらすという作業をしています。具体的には

  1. a[7]=a[6];
  2. a[6]=a[5];
  3. a[2]=a[1];
  4. a[1]=2;

です。計算量でいうと

  1. 二分探索で計算して(オーダーlogn)
  2. ずらす(オーダーn)

となります。よって、オーダーはnですね。

データを削除する場合は逆に左にずらす必要があります。これもオーダーはnとなります。

検索に関しては、二分探索を使うことでlog(n)となります。

まとめ

単純にデータを管理すると

  • 加えたり、削除するのにかかる計算オーダー:n
  • 値を探すのにかかる計算オーダー:log(n)

となります。もう少し、効率的に作業できないものでしょうか?

ハッシュ法

そこで、ハッシュ法の登場です。ハッシュ(hash)とは「細切れの肉料理」という意味です。

このハッシュ法のコンセプトは、

データを細切れに分けて隙間を作ればずらさなくてすむ

ということです。例えば、

1,3,4,5,6,7,9

と詰めるのではなく

1,_,3,_,4,_,5,_,6,_,7,_,9

と隙間を作れば、挿入してもすべてずらさなくても済みますね。

ハッシュ法によるデータ管理

では具体的にハッシュ法を説明します。

1,3,4,6,7

というデータがあり、2を挿入する例で説明します。

まず、ハッシュ法ではハッシュ値によりデータを管理します。

ハッシュ値とは「10で割った際の余りのこと」です。

ここでは説明のため、10にしましたが別に10でなくてもかまいません。

このハッシュ値でデータを表にまとめると以下のようになります。

余り 0 1 2 3 4 5 6 7 8 9
データ *** 1 *** 3 4 *** 6 7 *** ***

この表をハッシュ表といい、ハッシュ表でデータを管理します。

データを加える

では、さっそくデータを加えてみましょう。12を加える事を考えましょう。

12を10で割った余りは2なので、ハッシュ値は2となります。ですからハッシュ表は

余り 0 1 2 3 4 5 6 7 8 9
データ *** 1 12 3 4 *** 6 7 *** ***

となります。データをずらす必要がないので加える際の計算量のオーダーは1です。

次に、2を加えてみましょう。2を10で割ったあまりは2なのでハッシュ値は2です。2をハッシュ表へ加えたいのですが、すでに12が占領しています。このことを衝突と呼びます。

衝突の回避法には主に

  • チェイン法
  • オープンアドレス法

の2つがあります。ここでは、まずチェイン法を説明します。

チェイン法

チェイン法では、衝突が起こった場合は、ハッシュ表へ付け加えるという手段をとります。

よって、ハッシュ表は

余り 0 1 2 3 4 5 6 7 8 9
データ *** 1 12,2 3 4 *** 6 7 *** ***

となります。

チェイン法で、データを消す場合は、ハッシュ表からデータを削除します。

例えば、3を削除する場合は、

  1. 3のハッシュ値を計算する(10で割ると3なのでハッシュ値は3)
  2. ハッシュ表のハッシュ値3の場所をみて、3を削除する

という手順になります。計算のオーダーは「ハッシュ値のデータ数」です。

チェイン法で、データを検索する場合は、ハッシュ表をみて探します。

例えば、7を検索する場合は

  1. 7のハッシュ値を計算する(10で割ると7なのでハッシュ値は7)
  2. ハッシュ表のハッシュ値7の場所をみて7を探す
  3. あればtrue、なけばfalseを返す

となります。これも計算オーダーは「ハッシュ値のデータ数」です。

【チェイン法のまとめ】

チェイン法では衝突が起こったら、表にデータを付け加えます。計算オーダーは以下の通りです。

  • 加える:オーダー=1
  • 消去する:オーダー=ハッシュ値のデータ数
  • 検索する:オーダー=ハッシュ値のデータ数

チェイン法を使わないとオーダーはnなので、かなり計算が効率的になったことがわかります。

計算を早くするには、ハッシュ値のデータ数を少なくすればOKです。つまり、10で割った値ではなく、10000で割ったあまりにすればハッシュ値のデータ数は少なくできるので計算が早くなります(データ数が10000を超える場合はもっと多くする)。

しかし、その分メモリーも使用するので、

割る値=データ数☓2

くらいが適当でしょう。あらかじめデータの大きさがわかっている場合はこのようにしてわる値を決めるといいでしょう。

オープンアドレス法

続いてオープンアドレス法を説明します。

余り 0 1 2 3 4 5 6 7 8 9
データ *** 1 12 3 4 *** 6 7 *** ***

に2を付け加えると、2のハッシュ値は2なので12と衝突が起こります。

オープンアドレス法では、衝突した場合はハッシュ値を増やしていき衝突が起こらないとこまで繰り返すことをします。

この場合、ハッシュ値2,3,4とすべて衝突しますが、5は開いているので5に加えます。すると

余り 0 1 2 3 4 5 6 7 8 9
データ *** 1 12 3 4 2 6 7 *** ***

となります。計算はハッシュ表がデータ数より十分大きければ1となります。

次にデータの検索方法を説明します。ここでは2を検索する方法を説明します。

まず、2のハッシュ値を計算します。すると2になることがわかります。

次に、ハッシュ表を見るとハッシュ値が2の場所に2はありません。

そこで、ハッシュ値を繰上げていき空の部分につくまで2を探します。

するとハッシュ値5に2があるので、2を検索できます。

もし、空の位置に来たら「ない」と判断します。

この計算数はハッシュ表が十分出かければ1となります。

最後にデータ削除の方法を説明します。例として、12を削除する場合を考えます。

手順は以下の通りです。

  1. 12のハッシュ値を計算してを検索する
  2. 12を削除する
  3. 削除した場所に印を付ける

よって、ハッシュ表は以下のとおりになります。

余り 0 1 2 3 4 5 6 7 8 9
データ *** 1 3 4 2 6 7 *** ***

ここでのポイントは印(☆)をつけるということです。もし印がないと2を検索すると、ハッシュ値2にないので、2はないことになります。

一方、印があれば、ハッシュ値2に印があるので衝突を繰り返しハッシュ値5に2を発見出来ます。

データの消去にかかる計算オーダーは1となります。

【オープンアドレス法のまとめ】

オープンアドレス法では、衝突が起こったらハッシュ表に開いている場所を探していれます。

計算オーダーはチェイン法と同じです。

最後に

ハッシュ法は、データ管理を効率的に行うことができるということを理解していただけたでしょうか。

計算オーダーが1なのでとても速く検索、追加、削除を行うことができます。

データ管理ソフトを作る際はハッシュ法を検討してみてください。

著者:安井 真人(やすい まさと)