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

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

関連記事

クッキーとは?JSPでCookieを保存&取得するサンプルプログラムと代表的なメソッド紹介

(1) セッションとは (2) クッキーとは  (2-1) 概要  (2-2) サンプルプログラム   (2-2-1) 概要&画面遷移   (2-2-2) HelloCookie.jsp   (2-2 …

Javaの継承やオーバーライドとは?特徴の解説とサンプルプログラムの紹介

(0)目次&概説 (1) 継承/Inherit  (1-1) 継承とは?  (1-2) 継承の特徴  (1-3) 継承のサンプルコード   (1-3-1) Carクラス   (1-3-2) Truck …

int型のオーバーフロー(桁あふれ)とは?実際の発生パターンと併せてご紹介

  <目次> (1) int型のオーバーフロー(桁あふれ)とは?実際の発生パターンと併せてご紹介  (1-1) int型のオーバーフローとは?  (1-2) int型のオーバーフローが発生す …

Javaで複数の配列を結合する方法について

<目次> (1) Javaで複数の配列を結合する方法について  (1-1) 構文  (1-2) サンプルプログラム (1) Javaで複数の配列を結合する方法について Javaで複数の配列を結合する方 …

Javaでcsvファイルに書き込みを行う方法(サンプルプログラム付き)

<目次> (1) Javaでcsvファイルに書き込みを行う方法  (1-1) 構文  (1-2) サンプルプログラム (1) Javaでcsvファイルに書き込みを行う方法 Javaでcsvファイルを生 …

  • English (United States)
  • 日本語
Top