Rainbow Engine

IT技術を分かりやすく簡潔にまとめることによる学習の効率化、また日常の気付きを記録に残すことを目指します。

Java

オープンアドレス法のアルゴリズムについて図を使ってご紹介

投稿日:2021年2月10日 更新日:

<目次>

(1) オープンアドレス法のアルゴリズムについて図を使ってご紹介
 (1-1) オープンアドレス法とは?
 (1-2) オープンアドレス法のアルゴリズム
 (1-3) オープンアドレス法の利用シーン
 (1-4) サンプルプログラム

(1) オープンアドレス法のアルゴリズムについて図を使ってご紹介

(1-1) オープンアドレス法とは?

「オープンアドレス法」は、ハッシュを使った探索において使用するアルゴリズムで、異なるキー同士から計算した格納先アドレスが重複(衝突と呼ぶ)した場合の対処法として使います。

通常、ハッシュを使った探索では「キー」となる値に対応したハッシュ値を求め、その値から求まるアドレスにデータを格納していきます。ハッシュによる探索の基本については、別途下記の記事でご紹介しているので、ハッシュの探索とは?から知りたい方はまずは、下記をご覧ください。
 
①ハッシュの基礎について
②ハッシュの計算式の意味について
 
(図111)ハッシュによる探索では「キー」から計算したアドレスへ読み書きをしていく

しかしながら、ハッシュから計算したアドレスは必ず一意になるとは限らず、場合によっては異なるキーでも同じインデックス(格納アドレス)になる事があります。
 
(図112)rumbleとfairlyが共にアドレス「369」で衝突が起きる

目次にもどる

(1-2) オープンアドレス法のアルゴリズム

オープンアドレス法は計算されたアドレスが「衝突」した際に「別のアドレスを探す」動きをする事で、衝突を防ぐアルゴリズムです。

その「別のアドレス」の決め方はいくつか方法がありますが、最もシンプルなのは、計算されたインデックスの値に「1を加算する」方法です。下図がオープンアドレス法のアルゴリズムを描いたフローチャートです。
(図121)

(フローチャートの説明)

ステップ 説明
①インデックスの計算 まずは普通に格納先アドレスを計算します。
②計算したアドレスが衝突しているか? 計算されたアドレスが衝突しているか?をチェックします。具体的には下記の条件を満たす場合を「衝突」とみなしています。

①要素に値がある(使用されている)
②要素に値がある場合、キーの値は異なるか?

この2つの条件をANDで満たす(①と②両方に該当する)場合にオープンアドレス法を実施します(空き領域探しの旅が始まる)

③格納アドレス探索完了フラグ=falseか? 「格納アドレス探索完了フラグ」というのは、言い換えると「空き領域探しが完了したか?」のステータスを管理するフラグです。これがfalseの間、探し続けるwhile文になっています。
④インデックスを+1 アドレス探しの旅の最初のステップとして、インデックスに+1を加えます。つまり、シンプルに1つ次のアドレスが使えるか?をチェックしています。

例えばfairlyが「369」で既存のrumbleと衝突したので、fairlyの方は譲歩して+1した「370」のアドレスを見に行く感じです。

⑤再計算したアドレスが衝突していないか? +1したアドレスでも「衝突」しているかをチェックします。オープンアドレス法により値を格納していくと、連続して衝突する事が起こり得ますので、再チェックをしています。
⑥格納アドレス探索完了フラグ=trueに更新 再計算したアドレスが衝突していなければ、晴れて「空き領域探しの旅」は終わり、ようやくフラグをtrueに更新して、旅の終わりを宣言します。
⑦再計算したアドレスが次の条件を満たすか?
 ・要素に値が無い
最後に、探し当てたアドレスに更新を掛けていきますが、この時もパターンが2つあります。
①新規(元はnull)
②既存(既に同じキーの古い値が入っている)

そのため「null」かどうかの判定を挟んで、結果に応じて更新の仕方を少し変えます。

⑧-1 新規の場合は、元が空なのでnewで新しいインスタンスを代入します。
(例)
wordmix[index] = new Word(w,c);
⑧-2 既存の場合は、同じキーの古い値が既に存在しているので、値の部分のみを最新化します。
そのためのメソッドとしてputメソッドを実装して使っています。
(例)
wordmix[index].setValue(c);

目次にもどる

(1-3) オープンアドレス法の利用シーン

この「衝突」の対処法にはいくつか方法があり、「オープンアドレス法」以外では「チェイン法」などもあります。

「オープンアドレス法」は以下の条件を満たす場合に向いている方法と言われています。
・要素の数が予測できる
・余裕を持った要素数の確保ができる
 

目次にもどる

(1-4) サンプルプログラム

⇒別記事にて執筆予定

目次にもどる

Adsense審査用広告コード


Adsense審査用広告コード


-Java

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

Javaでハッシュ値を計算する方法について

<目次> (1) Javaでハッシュ値を計算する方法について  (1-1) ハッシュを使った探索の概要  (1-2) ハッシュからアドレスを計算する方法  (1-3) サンプルプログラム (1) Ja …

オープンアドレス法をJavaで実装したプログラムのサンプルをご紹介

<目次> (1) オープンアドレス法をJavaで実装したプログラムのサンプルをご紹介  (1-1) オープンアドレス法とは  (1-2) Javaのサンプルプログラムの全体像  (1-3) Javaの …

Javaのswitch-case文の構文や使い方を紹介+UFOキャッチャーの座標移動プログラムも紹介

<目次> (1) Javaのswitch-case文の構文や使い方を紹介  (1-1) switch-caseの構文  (1-2) else-if文との比較 (2) サンプルプログラムの紹介  (2- …

JavaScriptでAttributeの値を削除(Remove)する方法

<目次> (1) JavaScriptでAttributeの値を削除(Remove)する方法  (1-1) 構文  (1-2) サンプルプログラム   (1-2-1) サンプルプログラムの概要   ( …

Javaの選択ソートとは?アルゴリズムの流れ+サンプルプログラムをご紹介

<目次> (1) バイナリ―サーチとは?Javaのサンプルプログラムを用いて解説  (1-1) バイナリ―サーチのアルゴリズム  (1-2) バイナリ―サーチの性能(処理回数)  (1-3) バイナリ …

  • English (United States)
  • 日本語
Top