Rainbow Engine

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

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

関連記事

Javaのフォーム認証でログインを行うと数回で固まってしまう事象の対処記録

<目次> (1) Javaのフォーム認証でログインを行うと数回で固まってしまう事象の対処記録  (1-1) 発生事象・エラーメッセージ  (1-2) 原因  (1-3) 対策 (1) Javaのフォー …

Javaのswitch-case文の構文や使い方を紹介+UFOキャッチャーの座標移動プログラムも紹介

<目次> (1) Javaのswitch-case文の構文や使い方を紹介  (1-1) switch-caseの構文  (1-2) else-if文との比較 (2) サンプルプログラムの紹介  (2- …

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

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

Javaでカンマやクォーテーションをエスケープする方法

<目次> (1) Javaでカンマやクォーテーションをエスケープする方法  (1-1) 実現方法・構文  (1-2) サンプルプログラム  (1-3) 参考:カンマとダブルクォーテーション両方のエスケ …

Javaのアノテーションを自作する方法をご紹介(サンプルプログラム付き)

(1) 自作アノテーションの作成~使用の手順  (1-1) アノテーションの宣言  (1-2) メタアノテーションの追加(任意)  (1-3) アノテーションを実際に使う(注釈の付与)  (1-4) …

  • English (United States)
  • 日本語
Top