Rainbow Planet

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

Java

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

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

<目次>

(1) オープンアドレス法をJavaで実装したプログラムのサンプルをご紹介
 (1-1) オープンアドレス法とは
 (1-2) Javaのサンプルプログラムの全体像
 (1-3) Javaのサンプルプログラム
 (1-4) 参考(オープンアドレス法を適用する前のプログラム)

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

当記事では「オープンアドレス法」をJavaで実装した例をご紹介していきます。

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

配列等に値を格納する際に「ハッシュ」を元に計算したアドレスに値を格納する方法がありますが、その計算されたアドレスの値が重複(衝突)した時の対処方法が「オープンアドレス法」です。
 
その前提知識である「ハッシュ」の計算方法や計算したアドレスへの値の格納方法等を知りたい方は、別記事にて概要やアルゴリズムを解説していますので、併せてご覧頂けたらより理解が深まると思います(特に①を読むとプログラムの理解がしやすいです)。
 
 

目次にもどる

(1-2) 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)を取得します。

【処理フロー概要】
(1) インデックスの計算
(2)オープンアドレス法の処理
(3)値の追加処理
(3-1)インデックスの要素がnullの場合
 →未使用の要素のため、例外回避のため0を返却
(3-2)インデックスの要素がnullでない場合
 →使用中の既存要素のため、現在の値(Value)を返却

【値の更新】
(putメソッド)
配列に要素を追加するためのputメソッドを実装しています。

引数としてキー(w)と値(c)を受取り、値(c)のhashCodeから、格納先のインデックス(index)を計算して、もしそこが「空きアドレス」の場合は新規のWordクラスのインスタンスを追加し、「空きアドレスでない」場合は「既存の要素」が既にあるとみなし、値(wordcode)の更新のみしています(同じキーの値だけを更新する)。

【処理フロー概要】
(1) インデックスの計算
(2)オープンアドレス法の処理
(3)値の追加処理
(3-1)インデックスの要素がnullの場合
  →未使用の要素のため、新規Wordクラスのインスタンスを代入
(3-2)インデックスの要素がnullでない場合 →既存更新
  →使用中の既存要素のため、既存のキーの値のみをsetValueで更新

目次にもどる

(1-3) Javaのサンプルプログラム

main文で実際にWordクラス型の配列wordmixに対してインスタンスを配列に追加(put)したり、値を取得(get)したりします。

この例で注目すべきが、単語「rumble」と「fairly」は共にハッシュが「369」となり「衝突」が起きています。同様に「severe」と「stuff」も共にハッシュが「372」で衝突が起きています。

しかし、オープンアドレス法が適用され、それぞれ+1したアドレスに無事に格納されています。

(サンプルプログラム)

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)インデックスを+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; }
    }
}

(図132)実行結果

目次にもどる

(1-4) 参考(オープンアドレス法を適用する前のプログラム)

参考ですが、オープンアドレス法を適用する前のプログラムもご紹介します。
(※上記のプログラムで「## オープンアドレス方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の場合 →未使用の要素のため0を返却
        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; }
    }
}

(図131)

目次にもどる

Adsense審査用広告コード


Adsense審査用広告コード


-Java

執筆者:


comment

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

関連記事

GitHubのWebAPIをコールしてユーザー情報を取得するサンプルプログラムの解説+エラー対応も2例紹介

(0)目次&概説 (1) 目的  (1-1) 記事の目的 (2) APIの概要  (2-1) APIとは?  (2-2) Web APIとは?  (2-3) Web APIの様々な呼び方   (2-3 …

木構造の探索における計算量の違いや木構造の種類について(B木/二分木/2-3探索木)

<目次> (1) 木構造の探索における計算量の違いや木構造の種類について(B木/二分木/2-3探索木)  (1-1) 木構造について  (1-2) 「B木」構造  (1-3) 「二分木」構造  (1- …

サーバサイドJava(JSP&サーブレット)のFORM認証を用いたログイン画面の開発

(0)目次&概説 (1) サーバー側JavaのFORM認証  (1-1) 認証の種類  (1-2) FORM認証の特徴  (1-3) FORM認証の実装概要 (2) FORM認証の実装手順  (2-1 …

JVMの基本アーキテクチャと各サブシステム等の概要説明について

(0)目次&概説 (1) 記事の目的 (2) Javaのアーキテクチャ概要・概観 (3) JVMのアーキテクチャ概要  (3-1) JVMの概観  (3-2) JVMの主要サブシステム1:Class …

JFreeChartを使ってJavaで様々なグラフを簡単に描画する方法

(0)目次&概説 (1) 記事の目的  (1-1) 目的 (2) JFreeChartの概要  (2-1) JFreeChartとは?  (2-2) JFreeChartのアーキテクチャについて (3 …

  • English (United States)
  • 日本語
Top