javaでは気軽にjava.util.HashMapを使っていますが、JDKのバージョンが上がると実装が変わっていました。
・・・
Sun JDK 1.3
例えば、HashMap#getをソースの一部は以下の通り。
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry e = tab[index]; e != null; e = e.next)
教科書的なコードです。
Sun JDK 1.4
同じくHashMap#getの一部。
int hash = hash(k);
int i = indexFor(hash, table.length);
Entry e = table[i];
while (true) {
これじゃ何やっているか分からないので、HashMap#hashとHashMap#indexForも探す。
static int hash(Object x) {
int h = x.hashCode();
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
}
static int indexFor(int h, int length) {
return h & (length-1);
}
どうやらkeyとして渡したhashCodeをビット操作している。さらにテーブルの要素数を２の累乗にして、剰余(%)ではなくビットマスク(&)でインデックスを計算している。
Sun JDK 5
型がジェネリクスになっているけど、HashMap#getはほぼ同じ。そこで、hashメソッドを探す。
static int hash(int h) {
return useNewHash ? newHash(h) : oldHash(h);
}
なんじゃ？ newHashとoldHash
private static int oldHash(int h) {
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
}
private static int newHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
useNewHashフラグですが、デフォルトはfalseなので、oldHashが使われる。
Javadocコメントを見ると、-XX起動オプションで指定するらしい。＃やったことないが・・
Set to true only by hotspot when invoked via
-XX:+UseNewHashFunction or -XX:+AggressiveOpts
Sun JDK 6
HashMap#getは同じようにhashを呼んでいる。hashの実装は以下の通り、JDK 5のnewHashとなった。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
IBM Java 1.3
引用しないが、Sun JDK 1.3と同じ。別の場所でIBMが修正を入れている（rehash）。
IBM Java 1.4
引用しないが、Sun JDK 1.4と同じ。IBMの修正を入れている。
IBM Java 5
型がジェネリクスになっているけど、ハッシュ値算出はSun JDK 1.4と同じ。つまりnewHashのロジックはなく、oldHashのロジック。
BEA Jrockit VM 5
型がジェネリクスになっているけど、ハッシュ値算出はSun JDK 1.4と同じ。つまりnewHashのロジックはなく、oldHashのロジック。
まとめ
oldHashとnewHashの違いはよく分からんが、IBMもBEAもV6くらいにnewHashに移行するのだろうか・・。
ダメなこと
自前のクラスでFoo#hashCodeが常に定数（例えば１）を返す実装にすると、常にハッシュ値が同じなので衝突します。
これはJDK 1.3のロジックだろうが、oldHashだろうが、newHashだろうが、同じです。
