＜目次＞
(１) オープンアドレス法のアルゴリズムについて図を使ってご紹介
(１-１) オープンアドレス法とは？
(１-２) オープンアドレス法のアルゴリズム
(１-３) オープンアドレス法の利用シーン
(１-４) サンプルプログラム
(１) オープンアドレス法のアルゴリズムについて図を使ってご紹介
(１-１) オープンアドレス法とは？
「オープンアドレス法」は、ハッシュを使った探索において使用するアルゴリズムで、異なるキー同士から計算した格納先アドレスが重複（衝突と呼ぶ）した場合の対処法として使います。
通常、ハッシュを使った探索では「キー」となる値に対応したハッシュ値を求め、その値から求まるアドレスにデータを格納していきます。ハッシュによる探索の基本については、別途下記の記事でご紹介しているので、ハッシュの探索とは？から知りたい方はまずは、下記をご覧ください。
①ハッシュの基礎について
②ハッシュの計算式の意味について
（図１１１）ハッシュによる探索では「キー」から計算したアドレスへ読み書きをしていく
しかしながら、ハッシュから計算したアドレスは必ず一意になるとは限らず、場合によっては異なるキーでも同じインデックス（格納アドレス）になる事があります。
（図１１２）rumbleとfairlyが共にアドレス「369」で衝突が起きる
(１-２) オープンアドレス法のアルゴリズム
オープンアドレス法は計算されたアドレスが「衝突」した際に「別のアドレスを探す」動きをする事で、衝突を防ぐアルゴリズムです。
その「別のアドレス」の決め方はいくつか方法がありますが、最もシンプルなのは、計算されたインデックスの値に「1を加算する」方法です。下図がオープンアドレス法のアルゴリズムを描いたフローチャートです。
（図１２１）
（フローチャートの説明）
| ステップ | 説明 |
| ①インデックスの計算 | まずは普通に格納先アドレスを計算します。 |
| ②計算したアドレスが衝突しているか？ | 計算されたアドレスが衝突しているか？をチェックします。具体的には下記の条件を満たす場合を「衝突」とみなしています。
①要素に値がある（使用されている） この２つの条件をANDで満たす（①と②両方に該当する）場合にオープンアドレス法を実施します（空き領域探しの旅が始まる） |
| ③格納アドレス探索完了フラグ＝falseか？ | 「格納アドレス探索完了フラグ」というのは、言い換えると「空き領域探しが完了したか？」のステータスを管理するフラグです。これがfalseの間、探し続けるwhile文になっています。 |
| ④インデックスを＋１ | アドレス探しの旅の最初のステップとして、インデックスに＋１を加えます。つまり、シンプルに１つ次のアドレスが使えるか？をチェックしています。
例えばfairlyが「369」で既存のrumbleと衝突したので、fairlyの方は譲歩して＋１した「370」のアドレスを見に行く感じです。 |
| ⑤再計算したアドレスが衝突していないか？ | ＋１したアドレスでも「衝突」しているかをチェックします。オープンアドレス法により値を格納していくと、連続して衝突する事が起こり得ますので、再チェックをしています。 |
| ⑥格納アドレス探索完了フラグ＝trueに更新 | 再計算したアドレスが衝突していなければ、晴れて「空き領域探しの旅」は終わり、ようやくフラグをtrueに更新して、旅の終わりを宣言します。 |
| ⑦再計算したアドレスが次の条件を満たすか？ ・要素に値が無い |
最後に、探し当てたアドレスに更新を掛けていきますが、この時もパターンが２つあります。 ①新規（元はnull） ②既存（既に同じキーの古い値が入っている） そのため「null」かどうかの判定を挟んで、結果に応じて更新の仕方を少し変えます。 |
| ⑧-1 | 新規の場合は、元が空なのでnewで新しいインスタンスを代入します。 （例） wordmix[index] = new Word(w,c); |
| ⑧-2 | 既存の場合は、同じキーの古い値が既に存在しているので、値の部分のみを最新化します。 そのためのメソッドとしてputメソッドを実装して使っています。 （例） wordmix[index].setValue(c); |
(１-３) オープンアドレス法の利用シーン
この「衝突」の対処法にはいくつか方法があり、「オープンアドレス法」以外では「チェイン法」などもあります。
「オープンアドレス法」は以下の条件を満たす場合に向いている方法と言われています。
・要素の数が予測できる
・余裕を持った要素数の確保ができる
(１-４) サンプルプログラム
⇒別記事にて執筆予定
