问为什么java的HashMap不直接使用树来进行冲突链

EN

在我回答你的问题之前，先澄清一下：

从你的问题听起来，前8个节点总是由链表结构管理，而第8个节点之后的节点是由树结构管理的。

但这是它在Java8中更改后的实际工作方式：

• 如果存储桶包含少量节点(< 8)，则它对此存储桶节点的所有节点使用链表。
• 如果存储桶包含大量节点(=> 8)，它将使用树映射的即席实现动态替换它，以获取此存储桶节点的所有。

为什么是这样工作的？

你有一个更详细的解释here，但基本上：

嗯，以前带有冲突键的条目被简单地附加到链表中，后来不得不遍历链表。现在HashMap将列表提升为二叉树，使用散列代码作为分支变量。如果两个哈希是不同的，但最终在同一个桶中，则认为其中一个更大，并向右移动。如果散列相等(就像在我们的例子中一样)，HashMap希望键是可比较的，这样它就可以建立某种顺序。这不是HashMap密钥的要求，但显然是一个很好的实践。如果键不具有可比性，那么在大量散列冲突的情况下，不要期望任何性能改进。

在高哈希冲突的情况下，这种实现将把最坏情况下的性能从O(n)提高到O(log )。

作为参考，JEP 180介绍了HashMap中的这种实现更改

为什么它们不总是作为树来处理呢？

我想他们可能是这样的。我看到了两个原因，结合起来可以回答这个问题：

使用树会产生空间损失，如answer.

• Switching to a tree
• this仅在极少数冲突较多的情况下才会触发所述。一个存储桶通常不应该包含8个或更多节点。如果是这样的话，这意味着已经有了非常多的冲突(由于糟糕的键散列码实现或非常糟糕的运气)。在冲突较少的大多数情况下，简单的链表就足够了，因为时间复杂度往往是常数0(1)。