Java : Re: HashMap と IdentityHashMap

[id:lethevert:20070425:p2]について、解説を期待されていたので、説明を試みてみる。
java.util.HashMapの方は、ハッシュテーブルの実装として誰もが思い付くような標準的な実装になっています。

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

という内部クラスを宣言して、

    transient Entry[] table;

というフィールドに対して、table[hash(e)]に、Entryをリンクリスト状につないで要素を格納しています。
それに対して、IdentityHashMapの方は、

    private transient Object[] table;

というフィールドを用意して、table[2m]にキーを、table[2m+1]に値を格納しています。
そして、衝突が発生したときには、HashMapのようにリンクリスト状に要素を格納するのではなく、tableをインデックスが大きい方に辿って、空いているセルに値を格納します。
このようにすることで、IdentityHashMapでは、リンクを使わないでハッシュテーブルを実装しているところが、HashMapの実装とは大きく異なる所です。