这是《破解哈希表编码面试》中颇具争议的一句话。
Another common implementation(besides linked-list) for a hash table is to use a BST as the underlying data structure.
我知道这个问题以前已经被问过......这很令人困惑，因为每个人都给出了两个不同的答案。例如
Why implement a Hashtable with a Binary Search Tree?
这篇文章中得票最高的答案表示，上面引用的语句是在谈论使用二叉搜索树的哈希表实现，而不使用底层数组。我了解到，由于插入的每个元素都会获得一个哈希值(整数)，因此这些元素形成了一个全序(每对都可以与 < 和 > 进行比较)。因此，我们可以简单地使用二叉搜索树来保存哈希表的元素。
另一方面，其他人说
Hash table - implementing with Binary Search Tree
这本书说我们应该用二叉搜索树来处理冲突。因此存在一个底层数组，当由于多个元素获得相同的哈希值并被放置在数组中的同一个槽中而发生冲突时，BST 就发挥作用了。
因此数组中的每个槽都将是一个指向 BST 的指针，其中包含具有相同哈希值的元素。
我倾向于第二篇文章的论点，因为第一篇文章并没有真正解释哈希表的这种实现如何处理冲突。而且我认为它无法实现预期的 O(1) 插入/删除/查找时间。
但是对于第二篇文章，如果我们有多个元素获得相同的哈希值并放入 BST 中，我不确定这些元素是如何排序的(它们如何相互比较？)
请帮我一劳永逸地结束这个问题!
最佳答案
the first post does not really explain how such implementation of a hash table can handle collisions
通过 BST，您可以使用不会产生重复键的哈希函数，因此不会发生冲突。这里的优势不是速度，而是减少内存消耗，并有更好的最坏情况保证。如果您正在为关键的实时系统编写软件，您可能无法容忍 O(n) 的哈希表大小调整。
if we have multiple elements that get the same hash value and placed in a BST, I'm not sure how these elements are ordered (how can they be compared against each other?)
使用另一个函数重新哈希。
最后，这一切都取决于您的数据结构的用途(内存与速度更重要吗？摊余性能与最坏情况性能更重要吗？等等)
关于hash - 用二叉搜索树实现哈希表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44655237/