＜目次＞
(１) オープンアドレス法をJavaで実装したプログラムのサンプルをご紹介
(１-１) オープンアドレス法とは
(１-２) Javaのサンプルプログラムの全体像
(１-３) Javaのサンプルプログラム
(１-４) 参考（オープンアドレス法を適用する前のプログラム）
(１) オープンアドレス法をJavaで実装したプログラムのサンプルをご紹介
当記事では「オープンアドレス法」をJavaで実装した例をご紹介していきます。
(１-１) オープンアドレス法とは
配列等に値を格納する際に「ハッシュ」を元に計算したアドレスに値を格納する方法がありますが、その計算されたアドレスの値が重複（衝突）した時の対処方法が「オープンアドレス法」です。
その前提知識である「ハッシュ」の計算方法や計算したアドレスへの値の格納方法等を知りたい方は、別記事にて概要やアルゴリズムを解説していますので、併せてご覧頂けたらより理解が深まると思います（特に①を読むとプログラムの理解がしやすいです）。
(１-２) Javaのサンプルプログラムの全体像
まずはプログラムの内容を素早く把握するために、どのような構造になっているか？をざっくりご紹介します。
（プログラムの構造）
class CustomHashMap4 {
//【メンバ変数】
public Word[] wordmix;
int mapsize;
//【コンストラクタ】CustomHashMapのコンストラクタ
public CustomHashMap4(int mapsize) {
this.wordmix = new Word[mapsize];
this.mapsize = mapsize;
}
//【値の更新】Wordクラスのインスタンスを更新
public void put(String w, int c) {
//（インデックス計算＋オープンアドレス法によるアドレス探索）
//putの処理（アドレスの要素を更新）
}
//【値の取得】キーからインデックスを計算して値を取得
public int get(String w) {
//（インデックス計算＋オープンアドレス法によるアドレス探索）
//getの処理（アドレスの要素を取得）
}
//【クラス】Wordクラス
class Word {
private String word; //Key
private int wordcode; //Value
public Word(String w, int c) {word = w; wordcode = c;}
public String getKey() {return word;}
public int getValue() {return wordcode;}
public void setValue(int c) {wordcode = c; }
}
}
（構造の説明）
| main文 | main文で実際にWordクラスのインスタンスを配列に追加（put）したり、値を取得（get）したりします。
この例で注目すべきが、単語「rumble」と「fairly」は共にハッシュが「369」となり「衝突」が起きています。同様に「severe」と「stuff」も共にハッシュが「372」で衝突が起きています。 |
| 【Wordクラス】 | 今回の配列の各要素に格納されるクラスです。 単語（word）と単語コード（wordcode）を保持しています。 今回の場合、main文にて配列の容量を1000確保しているので、配列にはWordクラスが最大1000個格納できます。 CustomHashMap4 cm = new CustomHashMap4(1000); |
| 【メンバ変数】 （wordmix、mapsize） |
Wordクラス型の配列wordmixと、そのサイズを格納するint型のmapsizeを定義しています。 |
| 【コンストラクタ】 （CustomHashMap4） |
int型のmapsizeを受け取り、配列wordmixを初期化します。 |
| 【値の取得】 （getメソッド） |
配列の要素を取得するためのgetメソッドを実装しています。
引数としてキー（w）と値（c）を受取り、値（c）のhashCodeから、格納先のインデックス（index）を計算して、もしそこが「空きアドレス」の場合は0を返し、「空きアドレスでない」場合は「既存の要素」が既にあるとみなし、格納されている値（wordcode）を取得します。 【処理フロー概要】 |
| 【値の更新】 （putメソッド） |
配列に要素を追加するためのputメソッドを実装しています。
引数としてキー（w）と値（c）を受取り、値（c）のhashCodeから、格納先のインデックス（index）を計算して、もしそこが「空きアドレス」の場合は新規のWordクラスのインスタンスを追加し、「空きアドレスでない」場合は「既存の要素」が既にあるとみなし、値（wordcode）の更新のみしています（同じキーの値だけを更新する）。 【処理フロー概要】 |
(１-３) Javaのサンプルプログラム
main文で実際にWordクラス型の配列wordmixに対してインスタンスを配列に追加（put）したり、値を取得（get）したりします。
この例で注目すべきが、単語「rumble」と「fairly」は共にハッシュが「369」となり「衝突」が起きています。同様に「severe」と「stuff」も共にハッシュが「372」で衝突が起きています。
しかし、オープンアドレス法が適用され、それぞれ＋１したアドレスに無事に格納されています。
（サンプルプログラム）
public class IT0XXX_OpenAddress_After {
public static void main(String args[]) {
CustomHashMap4 cm = new CustomHashMap4(1000);
cm.put("rumble", 15); //index=369に格納される
cm.put("fairly", 20); //index=369でrumbleと衝突⇒370に格納される
cm.put("severe", 10); //index=372
cm.put("stuff", 35); //index=372でsevereと衝突⇒373に格納される
System.out.println("Point of team rumble : "+cm.get("rumble"));
System.out.println("Point of team fairly : "+cm.get("fairly"));
System.out.println("Point of team severe : "+cm.get("severe"));
System.out.println("Point of team stuff : "+cm.get("stuff"));
}
}
class CustomHashMap4 {
//【メンバ変数】
public Word[] wordmix;
int mapsize;
//【コンストラクタ】CustomHashMapのコンストラクタ
public CustomHashMap4(int mapsize) {
this.wordmix = new Word[mapsize];
this.mapsize = mapsize;
}
//【値の更新】Wordクラスのインスタンスを更新
public void put(String w, int c) {
//(1) インデックスの計算
int index = (w.hashCode() & 0x7fffffff) % mapsize;
//#################### オープンアドレス方START ####################
//(2) オープンアドレス法
// (2-1) 計算したアドレスが「衝突」しているか？をチェック
// ①要素に値がある（使用されている）
// ②要素に値がある場合、キーの値は異なるか？
// →①と②両方に該当する場合にオープンアドレス法を実施
if(wordmix[index]!=null && !w.equals(wordmix[index].getKey())) {
//格納アドレス探索完了フラグ
boolean flg_canupdate = false;
//(2-1-1)格納できるアドレスが見つかるまで繰り返し処理
// （格納アドレス探索完了フラグ=trueになるまで）
// ⇒空きアドレスが見つかる or 既存の値と一致する＝既出の場合にtrue
while(!flg_canupdate) {
//(2-1-1-1)インデックスをインクリメント
index++;
// (2-1-1-2)再計算したアドレスが衝突していないか？をチェック
// ①要素に値がない（未使用）or ②キー値が同じか？
if(wordmix[index]==null) {
//(2-1-1-2-1)要素に値がない場合
// →未使用の領域である（空きアドレス）
// →flag=trueに更新
flg_canupdate = true;
}
else if(wordmix[index]!=null && w.equals(wordmix[index].getKey())){
//(2-1-1-2-2)要素に値がありキー値が同じ場合
// →同じキー＝衝突してないので、これ以上のindex加算は不要
// →flag=trueに更新
flg_canupdate = true;
}
//(2-1-1-2-3)空いてなくて既存キーしていない
// →別のキーが既にいる（衝突）ので、次のアドレスに移動
// →何もせず（index++に戻り次のアドレスをチェック）
}
}
//#################### オープンアドレス方END ####################
//(3)値の追加処理
//(3-1)インデックスの要素がnullの場合
// →未使用の要素のため、新規Wordクラスのインスタンスを代入
if(wordmix[index]==null) {
wordmix[index] = new Word(w,c);
}
//(3-2)インデックスの要素がnullでない場合 →既存更新
// →使用中の既存要素のため、既存のキーの値のみをsetValueで更新
else {
wordmix[index].setValue(c);
}
}
//【値の取得】キーからインデックスを計算して値を取得
public int get(String w) {
//(1) インデックスの計算
int index = (w.hashCode() & 0x7fffffff) % mapsize;
//#################### オープンアドレス方START ####################
//(2) オープンアドレス法
// (2-1) 計算したアドレスが「衝突」しているか？をチェック
// ①要素に値がある（使用されている）
// ②要素に値がある場合、キーの値は異なるか？
// →①と②両方に該当する場合にオープンアドレス法を実施
if(wordmix[index]!=null && !w.equals(wordmix[index].getKey())) {
//格納アドレス探索完了フラグ
boolean flg_canupdate = false;
//(2-1-1)格納できるアドレスが見つかるまで繰り返し処理
// （格納アドレス探索完了フラグ=trueになるまで）
// ⇒空きアドレスが見つかる or 既存の値と一致する＝既出の場合にtrue
while(!flg_canupdate) {
// (2-1-1-1)インデックスを＋１
index++;
// (2-1-1-2)再計算したアドレスが衝突していないか？をチェック
if(wordmix[index]==null) {
//(2-1-1-2-1)要素に値がない場合
// →未使用の領域である（空きアドレス）
// →flag=trueに更新
flg_canupdate = true;
}
// (2-1-1-2-2)空いてなくて既存キーの場合
// →同じキーなので、これ以上のindex加算は不要（衝突ではないので、このアドレスでOK）
// →flag=trueに更新＋値の返却処理で現在の値(Value)を返却
else if(wordmix[index]!=null && w.equals(wordmix[index].getKey())){
//(2-1-1-2-2)要素に値がありキー値が同じ場合
// →同じキー＝衝突してないので、これ以上のindex加算は不要
// →flag=trueに更新
flg_canupdate = true;
}
// (2-1-1-2-3)空いてなくて既存キーしていない
// →別のキーが既にいる（衝突）ので、次のアドレスに移動
// →何もせず（index++に戻り次のアドレスをチェック）
}
}
//#################### オープンアドレス方END ####################
//(3)値の追加処理
//(3-1)インデックスの要素がnullの場合
// →未使用の要素のため、例外回避のため0を返却
if(wordmix[index]==null) {
System.out.println("### [String]="+w+" [index]="+index);
return 0;
}
//(3-2)インデックスの要素がnullでない場合
// →使用中の既存要素のため、現在の値(Value)を返却
else {
System.out.println("@@@ [String]="+w+" [index]="+index);
return wordmix[index].getValue();
}
}
//【クラス】Wordクラス
class Word {
private String word; //Key
private int wordcode; //Value
public Word(String w, int c) {word = w; wordcode = c;}
public String getKey() {return word;}
public int getValue() {return wordcode;}
public void setValue(int c) {wordcode = c; }
}
}
（図１３２）実行結果
(１-４) 参考（オープンアドレス法を適用する前のプログラム）
参考ですが、オープンアドレス法を適用する前のプログラムもご紹介します。
（※上記のプログラムで「## オープンアドレス方START ##」～「## オープンアドレス方END ##」の部分を削除しただけです）
こちらはオープンアドレス法を適用していないので、先ほどの例の「rumble」と「fairly」が衝突している様子などを見る事ができます。
public class IT0XXX_OpenAddress_Before {
public static void main(String args[]) {
CustomHashMap3 cm = new CustomHashMap3(1000);
cm.put("rumble", 15); //index=369
cm.put("fairly", 20); //index=369
cm.put("severe", 10); //index=372
cm.put("stuff", 35); //index=372
System.out.println("Point of team rumble : "+cm.get("rumble"));
System.out.println("Point of team fairly : "+cm.get("fairly"));
System.out.println("Point of team severe : "+cm.get("severe"));
System.out.println("Point of team stuff : "+cm.get("stuff"));
}
}
class CustomHashMap3 {
//【メンバ変数】
public Word[] wordmix;
int mapsize;
//【コンストラクタ】CustomHashMapのコンストラクタ
public CustomHashMap3(int mapsize) {
this.wordmix = new Word[mapsize];
this.mapsize = mapsize;
}
//【値の更新】Wordクラスのインスタンスを更新
public void put(String w, int c) {
//単語のインデックスを計算
int index = (w.hashCode() & 0x7fffffff) % mapsize;
//インデックスの要素がnullの場合 →新規追加
if(wordmix[index]==null) {
wordmix[index] = new Word(w,c);
}
//インデックスの要素がnullでない場合 →既存更新
else {
wordmix[index].setValue(c);
}
}
//【値の取得】キーからインデックスを計算して値を取得
public int get(String w) {
int index = (w.hashCode() & 0x7fffffff) % mapsize;
//インデックスの要素がnullの場合 →未使用の要素のため０を返却
if(wordmix[index]==null) {
System.out.println("### [String]="+w+" [index]="+index);
return 0;
}
//インデックスの要素がnullでない場合 →使用中の要素のためカウンタの値を返却
else {
System.out.println("@@@ [String]="+w+" [index]="+index);
return wordmix[index].getValue();
}
}
//【クラス】Wordクラス
class Word {
private String word; //Key
private int wordcode; //Value
public Word(String w, int c) {word = w; wordcode = c;}
public String getKey() {return word;}
public int getValue() {return wordcode;}
public void setValue(int c) {wordcode = c; }
}
}
（図１３１）
＞目次にもどる
