3

のJavadocにIdentityHashMapよると、

このクラスは、Mapキー（および値）を比較するときにオブジェクトの同等性の代わりに参照の同等性を使用して、ハッシュテーブルを使用してインターフェイスを実装します。言い換えると、でIdentityHashMap、2つのキーk1とk2は、がである場合にのみ等しいと見なされ(k1==k2)ます。（通常のMap 実装（のようなHashMap）では、2つのキーk1とk2は、次の場合にのみ等しいと見なされ(k1==null ? k2==null : k1.equals(k2))ます。）

私が理解しているように、異なるメモリ位置を指す2つの異なるオブジェクトは、同じハッシュコードを持つことができるため、object1.equals(object2)を返すことができtrueます。ただし、異なるメモリ位置を指す2つの異なるオブジェクトは、に戻ることはできませtrueんobject1 == object2。

質問1-IdentityHashMap参照の同等性に厳密に依存している場合、それは衝突が発生しないことを意味しますか？

質問2-次のコードをデバッグすると、キーと値の両方が別々のバケットに格納されている、全部で6つのバケットが表示されます。ただし、これはHashMap、キーと値が同じバケットに格納されている場合には当てはまりません。

名前には「ハッシュ」という単語が含まれているため、キーをハッシュする必要があります。それでは、なぜキーと値を別々に格納し、特定のキーの値を取得するのでしょうか。

String A = "abc";
String B = "def";
String C = new String("abc");
Map<String, String> map1 = new IdentityHashMap<String, String>();
map1.put(A, "123");
map1.put(B, "345");
map1.put(C, "567");
4

3 に答える 3

5

IdentityHashMapキーのを使用しませんhashCodeが、キーを使用しますSystem.identityHashCode。巨大なメモリがある場合、このようなIDハッシュコードの衝突は発生する可能性がありますが、衝突することはめったにありません。もちろん、バケットの数は通常2 ^ 32-1よりはるかに少ないため、2つのキーが同じバケットに入るのを防ぐことはできません。

于 2012-10-08T09:51:18.017 に答える
3

IdentityHashMapが参照の同等性に厳密に依存している場合、それは衝突が発生しないことを意味しますか？

衝突は、そうでない場合とほぼ同じように発生する可能性があります。システムのhashCodeは一意ではなく、コレクションのサイズが2 ^^ 32でない場合でも、hashCodeのみを少数のビットに削減する必要があります。

特定のキーの値をどのように取得しますか？

コードを読んで調べます。

public V get(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
    while (true) {
        Object item = tab[i];
        if (item == k)
            return (V) tab[i + 1];
        if (item == null)
            return null;
        i = nextKeyIndex(i, len);
    }
}
于 2012-10-08T09:50:51.357 に答える
1

衝突は、2つの異なるアイテムが同じハッシュコードを持っている場合に発生するため、明らかにIdentityHashMap衝突に対処する必要があります。唯一の違いは、「通常の」ハッシュマップは、異なるオブジェクトに使用equalsできるtrueのに対し、異なるオブジェクトにIdentityHashMapは使用==できないことtrueです。

「通常の」ハッシュマップにキーと値の個別の変数がある理由は、実装の詳細ですIdentityHashMap。その実装では、線形プロービングを使用して衝突に対処し、キーと値を同じテーブルに格納します。キーは、に配置されますtable[hash]。値はに配置されtable[hash+1]ます。レギュラーは、キーとその値を同じオブジェクトに結合し、エントリをバケットに格納HashMapするクラスを定義します。Entry

于 2012-10-08T09:51:09.467 に答える