字符串IdentityHashMap与HashMap的性能表现

Question

Identity HashMap 是 Java 中的一种特殊实现，它比较对象的引用而不是使用 equals() 方法，并且使用 identityHashCode() 而不是 hashCode()。此外，它使用线性探测哈希表而不是条目列表。

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

这是否意味着如果正确调整，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 

我认为这是一个很好的改进，除非我在这里做错了什么。

- Himanshu Ahire

---

根据Java文档，“这个类不是一个通用的Map实现！虽然这个类实现了Map接口，但它有意违反Map的常规契约，强制要求在比较对象时使用equals方法。这个类仅设计用于极少数需要使用引用相等语义的情况。”因此，理想情况下，您不应该仅为了性能改进而使用它... 另外，您可以解释一下需要优化多少数据才能比HashMap更快，但不要进行过早的优化... - coder

如果我没错的话，String == String 的检查与 String.equal(String) 方法完全相同，所以我认为在这种情况下没有关系。那么，linear-probe hash table 是否会比常规 entry Set 提供改进呢？我只是好奇，所以没有确切的计数，但我们可以考虑可能有 5K+ 个字符串吗？ - Himanshu Ahire

不。string == string并不等同于String.equal(string)。试试这个：String s1 = "abc"; String s2 = new String("abc"); 打印 (s1 == s2)。 - coder

感谢您的纠正，我的假设是错误的。 - Himanshu Ahire

我做了一些快速实验。我没有使用适当的基准测试，所以这些结果仅供参考，但是在我的测试程序中，IdentityHashMap 大约快了20%。然而，我完全同意程序员的观点。你几乎肯定不应该使用 IdentityHashMap。 - Paul Boddington

Answer 1

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

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

注意：与@m3th0dman的答案所述不同，您不需要对值进行intern()。

无论哪种方式，将字符串放入池中最终都需要在已经放入池中的字符串的哈希表中查找它。因此，除非您必须出于其他原因将字符串放入池中（并且因此已经付出了代价），否则您不会从中获得实际的性能提升。

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

您的测试不太现实的地方在于，您保留了使用put()的确切键列表，并按照列表顺序逐个迭代它们。请注意（通过将元素插入到LinkedHashMap中并简单地在其条目集上调用iterator()也可以实现相同的效果）。

IdentityHashMap的意义是什么？

有些场景可以保证（或实际上保证）对象标识与equals()相同。例如，想象一下尝试实现自己的ThreadLocal类，您可能会编写以下代码：

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

因为您知道线程除了身份之外没有相等概念。同样适用于如果您的映射键是枚举值等。

- biziclop

---

这是否意味着我们可以安全地使用单例类和Identity Hash Map，从而提高性能？ - Himanshu Ahire

@Himanshu 它可以安全地与所有实例控制的类一起使用。然而，在实践中，大多数这些类只有很少的实例（枚举不太可能有超过100个值，线程计数可能会超过这个值，但不会太多），并且具有非常快速的equals()实现（通常基于对象标识），因此使用IHM带来的性能提升可以忽略不计。 - biziclop

Answer 2

您将会看到IdentityHashMap有显著的更快的性能，但这是以巨大的代价为代价的。您必须非常确定您永远不会将具有相同值但不同标识的对象添加到地图中。这很难保证现在和未来，许多人都会做出错误的假设。例如：

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

t1==t2会返回true。

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

t1==t2将返回false。

总的来说，我建议除非你绝对需要性能提升并且确切知道自己在做什么，并且严格锁定和注释类的访问，否则使用IdentityHashMap会使你面临未来极难追踪的大量风险。

- Tim B

Answer 3

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

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()。

- Random42

Answer 4

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

IdentityHashMap和HashMap在内部不同，因此如果您的键的equals（）方法非常快，则HashMap似乎更好。

- Stefan Reich