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

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

関連記事

JDBCドライバとは?概要や使い方をご紹介

<目次> (1) JDBCドライバとは?概要や使い方をご紹介  (1-1) JDBC及びJDBCドライバとは?   (1-1) JDBC API   (1-2) JDBCドライバマネージャー   (1 …

JavaのJDBC接続でjava.sql.SQLRecoverableException: Closed Connectionが発生した時の解決メモ

(0)目次&概説 (1) エラー事象の概要  (1-1) エラーの発生状況  (1-2) エラーメッセージ全文 (2) エラーの原因 (3) エラーの対処方法  (3-1) エラーの修正内容  (3- …

Servlet(サーブレット)におけるフォワード(forward)とリダイレクト(redirect)の違い

<目次> (1) Servlet(サーブレット)におけるフォワード(forward)とリダイレクト(redirect)の違い  (1-1) フォワード(forward)とは?  (1-2) リダイレク …

Javaのラッパークラスとは?使い方や一覧をご紹介

<目次> (1) Javaのラッパークラスとは?使い方や一覧をご紹介  (1-1) ラッパークラスとは?  (1-2) 構文(オブジェクト生成)  (1-3) 代表的なメソッド(Integerを例に) …

Javaでdouble型での誤差を対処する方法について+サンプルプログラムも紹介

(1) Javaでの誤差の対処法  (1-1) 対処が必要なケース  (1-2) 対処の方法   (1-2-1) BigDecimalクラスでの対処   (1-2-2) int型を優先的に使い対処   …

  • English (United States)
  • 日本語
Top