JEP 180: Handle Frequent HashMap Collisions with Balanced Trees | 使用平衡树处理频繁的 HashMap 冲突
摘要
针对高哈希冲突条件，通过使用平衡树而不是链表来存储 java.util.HashMap 中的映射条目，提高其性能。在 LinkedHashMap 类中实现相同改进。
动机
在 JDK 8 中，这个领域的早期工作，即 替代的字符串哈希实现，仅仅改善了字符串键的冲突性能，并以向每个 String 实例添加一个新的（私有的）字段为代价。
这里提出的更改将改善任何实现了 Comparable 接口的键类型的碰撞性能。包括添加到 String 类的私有 hash32 字段的替代字符串哈希机制可以被移除。
描述
主要的思想是，一旦哈希桶中的项目数量超过了某个阈值，该桶将从使用条目的链表切换到使用平衡树。在哈希冲突较多的情况下，这将把最坏情况的性能从
这种技术已经在最新版本的 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 类的迭代顺序将会保持不变。