java.util.Hashtableとjava.util.HashMap

• Togetter - 「hashtableのn * 2 + 1の意義」

なるほど。

Hashtableのハッシュ関数はハッシュの再作成するときに、

    protected void rehash() {
        ...

	int newCapacity = oldCapacity * 2 + 1;
	Entry[] newMap = new Entry[newCapacity];

        ...
    }

と、古いサイズnに対して、新しいサイズを2*n+1にしているのはなぜかという話。初期値が11に設定されていて、2*n+1を繰り返すとかなりの確率で素数になるためみたい。

で、なぜ素数にしているのかはHashtableのgetが

public synchronized V get(Object key) {
	Entry tab[] = table;
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % tab.length;
	for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
	    if ((e.hash == hash) && e.key.equals(key)) {
		return e.value;
	    }
	}
	return null;
    }

と、オブジェクトのhashCodeをテーブルサイズで除算しているので、キーのオブジェクトのhashCode実装がヘボかった場合の保険ということかな。例えばテーブルサイズが偶数でhashCodeが奇数しか出力しない場合、奇数のスロットしか利用されず利用率が半分になってしまう。

あと、この時にJavaもテーブルサイズを2^nにしているというように書いたけども、ここではHashtableではなくHashMapを調べていた。HashMapの場合はリサイズする時は2倍になっている

    void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

これだと、hashCodeの実装がヘボい場合利用率が悪くなるのではと思うかもしれないが、get/putする時に、hashCodeの値にさらにhashメソッドを実行している

    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

2^nで除算すると下位ビットが同じものは同じ値になってしまうが、その前に上位ビットと排他的論理和を取ることで下位ビットが同じものでもばらつかせるようにしている。ビット演算なのでそんなに時間はかからないはず。さらに除算も2^nであるためビット演算で高速にできる。