JEP 180：使用平衡树处理频繁的 HashMap 冲突
概述
通过使用平衡树而不是链表来存储映射条目，从而提高在高哈希冲突条件下 java.util.HashMap 的性能。在 LinkedHashMap 类中实现相同的改进。
动机
JDK 8 中此领域早期的工作，即替代的字符串哈希实现，仅改进了字符串键值的冲突性能，并且这样做是以在每个 String 实例中添加一个新的（私有）字段为代价的。
这里提出的更改将改进任何实现 Comparable 的键类型的碰撞性能。然后可以移除替代的字符串哈希机制，包括添加到 String 类中的私有 hash32 字段。
描述
主要的想法是，一旦哈希桶中的条目数量增长超过某个阈值，该桶就会从使用链表转换为使用平衡树。在哈希冲突严重的情况下，这将把最坏情况下的性能从 O(n) 提升到 O(log n)。
该技术已经在最新版本的 java.util.concurrent.ConcurrentHashMap 类中实现，同时也计划作为 JEP 155 的一部分包含在 JDK 8 中。这部分代码将会被重用来在 HashMap 和 LinkedHashMap 类中实现相同的思想。只有实现部分会发生变化；接口和规范都不会修改。某些用户可见的行为（例如迭代顺序）将在其当前规范的范围内发生变化。
我们不会在旧的 Hashtable 类中实现此技术。该类自 Java 1.0 以来一直是平台的一部分，已知一些使用它的旧代码依赖于迭代顺序。Hashtable 将恢复到引入替代字符串哈希实现之前的状态，并保持其历史上的迭代顺序。
我们也不会在 WeakHashMap 中实现这种技术。虽然曾经尝试过，但由于必须考虑弱键（weak keys）的复杂性，导致微基准测试性能出现了不可接受的下降。WeakHashMap 也将恢复到之前的状态。
在 IdentityHashMap 类中不需要实现这种技术。它使用 System.identityHashCode() 来生成哈希码，因此冲突通常很少见。
测试
- 运行 Doug Lea 的 JSR 166 CVS 工作区中的
Map测试（包含一些微基准测试） - 运行标准工作负载的性能测试
- 可能开发新的微基准测试
风险与假设
此更改将为平衡树的添加和管理引入一些开销；我们预计该开销可以忽略不计。
此更改可能会导致 HashMap 类的迭代顺序发生变化。HashMap 规范明确表示不保证迭代顺序。而 LinkedHashMap 类的迭代顺序将得以保持。