何时以及如何将HashMap从链表转换为红黑树？
我正在浏览java 8的function，发现当桶上的条目集数量增加时，哈希映射使用红黑树而不是链表。
但是，这不是要求密钥是可比较的或存在密钥的某些顺序，这是如何工作的？ 这种转换何时实际发生？如何？
当一个存储桶中至少有 8个条目（ TREEIFY_THRESHOLD ）且存储桶总数超过64（ MIN_TREEIFY_CAPACITY ）时，该单个存储桶将转换为完美平衡的红黑树节点 。
当您删除条目（ UNTREEIFY_THRESHOLD == 6）时，您应该注意（如果需要）收缩。
你是正确的，键应该是可Comparable – 但并不总是需要它，如果它们是好的（如果它们具有相同的hashCode ），但是如果它们不是，则使用它：
static int tieBreakOrder(Object a, Object b) { int d; if (a == null || b == null || (d = a.getClass().getName(). compareTo(b.getClass().getName())) == 0) d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1); return d; }
所以className作为String用于比较，如果也失败，则使用System.identityHashCode （Marsaglia XOR-Shift算法）来决定左右 。
当发生这种情况时回答你的问题 - 调用resize时。 当您必须调整HashMap大小时 - 有些事情正在发生; 比如桶的数量增加了两倍（在一个条目将移动或不移动的情况下再考虑一个比特）或某个桶被转换为树。 这个过程（再次，如果你真的关心）是相当缓慢的，有些人说Java HashMap是“sloooooooow，然后是快速快速;然后它是sloooooo，然后它快速快速”（我仍然认为这是嘲弄，但那里是PauselessHashMap实现）。
这带来了两个有趣的观点。 首先是最初选择正确的Map大小（即使粗略估计也会这样做），即：
new HashMap<>(256); // choosing the size
这将避免一些resize。
第二个是为什么转换为Tree很重要（想想数据库索引以及为什么它们是BTREE ......）。 在完美树中找到具有INTEGER.MAX_VALUE条目（理论上）的条目需要多少步骤。 最多32个。