java.lang.String#hashCode()は微妙かも。

雑記

http://d.hatena.ne.jp/kilrey/20090718#p1と関係があるような、ないような。

いきなりソース

google code search経由でhttp://hg.openjdk.java.net/jdk7/hotspot/jdkのソースを見たところ

    public int hashCode() {
        int h = hash;
        if (h == 0) {
            int off = offset;
            char val[] = value;
            int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }

となっていた。この31は適切なのだろうか。

31の由来

基本的には「経験的に良いとされている値」以外の何者でもない。もちろん、良い値の必要条件はすべて満たしているのでそれほど悪い値ではない。

素数である
大抵のハッシュ表の大きさと互いに素。
メルセンヌ数
2^N-1という値の掛算はシフト*1,引算*1で計算できる。

31^3=29791

しかし、javaのcharは16bit=2^16=65536だ。hashの最下位ビットがcharの最上位ビットに影響を及ぼすまで4ステップかかる。ASCIIコードの使用率が極めて高い欧米では常時4ステップかかっているとみなしても良いだろう。そんなハッシュ関数は嫌だ。

〆。

もしかしたら「経験的に良いとされている値」という話の「経験」はcharが8bitの環境だけなのかもしれない。2^8<31*31であり2ステップで影響を及ぼせる。しかも、ASCIIコードの表示文字0x20〜0x7Eとも相性が良さそうだ。
この推測が正しければ16bit環境向けには2^7-1=127, 2^13-1=8191辺りが適しているのではないだろうか。