Rainbow Planet

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

Java

Javaでハッシュ値を計算する方法について

投稿日:2021年1月29日 更新日:

<目次>

(1) Javaでハッシュ値を計算する方法について
 (1-1) ハッシュを使った探索の概要
 (1-2) ハッシュからアドレスを計算する方法
 (1-3) サンプルプログラム

(1) Javaでハッシュ値を計算する方法について

(1-1) ハッシュを使った探索の概要

ハッシュを使った探索では「キー」となる値に対応したハッシュ値を求め、その値から求まるアドレス(下図ではindexという)にデータを格納していきます。

(図111)イメージ図
ハッシュを求め、そこから格納アドレスを計算する

ピンポイントの値に直接アクセスするので、データを探す時間を短縮できて高速ですが、その分余分なメモリを消費します。
JavaのStringクラスにはハッシュを計算する便利なhashCodeメソッドが用意されているので、そちらを次の節でご紹介します。
 

(1-2) ハッシュからアドレスを計算する方法

(構文)

int index = (hash & 0x7fffffff) % [定数];

各値の内容は以下の表の通りです。

(表)構文の各値の内容

項目 説明
index ハッシュから計算したアドレスです。配列のindex番目の要素に、値を格納していきます。
hash ハッシュの値です。これはStringクラスの「hashCode」メソッドにより計算します。

(例)
String color = “Red”;
int hash = color.hashCode();

& 0x7fffffff ハッシュの計算で目にする「& 0x7fffffff」は、インデックス(アドレス)にマイナスの数が入るのを防ぐための「ビットマスク」です。

後半の「0x7fffffff」のうち「0x」は「16進数である」事を表しており、「7fffffff」は16進数で表現された「32ビットの整数」です。これを「2進数」に変換すると、0の後に1が31個続き「01111111111111111111111111111111」となります。このとき一番左端の「0」のビットが「符号ビット」で、符号の情報を表しています(プラスは0、マイナスは1)。

(図)16進数⇒2進数への変換

前半の「&」を前に付けて「& 0x7fffffff」とする事で、先頭のビットのみ0をセットする、つまり符号を「必ずプラスにする」処理になります。

% [定数] [定数]で割った余りを、最終的な格納アドレスにしています。そのため、配列は[定数]の数だけ要素を確保しておけば、OutOfRangeを防ぐ事ができます。

(図121)ハッシュの取得

StringクラスのhashCode()メソッドを使うと、String型の変数のハッシュを簡単に取得する事ができます。例では「The」のハッシュ値は「84049」になっています。

目次にもどる

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

実際にハッシュから計算したアドレスの要素に、値を格納するプログラムをご紹介します。


(概要)
Fruitクラスというフルーツの「名前」と「個数」を格納するクラスと、そのFruit型の配列「fruitmix」があります。そしてfruitmixにFruit型のインスタンスの要素を追加&取得する際には「put」と「get」メソッドを使います。このputとgetではそれぞれ格納・取得のアドレスをハッシュから計算しています。

(図131)

(サンプルプログラム)

public class IT0XXX_HashCodeTest3 {
    public static void main(String args[]) {
        CustomHashMap5 cm = new CustomHashMap5(1000);
        cm.put("Apple", 15);
        cm.put("Banana", 20);
        cm.put("Melon", 10);
        System.out.println("Quantity of Apple : "+cm.get("Apple"));
        System.out.println("Quantity of Banana : "+cm.get("Banana"));
        System.out.println("Quantity of Melon : "+cm.get("Melon"));
    }
}
class CustomHashMap5 {
    //【メンバ変数】
    public Fruit[] fruitsmix;
    int mapsize;
    //【コンストラクタ】CustomHashMapのコンストラクタ
    public CustomHashMap5(int mapsize) {
        this.fruitsmix = new Fruit[mapsize];
        this.mapsize = mapsize;
    }
    //【値の更新】Fruitクラスのインスタンスを更新
    public void put(String w, int c) {
        //単語のインデックスを計算
        int index = (w.hashCode() & 0x7fffffff) % mapsize;
        //インデックスの要素がnullの場合 →新規追加
        if(fruitsmix[index]==null) {
            fruitsmix[index] = new Fruit(w,c);
        }
        //インデックスの要素がnullでない場合 →既存更新
        else {
            fruitsmix[index].setValue(c);
        }
    }
    //【値の取得】キーからインデックスを計算して値を取得
    public int get(String w) {
        int index = (w.hashCode() & 0x7fffffff) % mapsize;
        //インデックスの要素がnullの場合 →未使用の要素のため0を返却
        if(fruitsmix[index]==null) {
            return 0;
        }
        //インデックスの要素がnullでない場合 →使用中の要素のためカウンタの値を返却
        else {
            return fruitsmix[index].getValue();
        }
    }
    //【クラス】Fruitsクラス
    class Fruit {
        private String fruits; //Key
        private int price;       //Value
        public Fruit(String w, int c) {fruits = w; price = c;}
        public String getKey() {return fruits;}
        public int getValue() {return price;}
        public void setValue(int c) {price = c; }
    }
}


(図)実行結果


目次にもどる

Adsense審査用広告コード


Adsense審査用広告コード


-Java

執筆者:


comment

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

関連記事

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

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

サーブレットとは?その役割やHelloWorldサンプルコードのご紹介

(0)目次&概説 (1) サーブレットの基本  (1-1) サーブレットとは?  (1-2) サーブレットの前身技術との比較  (1-3) サーブレットとJSPの違い  (1-4) サーブレットのHe …

Javaの選択ソートとは?アルゴリズムの流れ+サンプルプログラムをご紹介

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

JavaのArrrayListとLinkedListの違いについて

<目次> (1) JavaのArrrayListとLinkedListの違いについて  (1-1) 比較表(ArrayList vs LinkedList)  (1-2) まとめ  (1-3) 参考 …

JSP/Servletで必須入力チェックを実装する方法+サンプルプログラムや操作動画も紹介

<目次> (1) JSP/Servletで必須入力チェックを実装する方法  (1-1) 必須入力チェックの概要   (1-1-1) 全体の処理フロー   (1-1-2) 必須入力チェック部分の処理フロ …

  • English (United States)
  • 日本語
Top