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) Javaでの正規表現の使い方  (1-3) サンプルプログラム (1) Javaで正規表現の使い方をご …

JavaのBigDecimalの使い方+初期化・四則演算・余り・累乗等の主要用途も紹介

<目的> (1) JavaのBigDecimalの使い方+初期化や四則演算・桁数設定等の主要用途も紹介  (1-1) 宣言の方法  (1-2) 代表的な用途(足し算・引き算・掛け算・割り算)  (1- …

Failed to execute goal org.apache.mavenエラーの原因と対処(Spring BootのMavenプロジェクトで発生)

  <目次> (1) Failed to execute goal org.apache.mavenエラーの原因と対処(Spring BootのMavenプロジェクトで発生)  (1-1) …

TwitterのAPIライブラリ(Twitter4j)で「いいね数」や「リツイート数」を取得する方法

<目次> (1) TwitterのAPIライブラリ(Twitter4j)で「いいね数」や「リツイート数」を取得する方法  (1-1) 構文  (1-2) サンプルプログラム (1) TwitterのA …

バイナリ―サーチとは?Javaのサンプルプログラムを用いて解説

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

  • English (United States)
  • 日本語
Top