为什么 ConcurrentHashMap 元素也可以是树

Question

我看到 ConcurrentHashMap 将其 (key, value) 对存储在. Node但是，aNode也可以组织为 a TreeBin。因此，ConcurrentHashMap 的底层数据结构是一个列表，其中包含独立或树的元素。为什么数据结构既不是列表也不是树？这种更复杂的实现有什么用处？

Answer 1

二叉树结构允许通过元素的自然顺序或哈希码轻松对元素进行排序（如果项目不可比较的话）。对于相当大的哈希桶，这允许快速检索元素。

然而，在一个较小的哈希桶中，维护这棵树的成本远远大于搜索树结构所节省的成本。在这种情况下，平均而言，列表会更有效率。