マジックナンバー【31】

演算処理上の特性

整数nに対して31を乗算するということは、2進数の世界では、5bit左シフトして元の値を引くことで擬制できます。

hash = hash * 31 + fieldValue; //fieldValueはint値と仮定。通常は .hashCode() によって得たint値
//すなわち
hash = (hash << 5) - hash + fieldValue;
//具体例でhashが0b00000110だった場合
0b0..00_11000000 + 0b1..11_1111010 + 0b0..00_00001001;

ビットシフト演算はとてもCPUで高速の扱われる処理のひとつです。さらに、-hashも、2の補数をとって加算するだけの単純な処理です。
よって例示したようにビット加算演算1行で処理が完結します。

すなわち、31の乗算はCPU効率が良い処理が実現されます。

素数ということ

int hash = 17;
hash = hash * 31 + firstField.hashCode();
hash = hash * 31 + nextField.hashCode();
hash = hash * 31 + otherField.hashCode();
...

このコードは私がよく実装するhashCode()のひとつです。（一時期は趣向で初期値をMyClass.class.getName().hashCode()にしていました）

後述のhashの離散的な結果を得るためのアプローチとして、firstFieldがnullや0の場合に備えて素数同士の掛け算を冒頭に挿入し、 かつ全fieldに対して同じ処理を施すことで実装の抜け漏れミスの可能性を低減させます。

hashという衝突可能性の低減が求められる処理では、素数を含める乗算によって、他の値と結果が同じになる可能性を低減できます。
……素数蝉ではありませんが、似たような特性を感じさせます。

/* obj1 の仮想hash値 */
int hash = 8;
hash = hash * 8 + 20;
hash = hash * 8 + 40;
// hash = 712
        

/* obj2 の仮想hash値 */
int hash = 8;
hash = hash * 8 + 10;
hash = hash * 8 + 120;
// hash = 712
        

これを 8 から 17と31 にすることで

/* obj1 の仮想hash値 */
int hash = 17;
hash = hash * 31 + 20;
hash = hash * 31 + 40;
// hash = 16997
        

/* obj2 の仮想hash値 */
int hash = 17;
hash = hash * 31 + 10;
hash = hash * 31 + 120;
// hash = 16767 Δ230(=23×2×5）
/*
 * hash=16997を狙うなら、
 * 最後の120は350に置き換えることで
 * この場合は衝突させることができます
 */
        

例示のように、8だった場合では容易に衝突が起こせましたが、17や31を使う処理では衝突が起きづらく、また離散（数値の距離）にも素数が絡みました。

hash論理値への貢献

前述の5bit左シフトをした段階で、下位4bitは0が生じます。そこに元の値を引くことにはなりますが、 それでも次のfieldValueがhashに寄与する下地を大きく作ることになります。

それでは、31（すなわち5ビットシフト）以外の2^nの数値はどうでしょうか？
1～4ビットシフト（2,4,8,16）は、次のfieldValueが寄与できる隙がまだ小さいと考えられます。
また、31より大きい6～ビットシフト（64,128...）は、シフトのし過ぎと考えます。懸念は多量のフィールドを処理した際に最初の頃の値の貢献が喪われることです

hash値に、すべてのフィールドの相違を適度に取り込むという目的から、演算時点より「前」も「後」も喪失させない、ちょうどよさが31（32の5bitシフト）にはあります。
31はハッシュ値の理論への適合性が高いと言えます。