java - 为什么 IdentityHashMap 使用线性探测来解决冲突

Question

正如我们所知，在 java 集合框架中，Map 中的每个类都使用 Chaining 来解决冲突，但 IdentityHashMap 使用对其进行线性探测。

如果你看 java 文档，它已经提到:

For many JRE implementations and operation mixes, this class will yield better performance than HashMap (which uses chaining rather than linear-probing).

我的问题是:

• 如果 中的性能更好，为什么实现者只对 IdentityHashMap 而不是所有 Map 实现使用 liner probing>线性探测

• 为什么线性探测然后链接会提高性能。

坦克。

Answer 1

当您构建身份 HashMap 时，不可能找到两个彼此相等但不是同一对象的实例。它还使用 System.identityHashCode ，IdentityHashMap 的设计者预先知道它有可能发生冲突，并且已知这种可能性非常小。在这些“实验室”条件下，就性能而言，线性探测似乎是更好的选择。

我怀疑类库的设计者在“常规” HashMap 中使用链接而不是线性探测的原因是他们希望即使在哈希函数不是最优的情况下也能保持良好的性能。