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

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

関連記事

JVMの基本アーキテクチャと各サブシステム等の概要説明について

(0)目次&概説 (1) 記事の目的 (2) Javaのアーキテクチャ概要・概観 (3) JVMのアーキテクチャ概要  (3-1) JVMの概観  (3-2) JVMの主要サブシステム1:Class …

Javaのstatic変数とは?その特徴及び付けた場合と付けない場合の違いを解説

(0)目次&概説 (1) static修飾子  (1-1) staticメンバとは?  (1-2) static変数   (1-2-1) static変数の説明と特徴   (1-2-2) static …

Javaのenumとは?使い方や意味を様々な利用シーンでご紹介(if、for、switch他)

<目次> (1) Javaのenumとは?意味や用途を様々な利用シーンでご紹介   (1-1) enumとは?  (1-2) 構文(enumの定義)  (1-3) 様々なenumの使用例 (1) Ja …

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

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

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

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

  • English (United States)
  • 日本語
Top