Rainbow Engine

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

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

関連記事

int型のオーバーフロー(桁あふれ)とは?実際の発生パターンと併せてご紹介

  <目次> (1) int型のオーバーフロー(桁あふれ)とは?実際の発生パターンと併せてご紹介  (1-1) int型のオーバーフローとは?  (1-2) int型のオーバーフローが発生す …

CentOS7にEclipseをインストールする手順

<目次> (1) CentOS7にEclipseをインストールする手順  (1-1) JDKのインストール  (1-2) Eclipse資源のダウンロード  (1-3) Eclipseのインストール …

JDKのインストール手順+どれを選択すれば良いか?&確認の方法は?をご紹介

  <目次> (1) JDKのインストール手順+どれを選択すれば良いか?&確認の方法は?をご紹介  (1-0) STEP0:JDKのインストールでどれを選択すれば良いか?  (1-1) ST …

JSP Servletで共通のヘッダーを設定する方法

<目次> (1) JSP Servletで共通のヘッダーを設定する方法  (1-1) 構文  (1-2) サンプルプログラム  (1-3) 参考 (1) JSP Servletで共通のヘッダーを設定す …

TwitterAPIのJavaでの使い方をご紹介~【入門編】Twitter4j導入~ハッシュタグでツイート検索するまで~

<目次> (1) TwitterAPIのJavaでの使い方をご紹介  (1-1) STEP0:前提条件  (1-2) STEP1:ライブラリ(jar)のダウンロード  (1-3) STEP2:アプリケ …

  • English (United States)
  • 日本語
Top