3

根据Javadocs，IdentityHashMap它说

此类Map使用哈希表实现接口，在比较键（和值）时使用引用相等代替对象相等。换句话说，在 a 中IdentityHashMap，当且仅当 时，两个键 k1 和 k2 被认为相等(k1==k2)。（在正常Map 实现中（如HashMap），当且仅当 时，两个键 k1 和 k2 被认为是相等的(k1==null ? k2==null : k1.equals(k2))。）

据我了解，指向不同内存位置的两个不同对象仍然可以具有相同的哈希码，因此object1.equals(object2)可以返回true. 但是指向不同内存位置的两个不同对象永远无法返回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. 虽然如果你有一个巨大的内存，这种身份哈希码的冲突是可能的，但它们很少见。这当然不会阻止两个键最终在同一个存储桶中，因为存储桶的数量通常远小于 2^32 - 1。

于 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

当两个不同的项目具有相同的哈希码时会发生冲突，因此显然IdentityHashMap必须处理冲突。唯一的区别是“常规”哈希映射equals可以true用于不同的对象，而不能IdentityHashMap用于不同的对象。==true

“常规”哈希映射具有单独的键和值变量的原因是 的实现细节IdentityHashMap：它的实现使用线性探测来解决冲突，并且它还将键和值存储在同一个表中：键放置在table[hash]，而该值位于table[hash+1]。常规HashMap定义了一个Entry类，它将键与其值组合在同一个对象中，并将条目存储在桶中。

于 2012-10-08T09:51:09.467 回答