使用二叉搜索树实现哈希表

Question

这是从破解哈希表的编码采访中引起争议的一行。

哈希表的另一个常见实现（除了链表）是使用BST作为基础数据结构。

我知道这个问题之前已经被问过......这很混乱，因为每个人都给出了两个不同的答案。例如

Why implement a Hashtable with a Binary Search Tree?

在这个职位最高的投票回答说，援引上述声明是说在谈论使用二叉搜索树的哈希表的实现，没有底层阵列。我明白，由于插入的每个元素都有一个散列值（一个整数），因此这些元素构成一个总的顺序（每个元素都可以与<和>进行比较）。因此，我们可以简单地使用二叉搜索树来保存散列表的元素。

在另一方面，也有人说

Hash table - implementing with Binary Search Tree

书上说，我们应该处理冲突与二叉​​搜索树。所以有一个底层阵列，当发生冲突时，因为多个元素获得相同的散列值并被放置在阵列中的同一个插槽中，这就是BST进入的位置。

因此，阵列中的每个插槽将是一个BST，它保存具有相同散列值的元素。

我倾向于第二篇文章的论点，因为第一篇文章没有真正解释哈希表的这种实现如何处理冲突。我不认为它可以实现预期的O（1）插入/删除/查找时间。

但是对于第二篇文章，如果我们有多个获得相同散列值并放置在BST中的元素，我不确定这些元素是如何排序的（它们如何相互比较？）

请帮助我一劳永逸地解决这个问题！

Answer 1

后的第一次并没有真正解释这种实现一个哈希表如何处理冲突

随着BST，您可以使用，将不产生重复键散列函数所以就没有碰撞。这样做的好处并不是速度，而是为了减少内存消耗，并有更好的最坏情况保证。如果您正在为关键实时系统编写软件，则可能无法容忍O（n）调整哈希表的大小。

如果我们有得到相同的哈希值，并放置在BST多个元素，我不知道这些元素是如何排序（他们怎么能对相互比较？）

用另一个函数重试。最后，这一切都取决于你的数据结构的用途（内存与速度更重要吗？摊销性能还是最坏情况性能更重要？等等。）