Rainbow Planet

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

Java

JavaのhashCode()で31を掛け算する理由について

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

<目次>

(1) JavaのhashCode()で31を掛け算する理由について
 (1-1) ハッシュの計算のソースコード
 (1-2) ソースコードに登場する代表的な変数
 (1-3) ソースコード解説

(1) JavaのhashCode()で31を掛け算する理由について

Javaでハッシュを計算するhashCode()について、実際のプログラムを見てみると「31」で掛け算する計算を行っていますが、今日はこの「31の意味」について書きたいと思います。

こんな人におすすめ
・hashCode()メソッド中に31で割る式があるけど、この「31」はどういう意味?を知りたい方
・hashCode()メソッドはどのような原理でハッシュ値を計算しているのか?を知りたい方

(1-1) ハッシュの計算のソースコード

以下がStringクラスのhashCode()メソッドのソースコードです。Eclipseなどで「[String変数].hashCode()」の部分を右クリックして「Open Declaration」を押下すると、hashCodeメソッドのソースコードを見る事ができます。

(ソースコード)

public int hashCode() {
	int h = hash;
	if (h == 0 && value.length > 0) {
		char val[] = value;
		for (int i = 0; i < value.length; i++) {
			h = 31 * h + val[i];
		}
		hash = h;
	}
	return h;
}

(図111)Open Declaration

目次にもどる

(1-2) ソースコードに登場する代表的な変数

ソースコードを理解するために、まず代表的な変数の意味を抑えます。

(表)

項目 説明
hash ハッシュ値を保持するための変数です。これはStringクラスのメンバ変数として下記のように定義されているものです。

private int hash; // Default to 0

初期値は「0」ですが、一回計算するとその結果が格納されるため、次回以降に同じ文字列に対しては値が入った状態になります。

value 文字列の各文字を1文字ずつ保持するためのchar型の配列です。これはStringクラスのメンバ変数として下記のように定義されているもので、文字列の生成時に値が入ります。

private final char value[]

目次にもどる

(1-3) ソースコード解説

先ほどのソースコードにコメントを追記したバージョンを掲載します。ただし「h = 31 * h + val[i];」の部分は難しいので、コードの後の(補足)欄で更に補足します。

(ソースコード)

public int hashCode() {
	//前回の計算結果(hash)をhに格納
	int h = hash;
	//前回の計算結果が0(なし) AND 文字列長>0(文字列あり)の場合
	if (h == 0 && value.length > 0) {
		//文字列をchar型の配列に格納(1文字ずつ計算に当てはめるため)
		char val[] = value;
		//文字列長の長さ(文字数)だけループ
		for (int i = 0; i < value.length; i++) {
			// 31 * h => 1つ前のループまでの結果×31倍
			// + val[i] => 次の文字の10進数のASCIIコードを加算
			// (char型は足し算する時は整数とみなされる性質を利用)
			h = 31 * h + val[i];
		}
		hash = h;
	}
	return h;
}
 
(補足)「h = 31 * h + val[i];」の計算の仕組み
文字列n+1番目の文字の10進数ASCIIコード(例:H=72)をval [n] とし、n乗を「^n」と表すと、この繰り返し計算は以下のような数式になります。
 
(計算式)
h[n] = 31 * h[n-1] + val[n-1] ・・・(★)
    = 31 * (31 * h[n-2] + val[n-2]) + val[n-1]
    = 31 * (31 * (31 * h[n-3] + val[n-3]) + val[n-2]) + val[n-1]
= 31 * (31 * (31 * (31 * h[n-4] + val[n-4]) + val[n-3]) + val[n-2]) + val[n-1]
・・・(続く)
    = val[0]*31^(n-1) + val [1]*31^(n-2) + ... + val [n-1] ・・・(▲)
式の最後の行(▲)の状態ですと、掛け算の計算を(n-1)+(n-2)+….+1 = n(n-1)/2回繰り返す事になってしまい(オーダーがO(N*N))処理効率が良くありません。そこで最初の行(★)の形式で計算を繰り返す事で、n回の計算で済みます(オーダーがO(N))。
 
また掛け算で「31」を掛けている理由はハッシュの値がバラつくようにするためです。なぜ「31」なのか?という点については、パフォーマンスが良いからです。31の掛け算の場合、内部的には「元の数」を「5ビット左にシフト」して、そこから元の数を引き算する処理として扱われるため、計算が速くなるメリットがあります。

(5ビットシフトして元の数を引く)

31 * i == (i << 5) - i

目次にもどる

Adsense審査用広告コード


Adsense審査用広告コード


-Java

執筆者:


comment

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

関連記事

JSPとは?役割や基本文法およびHelloWorldのサンプルプログラムの紹介

(0)目次&概説 (1) JSPの基本  (1-1) JSPとは?  (1-2) JSPのHelloWorld (2) JSPの基本文法  (2-1) ディレクティブ  (2-2) アクションタグ   …

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

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

Tomcatの起動時のエラー「アドレスは既に使用中です」や「必要な幾つかのポートがすでに使用中です」の対処方法

<目次> (1) Tomcatの起動時のエラー「アドレスは既に使用中です」や「必要な幾つかのポートがすでに使用中です」の対処方法  (1-1) 発生状況  (1-2) 原因  (1-3) 対処方法 ( …

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

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

Javaのアーキテクチャ概要やプログラムのコンパイルから実行までの流れ

(0)目次&概説 (1) 記事の目的  (1-1) 目的 (2) Javaのアーキテクチャ概要・概観  (2-1) プログラムのコンパイル~実行の流れ  (2-2) Javaアーキテクチャの特徴    …

  • English (United States)
  • 日本語
Top