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

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

関連記事

TwitterのAPIライブラリでリツイートした人の一覧を取得する方法

<目次> (1) TwitterのAPIライブラリでリツイートした人の一覧を取得する方法  (1-1) 構文  (1-2) サンプルプログラム (1) TwitterのAPIライブラリでリツイートした …

JSP/Servletでログイン・ログアウト機能を作成する方法

<目次> (1) JSP/Servletでログイン・ログアウト機能を作成する方法  (1-1) ログイン   (1-1-1) 概要・構文   (1-1-2) サンプルプログラム  (1-2) ログアウ …

JSPやServletの画面をスマホ表示に対応させる方法~メディアクエリの導入~

<目次> (1) JSPやServletの画面をスマホ表示に対応させる方法 (2) 設定手順  (2-1) Step1:ビューポートの設定  (2-2) Step2:メディアクエリを記述したcssファ …

TomcatでEclipseを使う際にserver.xmlを編集しても上書きされる事象の対処方法

<目次> (1) TomcatでEclipseを使う際にserver.xmlを編集しても上書きされる事象の対処方法  (1-1) 発生状況・エラーメッセージ  (1-2) 原因  (1-3) 対処法 …

Twitter APIのRate Limit Exceedエラー(code – 88)を回避するための簡易的な対策について

<目次> (1) Twitter APIのRate Limit Exceedエラー(code – 88)を回避するための簡易的な対策について  (1-1) 対策①:APIの使用回数に閾値を設ける  ( …

  • English (United States)
  • 日本語
Top