毎月アルゴリズム – 第7回 –

はじめに

こんにちは。よっしーです。
毎月アルゴリズムを考えていくブログの第 7 回目です。
前回から少し期間が空いてしまい申し訳ありません。(毎月アルゴリズムではなくなってしまう!笑)
前回に引き続き今回も探索に関するアルゴリズムを考えています。
今回も探索のアルゴリズムを 1 つ紹介して、探索のアルゴリズムを終えようかと思います。
良ければ御覧ください。

アルゴリズムを考えてみる

本日は以下の探索に関してアルゴリズムを考えていきます。
今回は探索アルゴリズムの分類としては 1 つなんですが、衝突が起こった場合に破綻しないためのロジックが 2 種類ほど方法論としてあるのでそちらを紹介します。

  • ハッシュ探索
    • チェイン法(分離連鎖法)
    • オープンアドレス法

ハッシュ探索

概要

以前紹介したデータ構造のハッシュテーブルの考え方を用いて、収納されたデータを取り出す方法です。
詳しい原理は 第2回で解説しているので省略しますが、データをハッシュ関数を用いてハッシュテーブル格納し、同じハッシュ関数をかけて探索値をハッシュテーブルから高速で探し出す探索方法です。

オーダー

ハッシュ値を用いてデータの挿入、探索を行うため、 O(1) です。

ハッシュ値の衝突

ハッシュ関数は一定のアルゴリズムで同じ Key から必ず同じ数値が返ってくるメソッドということを以前お伝えしたと思います。
ただし、別の Key でも同じ数値が返ってくることがあります。
これをハッシュ値の衝突と言います。
とても単純なロジックで考えてみましょう。

できるだけ衝突を起こしにくい関数を作るために日夜アルゴリズムは考えられていますが、衝突は起こってしまうものとして、衝突が起こったときの処理を考えておく必要があります。
その代表的な方法は以下です。

  •  チェイン法(分離連鎖法)
  • オープンアドレス法

チェイン法(分離連鎖法)

チェイン法は、同じハッシュ値のデータを連結リストでつなげていくことによって衝突を起こしても同じハッシュ値に複数データを格納することによって回避する方法です。
線形のリストに格納する性質上、線形リストが長くなると検索効率が落ちるので、できるだけハッシュ値が衝突を起こさないように、ハッシュ関数を考える必要があります。

コード

チェイン法を用いたハッシュ検索を行える構造を C#で書いてみました。
構造的な部分を重視したので、ハッシュ関数の作成、より効率のいい設計を目指すことは省きました。

オープンアドレス法

オープンアドレス法は格納したい値からハッシュ値を計算し、そこからアドレスを計算して配列に格納するというところまではチェイン法と同じです。
アドレスが衝突していたとき、アドレスを再計算して別のアドレスに格納する処理を行います。
上記で別のアドレスにも値が格納されていた場合、別のアドレスを再計算し、そのアドレスに格納するという処理を繰り返し行います。

処理

最も単純に処理を書くとすると以下になります

  1. 格納するデータよりインデックスの計算(アドレス作成)
  2. 計算したアドレスが衝突しているか
    1. Yes の場合:アドレスを再計算 2 に戻る
    2. No の場合:値を格納する-> end

アドレスの計算ロジックは工夫しなければ、埋まっているアドレスが多くなってきた場合に性能が劣化してしまいます。
今回はハッシュの再計算のロジックは簡単なものとして、線形走査法、二重ハッシュ法というものがあるのでそれも紹介しておきます。

ハッシュの再計算

あるハッシュ関数 h を定義したとして、引数 x を取ったとき、それにより得られるハッシュ値を h(x)と定義します。
h(x)はあるハッシュ値で数値を取るものとします。

線形走査法

あるハッシュ関数 h において、線形走査法におけるハッシュ値は以下で記されます。
ハッシュの配列の大きさを M とし、k 回目の再ハッシュ関数は以下で定義される。

(h(x) + k) \% M

一見難しく記載していますが、前述のコードで利用しているハッシュ関数は以下です。

h(x) \% M

これに 1 ずつ加えていって、M を超えるようなら 0 に戻してくださいねと言ってるのが線形操作法です。
とても噛み砕いて言うとアドレスが埋まっていたら一つ隣のアドレスを使ってくださいということになります。

二重ハッシュ法

あるハッシュ関数 h, g を用いて、二重ハッシュ法におけるハッシュ値は以下で記されます。
ハッシュの配列の大きさを M とし、k 回目の再ハッシュ関数は以下で定義される。

(h(x) + k \* g(x)) \% M

線形走査法に形が似ています。
g(x) = 1 のとき、線形操作法になります。
ここで、g は簡単な関数にしないと再計算に時間がかかってしまいます。
一般的には以下のようにするのが望ましいとされています。

g(x) = q - h(x) \% q

q は M より小さい値で、この値 g(x)は M と互いに素(※)になっていないとすべてを走査することはできません。
そのため、M は素数を取ることが多くなります。

※ 互いに素とは
2 つの整数が 1 以外の公約数を持たないこと
15 と 27 は素因数分解すると 15 = 3 /times 5, 27 = 3 ^ 3 と公約数を 1 しか持たないため互いに素となる。
15 と 24 は素因数分解すると 15 = 3 /times 5, 24 = 2 ^ 3 /times 3 と 3 を公約数に持つので互いに素とならない。

コード

今回は単純化するため線形走査法を用いて、オープンアドレス法を実装したいと思います。
いつもどおり、C#で書いてみました。

おわりに

今回は 1 つの検索方法なのに内容にボリュームがとてもあったと思います。
でも直感的に理解できるものだとは思いますのでぜひアルゴリズムの参考にしていただけたらと思います!

■ 序章
第0回 (初歩的な数学のアルゴリズムを考えてみよう)

■ ソートのアルゴリズム
第1回
第2回
第3回
第4回
第5回

■ 検索のアルゴリズム
第6回

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

アーカイブ

カテゴリー

PAGE TOP