String IdentityHashMap 与 HashMap 性能对比

Question

Identity HashMap 是 Java 中的特殊实现，它比较对象引用而不是 equals()，并且还使用 identityHashCode() 而不是 hashCode()。此外，它使用 linear-probe hash table 而不是 Entry list。

Map<String, String> map = new HashMap<>(); 
Map<String, String> iMap = new IdentityHashMap<>();

这是否意味着 String 键 IdentifyHashMap 如果调整正确通常会更快？

看这个例子：

public class Dictionary {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("/usr/share/dict/words"));

        String line;
        ArrayList<String> list = new ArrayList<String>();

        while ((line = br.readLine()) != null) {
            list.add(line);
        }
        System.out.println("list.size() = " + list.size());
        Map<String, Integer> iMap = new IdentityHashMap<>(list.size());
        Map<String, Integer> hashMap = new HashMap<>(list.size());

        long iMapTime = 0, hashMapTime = 0;

        long time;
        for (int i = 0; i < list.size(); i++) {
            time = System.currentTimeMillis();
            iMap.put(list.get(i), i);
            time = System.currentTimeMillis() - time;
            iMapTime += time;
            time = System.currentTimeMillis();
            hashMap.put(list.get(i), i);
            time = System.currentTimeMillis() - time;
            hashMapTime += time;
        }

        System.out.println("iMapTime = " + iMapTime + " hashMapTime = " + hashMapTime);
    }

}

尝试了非常基本的性能检查。我正在阅读字典单词 (235K) 并推入两张地图。它打印：

list.size() = 235886
iMapTime = 101 hashMapTime = 617

我认为这是一个非常好的改进，可以忽略，除非我在这里做错了什么。

Answer 1

您会发现 IdentityHashMap 的性能显着提高，但这需要付出高昂的代价。

您必须绝对确定您永远不会将具有相同值但不同身份的对象添加到地图中。

现在和将来都很难保证，而且很多人做出了错误的假设。

例如

String t1 = "test";
String t2 = "test";

t1==t2 将 return 为真。

String t1 = "test";
String t2 = new String("test");

t1==t2 会 return 错误。

总的来说，我的建议是，除非您绝对迫切需要性能提升并且确切地知道自己在做什么，并且严格锁定并评论对 class 的访问权限，否则通过使用 IdentityHashMap，您将向大量开放未来很难追踪错误的风险。

Answer 2

从技术上讲，您可以这样做以确保您拥有相同的字符串表示实例：

public class StringIdentityHashMap extends IdentityHashMap<String, String>
{
    @Override
    public String put(String key, String value)
    {
        return super.put(key.intern(), value.intern());
    }

    @Override
    public void putAll(Map<? extends String, ? extends String> m)
    {
        m.entrySet().forEach(entry -> put(entry.getKey().intern(), entry.getValue().intern()));
    }

    @Override 
    public String get(Object key)
    {
        if (!(key instanceof String)) {
            throw new IllegalArgumentException();
        }
        return super.get(((String) key).intern());
    }

    //implement the rest of the methods in the same way
}

但这对你没有太大帮助，因为 intern() 调用 equals() 来确保给定的 String 存在于或不存在于字符串池中，所以你最终会得到性能典型的 HashMap.

然而，这只会帮助您提高记忆力，而不会 CPU。没有办法实现更好的 CPU 用法并确保您的程序正确（不可能使用 JVM 的一些内部知识，这可能会改变）因为字符串可以在字符串池中，也可以不在字符串池中，而您不知道它们是否在在没有（不是隐含地）调用 equals().

Answer 3

`IdentityHashMap<String,?>` 是如何工作的？

要使 IdentityHashMap<String,?> 对任意字符串起作用，您必须 String.intern() 您 put() 的键和传递给 get() 的潜在键。（或使用等效机制。）

注意：与@m3th0dman 的回答中所述不同，您不需要 intern() 值。

无论哪种方式，驻留字符串最终都需要在某种已驻留字符串的散列 table 中查找它。因此，除非您出于某种其他原因不得不实习您的字符串（因此已经支付了费用），否则您不会从中获得太多实际性能提升。

那么为什么测试表明你可以？

您的测试不切实际的地方在于，您保留了与 put() 一起使用的键的确切列表，并按列表顺序逐一遍历它们。注意（同样可以通过将元素插入 LinkedHashMap 并简单地在其条目集上调用 iterator() 来实现。

那`IdentityHashMap`有什么意义呢？

在某些情况下可以保证（或实际上保证）对象标识与 equals() 相同。想象一下尝试实现你自己的 ThreadLocal class 例如，你可能会写这样的东西：

public final class ThreadLocal<T> {
   private final IdentityHashMap<Thread,T> valueMap;
   ...
   public T get() {
       return valueMap.get( Thread.currentThread() );
   }
}

因为您知道线程没有超越身份的平等概念。如果您的地图键是枚举值等，情况也是如此。

Answer 4

有趣的是，IdentityHashMap 可能更慢。我正在使用 Class 个对象作为键，并且发现 HashMap 的性能比 IdentityHashMap 提高了约 50%。

IdentityHashMap 和 HashMap 在内部是不同的，所以如果你的键的 equals() 方法真的很快，HashMap 似乎更好。

String IdentityHashMap 与 HashMap 性能对比

String IdentityHashMap vs HashMap performance

java

collections

hashtable

hashmap

`IdentityHashMap<String,?>` 是如何工作的？

那么为什么测试表明你可以？

那`IdentityHashMap`有什么意义呢？

String IdentityHashMap 与 HashMap 性能对比

String IdentityHashMap vs HashMap performance

java

collections

hashtable

hashmap

IdentityHashMap<String,?> 是如何工作的？

那么为什么测试表明你可以？

那IdentityHashMap有什么意义呢？

`IdentityHashMap<String,?>` 是如何工作的？

那`IdentityHashMap`有什么意义呢？