hash - 将哈希与二叉搜索树进行比较

Question

我们都知道，如果哈希函数选择得当，哈希表的插入和查找时间都是 O(1)。那么，我们要使用二叉搜索树的原因是什么？仅仅因为一个完美的哈希函数很难设计？

这里我是怎么想出这个问题的？
我注意到 标准 C++ STL 有 set和 map它们是用二叉搜索树实现的，但没有散列(不是在谈论非标准 hash_set ， hash_map )。而Ruby只有Hash .我想了解这种差异背后的理性。

Answer 1

树允许有序遍历。

哈希表的最坏情况性能是 O(N)(通过一个桶进行线性搜索)，二分搜索受限于 O(log N)。

注意:这需要平衡树 - 这就是为什么典型的实现使用自平衡树，suhc 作为红黑树。

虽然这种降级不太可能发生，但并非不可能，并且在很大程度上取决于选择合适的散列函数的能力和实际数据的分布。

树实现也可以轻松地增长到所需的大小，而哈希图在变满时开始降级(对于大多数实现，据说大约 70% 的存储桶已填充)。您要么需要重新散列整个表(再次对实时应用程序不利)，要么逐步移动到新表，这不是一个简单的实现。

最后，STL 可能只是采用了一个“基本”容器模板，即树，以避免额外的实现复杂性。