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

＜目次＞

配列等に値を格納する際に「ハッシュ」を元に計算したアドレスに値を格納する方法がありますが、その計算されたアドレスの値が重複（衝突）した時の対処方法が「オープンアドレス法」です。

 

その前提知識である「ハッシュ」の計算方法や計算したアドレスへの値の格納方法等を知りたい方は、別記事にて概要やアルゴリズムを解説していますので、併せてご覧頂けたらより理解が深まると思います（特に①を読むとプログラムの理解がしやすいです）。

 

⇒【参考①】オープンアドレス法のアルゴリズム解説

⇒【参考②】ハッシュを使ったアドレスの計算

⇒【参考③】ハッシュはなぜ31で割る？

 

（プログラムの構造）

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; }
        }
}

（サンプルプログラム）

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; }
    }
}

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; }
    }
}