素数のプログラミングへの応用 (hash function)
hash functionの計算に素数のマジックナンバーが使われているけど、31の理由がはっきりはしなくて、モヤモヤする記事です。
素数みんな好きですよね。ただ、あまり多くの開発者はで素数判定のアルゴリズム使うことはないかも。どんなとこで使われているのか気になって調べてみました。 素数のプログラミングへの応用で多くの人が最初に思いつくのは、暗号かと思います。共通鍵暗号で使われているのは素数というより素因数分解の難しさですが、素数がめちゃくちゃ日常に入り込んでいると言えるかもです。
そしてもう一つパッと見つかったのが、hash function。JavaのString#hashCodeには素数31が使われています。
こちらはJava8の例
/**
* Returns a hash code for this string. The hash code for a
* {@code String} object is computed as
* <blockquote><pre>
* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
* </pre></blockquote>
* using {@code int} arithmetic, where {@code s[i]} is the
* <i>i</i>th character of the string, {@code n} is the length of
* the string, and {@code ^} indicates exponentiation.
* (The hash value of the empty string is zero.)
*
* @return a hash code value for this object.
*/
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;
}
この31はどこから来たのでしょうか？ この記事にあるように確かに数字に対するmodを計算してhashを計算するのであれば、素数の方が良さそうです。
しかし上を見てわかるように、JavaのString#hashCodeでは s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] のように一つ一つの文字にかけ算をして足し合わせています。
ただ、こちらの記事には、
Primes are unique numbers. They are unique in that, the product of a prime with any other number has the best chance of being unique (not as unique as the prime itself of-course) due to the fact that a prime is used to compose it. This property is used in hashing functions.
「素数はユニークだからかけ算をした値も元の素数ほどではないがユニークである」と書いてありますがいまいちピンと来ません。
以下の記事は31じゃなくて109の方が衝突少なくていいよってのを確かめている面白い記事。
なんとなくもっともらしいのはこちらの論文。 526pageに以下のような文があります。
We have done some experimental studies that suggest that 33, 37, 39, and 41 are particularly good choices for a when working with character strings that are English words. In fact, in a list of over 50,000 English words formed as the unionof the word lists provided in two variants of Unix, we found that taking a to be33, 37, 39, or 41 produced less than 7 collisions in each case! I
ただ、31と書いてないような。。
Effective Javaの第二版に以下のような文があり、衝突が少なく、計算が高速であるということで選ばれている雰囲気はあります。
A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.
