二叉搜索树优于哈希表的优点

小开

二叉树的一个“优点”是，它可以被遍历以按顺序列出所有元素。这对于哈希表来说并非不可能，但对于设计成哈希结构的普通操作来说并非如此。

小开

Hashtable 在创建的时候会占用更多的空间——它会为未插入的元素提供可用的插槽(不管它们是否被插入) ，一个二叉查找树只会有它需要的那么大。另外，当散列表需要更多空间时，扩展到另一个结构可以会很耗时，但这可能取决于实现。

小开

最佳答案

请记住，二叉搜索树(基于引用的)是内存高效的。它们不会保留超过需要的内存。

For instance, if a hash function has a range R(h) = 0...100, then you need to allocate an array of 100 (pointers-to) elements, even if you are just hashing 20 elements. If you were to use a binary search tree to store the same information, you would only allocate as much space as you needed, as well as some metadata about links.

小开

二叉树的搜索和插入速度较慢，但具有中缀遍历的非常好的特性，这本质上意味着您可以按照排序顺序迭代树的节点。

Iterating through the entries of a hash table just doesn't make a lot of sense because they are all scattered in memory.

小开

二叉查找树可以通过 坚持不懈接口实现，返回一个新树，但是旧树仍然存在。经过仔细实现，新旧树共享它们的大部分节点。不能使用标准的哈希表进行此操作。

小开

二进制树相对于哈希表的主要优势在于，二进制树提供了两个额外的操作，而这两个操作是哈希表无法(轻松、快速地)完成的

找到最接近(不一定等于)某个任意键值的元素(或上下最接近的元素)
按排序顺序遍历树的内容

这两者是连接的——二叉树将其内容保持在排序顺序中，因此需要排序顺序的事情很容易做到。

小开

一个(平衡的)二叉查找树还有一个优点，那就是它的渐近复杂度实际上是一个上界，而散列表的“常数”时间是分摊时间: 如果你有一个不合适的散列函数，你可能最终退化为线性时间，而不是常数。

小开

如果希望以排序的方式访问数据，则必须与哈希表并行地维护排序列表。一个很好的例子是。网。(见 http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx)。

这样做的副作用是不仅减缓了插入的速度，而且比 b 树消耗更多的内存。

此外，由于对 b 树进行了排序，因此很容易找到结果的范围，或者执行联合或合并。

小开

除了所有其他的好评:

Hash tables in general have better cache behavior requiring less memory reads compared to a binary tree. For a hash table you normally only incur a single read before you have access to a reference holding your data. The binary tree, if it is a balanced variant, requires something in the order of K * lg (n) memory reads for some constant k.

另一方面，如果敌人知道你的哈希函数，敌人可以强制你的哈希表进行冲突，极大地阻碍了它的性能。解决方案是从一个家族中随机选择散列函数，但是 BST 没有这个缺点。此外，当散列表压力增长过大，你往往倾向于扩大和重新分配散列表，这可能是一个昂贵的操作。BST 在这里的行为比较简单，不会突然分配大量数据并执行重新散列操作。

树往往是最终的平均数据结构。它们可以作为列表，可以很容易地并行操作拆分，具有快速删除，插入和查找的顺序为 O (lg n)。他们没有做好 尤其是，但他们也没有任何过分恶劣的行为。

Finally, BSTs are much easier to implement in (pure) functional languages compared to hash-tables and they do not require destructive updates to be implemented (the 坚持不懈 argument by Pascal above).

小开

BST 还在 O (logn)时间内提供“ findPredecessor”和“ findSuccessor”操作(查找下一个最小的和下一个最大的元素) ，这也可能是非常方便的操作。哈希表不能提供这样的时间效率。

小开

它还取决于使用，哈希允许定位精确匹配。如果您想查询一个范围，那么 BST 是选择。假设你有很多数据 e1，e2，e3... ..。嗯。

使用哈希表，您可以在常量时间内定位任何元素。

如果希望查找大于 e41、小于 e8的范围值，BST 可以快速查找。

关键是用来避免冲突的散列函数。当然，我们不能完全避免碰撞，在这种情况下，我们诉诸链接或其他方法。这使得检索在最坏的情况下不再是固定的时间。

一旦填满，哈希表就必须增加桶的大小并再次复制所有元素。这是一个额外的费用没有超过英国夏令时。

小开

其他人没有指出的一个优势是，二叉查找树可以让你高效地进行范围搜索。

为了说明我的想法，我想做一个极端的例子。假设您想获取键在0到5000之间的所有元素。实际上只有一个这样的元素和其他10000个键不在范围内的元素。BST 可以相当有效地进行范围搜索，因为它不搜索不可能有答案的子树。

While, how can you do range searches in a hash table? You either need to iterate every bucket space, which is O(n), or you have to look for whether each of 1,2,3,4... up to 5000 exists. (如果0到5000之间的键是一个无限集合呢? 例如键可以是小数)

小开

哈希表不适合索引。当您搜索一个范围时，BST 更好。这就是为什么大多数数据库索引使用 B + 树而不是哈希表的原因

小开

来自破解编码访谈，第6版

我们可以用一个平衡二叉查找树(BST)来实现哈希表。这给了我们一个 O (log n)查找时间。这样做的好处是可能使用更少的空间，因为我们不再分配大型数组。我们还可以按顺序迭代键，这有时很有用。

小开

散列表是一个固定的关联数组。因此，您的输入值数组将被汇集到 bucket 中。在开放式寻址方案中，有一个指向桶的指针，每次向桶中添加新值时，都会发现桶中哪里有空闲空间。有几种方法可以做到这一点-您从桶的开头开始，每次递增指针，并测试它是否被占用。这叫做线性探测。然后，您可以执行像 add 这样的二进制搜索，在这种情况下，每次搜索空闲空间时，都要将 bucket 的开头和向上或向下的差值加倍。这叫二次探测。好的。现在这两种方法的问题是，如果 bucket 溢出到下一个 bucket 地址，那么您需要-

Double each buckets size- malloc(N buckets)/change the hash function- 所需时间: 取决于 malloc 的实现
将每个早期的 bucket 数据传输/复制到新的 bucket 数据中。这是一个 O (N)操作，其中 N 表示整个数据

好的。但是如果你使用一个链接列表，应该不会有这样的问题，对吗？是的，在链表中你不会有这个问题。考虑到每个 bucket 都是从一个链表开始的，如果你的 bucket 中有100个元素，那么你需要遍历这100个元素来到达 linkedlist 的末尾，因此 List.add (Element E)需要花费时间来-

Hash the element to a bucket- Normal as in all implementations
Take time to find the last element in said bucket- O(N) operation.

Linkedlist 实现的优点是不需要内存分配操作和所有存储桶的 O (N)传输/复制，就像打开寻址实现那样。

因此，最小化 O (N)操作的方法是将实现转换为一个二叉查找树，其中 find 操作为 O (log (N)) ，然后根据元素的值在其位置添加元素。BST 的附加特性是它来排序！

小开

如果键上定义了一些总顺序(键是可比较的) ，并且您希望保留顺序信息，那么二进制搜索树是实现 dictionary 的好选择。

由于 BST 保留了订单信息，因此它为您提供了四个额外的动态集操作，这些操作无法使用哈希表(有效地)执行。这些行动包括:

最大值
至少
继任者
前任

像每个 BST 操作一样，所有这些操作的时间复杂度都是 O (H)。此外，所有存储的密钥在 BST 中保持排序，因此只需按顺序遍历树就可以获得已排序的密钥序列。

总而言之，如果您想要的只是操作插入、删除和删除，那么哈希表在性能上是无与伦比的(大多数情况下)。但是如果你想要上面列出的任何或所有的操作，你应该使用一个 BST，最好是一个自我平衡的 BST。

小开

Binary search trees can be faster when used with string keys. Especially when strings are long.

二进制搜索树使用小于或大于的比较，这对于字符串来说是快速的(当它们不相等时)。因此，当找不到字符串时，BST 可以快速响应。当它被发现时，它将只需要做一个完整的比较。

在哈希表里。您需要计算字符串的哈希值，这意味着您需要至少遍历所有字节一次才能计算哈希值。然后，当找到匹配的条目时。

小开

海湾合作委员会 C + + 案例研究

让我们也从世界上最重要的实现之一获得一些见解。正如我们将看到的，它实际上完全符合理论！

如在 C + + 中 STL 集的底层数据结构是什么？所示，在海湾合作委员会6.4:

std::map使用 BST
std::unordered_map使用散列表

因此，这已经指出了一个事实，即您不能有效地横向散列表，这可能是 BST 的主要优点。

然后，我还对散列映射和 BST 以及堆积与二叉查找树(BST)的堆的插入时间进行了基准测试，这清楚地突出了关键的性能特征:

BST 插入为 O (log) ，散列表为 O (1)。在这个特定的实现中，散列表几乎总是比 BST 快，即使对于相对较小的尺寸也是如此
hashmap, although much faster in general, has some extremely slow insertions visible as single points in the zoomed out plot.

当实现决定是时候增加它的大小，并且需要将它复制到一个更大的时候，就会发生这种情况。

更准确地说，这是因为只有它的分摊的复杂性是 O (1) ，而不是最坏的情况，在数组复制过程中实际上是 O (n)。

这可能使得散列映射不适合某些实时应用程序，因为在这些应用程序中需要更强的时间保证。