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

Question

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

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

Answer 1

树允许按顺序遍历。

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

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

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

树的实现也很容易增长到所需的大小，而哈希图在满时开始退化（对于大多数实现，据说大约 70% 的桶被填满）。您要么需要重新散列整个表（再次，对实时应用程序不好），要么逐步移动到新表，这不是一个简单的实现。

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

Answer 2

补充一下 peterchen 的答案，虽然理论上哈希结构在插入和删除方面更快，但在很大程度上取决于实际数据、选择的哈希函数和数据量。

• 一个完美的哈希函数取决于数据的数量和分布。

在最佳情况和最差情况之间存在较大的性能差异使它们不适合通用结构。另一方面，二叉树更容易预测，与所使用的数据量/类型无关，即使在最佳情况下效率较低。

Answer 3

STL 最初并未在容器中包含哈希表，因为哈希表更复杂——您必须在开放和封闭寻址之间进行选择，更不用说哈希函数等了。当时，Stepanov 和 Stroustrup 试图加快速度在它上面取得进展，以便它很快被接受为标准。

另一方面，树相对简单。众所周知，由于这些是内存数据结构，我们可以只使用二叉树而不是 B 树。然后是在 AVL 和 RB 树之间进行选择。由于我无法评论更好的性能特征，因此倾向于选择 RB 树，但是关于这两种结构（AVL和RB）的维基百科文章会以相对较好的细节告诉您更多信息。

否则，树和哈希表适用于不同的事物。如果您需要快速插入或检索，并且不关心它们的存储顺序，那么哈希表很好。如果您需要插入和检索的排序特征和强有力的保证，那么二叉树就很好。另一个好的经验法则是剖析。由于两者的大多数用途都与接口兼容，因此分析以查看哪个可以为您提供更好的性能也有帮助。

Answer 4

您可以按顺序访问二叉搜索树中的数据。

Answer 5

好吧，搜索树是有序的，哈希不是。

Answer 6

要使用树，您需要一种对树中的项目进行排序的方法。要使用哈希表，您需要一个函数来计算哈希表中项目的哈希值。

有趣的是，.NET 框架要求每个类都实现（或继承）GetHashCode使每个对象都可以存储在哈希表中的功能。但是，这也给需要实现语义正确的哈希函数的开发人员增加了额外的负担，即使他们不打算对类进行哈希处理。一种解决方案是返回一个GetHashCode在语义上是正确的常量值，但如果该函数用于散列，则效率不高。

Answer 7

如果你能侥幸逃脱，你应该总是更喜欢散列而不是二叉搜索树。哈希比树具有更高的内存开销，但它们使用的所有内存都可以分配在一个大块中。对于树，添加的每个节点都需要单独分配，这会导致高度碎片化并且不利于性能。类似于您更愿意从 1 个文件中读取 1000 个字节而不是从 1000 个不同文件中读取 1 个字节。

哈希不起作用的情况是订购问题。例如，假设您正在编写一个内存分配器，并且您将空闲的内存块存储在一个数据结构中。键是块的大小，值是指向它们的指针。

内存请求需要查看此数据结构并找到满足请求的最小（意味着排序！）块。例如，如果您有键为 10、20、30 的块，并且请求 20 字节的内存，则选择第二个块。哈希图可以轻松做到这一点。

但是如果请求是 22 字节呢？由于没有值为 20 的键，因此您必须迭代整个哈希图以找到正确的键 (30)，这是一个 O(n) 操作。但是如果你使用了一棵树，那么“找到比给定键大的最小键”是一个 O(log n) 操作。

Answer 8

在 C++ 时代，人们仍然是数据结构和算法的核心学术方法的拥护者，因此他们更喜欢具有较小内存占用和易于理解的最佳和最坏情况行为的结构。

到 Ruby 出现时，出于脚本编写的目的，人们意识到他们更喜欢简单而不是原始性能，并且由于哈希表允许两个数组的语义（如果您使用顺序索引作为键）和字典（如果您使用自然键） ，它们被认为是更通用的数据结构。