在处理哈希冲突时，为什么要使用链表而不是二叉搜索树？

Question

3

链表需要O(n)时间才能搜索，而二叉搜索树只需要O(log n)时间。那么为什么要使用链表来处理碰撞呢？我能想到的唯一原因是，插入链表的时间复杂度是O(1)，而插入二叉搜索树的时间复杂度是O(log n)。

- Adam Zerner

3个回答

5

如果哈希函数很好且哈希表的装载因子不太高，则任何一个桶中都不应该有太多冲突。链表是一种非常简单的数据结构，当冲突数量较少时已足够使用。它快速且占用空间很小。请记住，大多数桶中要么没有值，要么只有一个值。

此外，BST需要具备可排序性的要求。哈希表的一个好处是键不需要可比较性。

- John Kugelman

2

我想主要原因是易于实现。至少一种广泛使用的哈希表实现最近已经从使用链表转向使用链表和平衡树的混合结构：JEP 180: Handle Frequent HashMap Collisions with Balanced Trees在Java 8中：

主要思想是，一旦哈希桶中的项目数量超过某个阈值，该桶将从使用条目的链表切换到使用平衡树。在高哈希冲突的情况下，这将把最坏情况的性能从O（n）提高到O（log n）。

值得注意的是，在列表上使用树需要元素可以被排序。普通哈希表（带或不带链表）没有这个要求：它只需要元素可哈希并可比较相等。

- NPE

@harold：这个机制用于解决哈希冲突，因此所有的项都将按照构造方式具有相同的哈希值。 - NPE

也许他们只是进入了同一个垃圾桶。通常不会有2^32个垃圾桶。 - harold

@哈罗德：你说得对。我需要考虑一下，但这听起来像是个好主意。 - NPE

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mcdowella · Accepted Answer

哈希表的理论基础是要让散列到同一个哈希槽中的数据尽可能少。对于这些较小的数目，使用链表比使用二叉搜索树更快（常数因子更好），而且编写起来更简单、更可靠。除非你想要非常过分地使用平衡树，否则二叉搜索树的最坏情况和链表相同。