跳到主要内容

JEP 180：处理频繁的 HashMap 与平衡树的冲突

概括​

java.util.HashMap通过使用平衡树而不是链表来存储映射条目，提高在高哈希冲突条件下的性能。在班级中实施同样的改进LinkedHashMap。

动机​

JDK 8 中该领域的早期工作，即替代字符串哈希实现，仅改进了字符串值键的冲突性能，但这样做的代价是向每个String实例添加新的（私有）字段。

此处提出的更改将提高任何实现Comparable.然后可以删除替代的字符串散列机制，包括hash32添加到类中的私有字段。String

描述​

其主要思想是，一旦哈希桶中的项目数量超过某个阈值，该桶就会从使用条目链表切换到使用平衡树。在哈希冲突较高的情况下，这会将最坏情况下的性能从 O(n) 提高到 O(log n)。

该技术已在该类的最新版本中实现java.util.concurrent.ConcurrentHashMap，该类也计划作为JEP 155的一部分包含在 JDK 8 中。该代码的部分内容将被重新用于在HashMap和LinkedHashMap类中实现相同的想法。仅实现会发生变化；不会修改任何接口或规格。一些用户可见的行为（例如迭代顺序）将在其当前规范的范围内发生变化。

我们不会在遗留Hashtable类中实现此技术。自 Java 1.0 以来，该类一直是平台的一部分，并且已知一些使用它的遗留代码依赖于迭代顺序。Hashtable将恢复到引入替代字符串哈希实现之前的状态，并将保持其历史迭代顺序。

我们也不会在 WeakHashMap 中实现这种技术。我们进行了尝试，但必须考虑弱密钥的复杂性导致微基准性能下降得令人无法接受。WeakHashMap也将恢复到之前的状态。

无需在IdentityHashMap课堂上实现此技术。它用于System.identityHashCode()生成哈希码，因此冲突通常很少见。

测试​

  • 从 Doug Lea 的 JSR 166 CVS 工作区运行Map测试（包括几个微基准）
  • 运行标准工作负载的性能测试
  • 可能开发新的微基准

风险和假设​

这一变化将为平衡树的添加和管理引入一些开销；我们预计这一开销可以忽略不计。

此更改可能会导致类的迭代顺序发生更改HashMap。该HashMap规范明确不保证迭代顺序。类的迭代顺序LinkedHashMap将保持不变。