java - 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) 并插入两张 map 。它打印:

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

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

Answer 1

如何IdentityHashMap<String,?>工作？

制作IdentityHashMap<String,?>适用于任意字符串，你必须 String.intern()两个键你put()以及您传递给 get() 的潜在 key . (或使用等效机制。)

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

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

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

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

IdentityHashMap 有什么意义？那么呢？

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

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

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