＜目次＞
(１) JavaのhashCode()で31を掛け算する理由について
(１-１) ハッシュの計算のソースコード
(１-２) ソースコードに登場する代表的な変数
(１-３) ソースコード解説
(１) JavaのhashCode()で31を掛け算する理由について
Javaでハッシュを計算するhashCode()について、実際のプログラムを見てみると「31」で掛け算する計算を行っていますが、今日はこの「31の意味」について書きたいと思います。
こんな人におすすめ
・hashCode()メソッド中に31で割る式があるけど、この「31」はどういう意味？を知りたい方
・hashCode()メソッドはどのような原理でハッシュ値を計算しているのか？を知りたい方
(１-１) ハッシュの計算のソースコード
以下が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;
}
（図１１１）Open Declaration
(１-２) ソースコードに登場する代表的な変数
ソースコードを理解するために、まず代表的な変数の意味を抑えます。
（表）
| 項目 | 説明 |
| hash | ハッシュ値を保持するための変数です。これはStringクラスのメンバ変数として下記のように定義されているものです。
private int hash; // Default to 0 初期値は「0」ですが、一回計算するとその結果が格納されるため、次回以降に同じ文字列に対しては値が入った状態になります。 |
| value | 文字列の各文字を1文字ずつ保持するためのchar型の配列です。これはStringクラスのメンバ変数として下記のように定義されているもので、文字列の生成時に値が入ります。
private final char value[] |
(１-３) ソースコード解説
先ほどのソースコードにコメントを追記したバージョンを掲載します。ただし「h = 31 * h + val[i];」の部分は難しいので、コードの後の（補足）欄で更に補足します。
（ソースコード）
public int hashCode() {
//前回の計算結果（hash）をhに格納
int h = hash;
//前回の計算結果が0（なし） AND 文字列長>0（文字列あり）の場合
if (h == 0 && value.length > 0) {
//文字列をchar型の配列に格納（１文字ずつ計算に当てはめるため）
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ビットシフトして元の数を引く）
31 * i == (i << 5) - i
