java.lang.Object#hashCode()の性質

Java 実験

この前、ふと Object クラスの JavaDoc を見ていたら、こんな記述がありました。

できるかぎり、Object クラスで定義される hashCode メソッドは、異なるオブジェクトについては異なる整数値を返します。

Oracle Technology Network for Java Developers | Oracle Technology Network | Oracle

この「できるかぎり」って、どのぐらいなんでしょうか。

オブジェクト数に比例して、衝突していました。

さくっとコードを書いてみました*1。
結果は以下のグラフの通りです。

（一定数（横軸）のオブジェクトを生成し、ハッシュコードの衝突割合（縦軸）を調べました）


オブジェクトが増えれば増えるほど、衝突確率が高まっていきます。
オブジェクトが100万個だと衝突確率は 1.46% でしたが、5,000万個だと 47.75% まで高まっています。

傾向

不思議なことに、java.lang.Object#hashCode() が返す値は常に 1〜33,554,431 (0x1FFFFFF) の間でした。
int 型の範囲を限界まで使って、Integer.MIN_VALUE*2 〜 Integer.MAX_VALUE*3 の間で返すと思っていたんですが、そうではないようです。


Windows*4 と Linux*5 でやってみましたが、同じ結果でした*6
また、ClientVM と ServerVM の両方でやってみましたが、こちらも同じ結果でした。

アルゴリズム

アルゴリズムを確認するために、JavaVMのソースコードを見てみました。
ObjectSynchronizer::FastHashCode(Thread * Self, oop obj) (576行目) と 同じファイル内の get_next_hash(Thread * Self, oop obj) (530行目) がそれっぽいです。
jdk6/jdk6/hotspot: src/share/vm/runtime/synchronizer.cpp@a541ca8fa0e3


…残念ながら、ここでギブアップです（´・ω・｀）
何やっているのか、さっぱり分かりません。
（os::random() となっていることから、場合によってはただのランダムになる場合があるんでしょうか…）


どなたかわかる方いらっしゃいますか。

追記１：

「java.lang.Object#hashCode()のアルゴリズムは、ただの乱数である」というのが結論でした。


ポイントは、上記の get_next_hash メソッドに合った条件分岐で、if(hashCode == 〜) となっている個所でした。
この hashCode は、globals.hpp で「0」と定義されており、この場合のハッシュコードは os::random() （一般的な線形合同法による乱数）によって生成されます。


ちなみに、この条件分岐に使われている hashCode は VMオプション「 -XX:hashCode=? 」で変更できます。? に設定する値と、そのときの挙動は以下の通りです。

値 挙動
0 乱数（デフォルト）
1 オブジェクトのアドレス＋乱数
2 (常に)1
3 連番
4 オブジェクトのアドレス
その他 XORシフト方式*7


追記（2014年12月21日）：
Java SE 8 で、デフォルトがXORシフト方式に変更されていました。
Java8 で java.lang.Object#hashCode() の生成アルゴリズムが変更されていました。 - 地平線に行く

追記２：

ハッシュコードの上限は、「 value &= markOopDesc::hash_mask; 」という記述があり、これで決まっていました。
この hash_mask ですが、この値は 32bit 環境で 0x1FFFFFF, 64bit 環境で 0x7FFFFFFF でした*8。（これは、コメントで欽ちゃん１号さんからいただいた結果とも符合します）


そのため、java.lang.Object#hashCode()のハッシュコードは 32/64bit 環境で変わります。また、値の取り得る範囲が広い 64bit 環境のほうが、ハッシュコードが衝突する可能性が低くなります。

実験に使用したソースコード

import java.util.HashSet;
import java.util.Set;

public class HashCodeConflict {

    public static void main(String... args) {
        for (int i = 1000000; i <= 50000000; i += 1000000) {
            Set<Integer> set = new HashSet<Integer>(i, 1.0f);
            int conflict = 0;
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int j = 0; j < i; j++) {
                Object obj = new Object();

                int hashCode = obj.hashCode();
                if (!set.add(hashCode)) {
                    conflict++;
                }
                if (max < hashCode) {
                    max = hashCode;
                }
                if (min > hashCode) {
                    min = hashCode;
                }
            }

            // Excelで集計するためのログ
            // System.out.format("%d    %d    %d    %d\n", i, conflict, min, max);
            System.out.println("LoopCount: " + i);
            System.out.format("Conflict: %d (%f%%)\n", conflict,
                    ((double) conflict / i) * 100);

            System.out.println("Min: " + min);
            System.out.println("Max: " + max);
            System.gc();
        }
    }
}

*1:このコードは、「続きを読む」に記載しています。

*2:2^31 = -2,147,483,648

*3:2^31 - 1 = 2,147,483,647

*4:WindowsXP 32bit - OracleJDK 1.6.0_29

*5:Fedora16, 32bit - OpenJDK 1.6.0_24

*6:手元に環境がないのでできなかったのですが、JavaVM 64bit でも結果は変わらないのでしょうか？

*7:コメントによれば、将来的にこれがデフォルトになるかも、とのこと

*8:この定義は、globalDefinitions.hpp にありました。jdk6/jdk6/hotspot: src/share/vm/utilities/globalDefinitions.hpp@a541ca8fa0e3