119

与哈希表相比，二叉搜索树的优势是什么？

哈希表可以在 Theta(1) 时间内查找任何元素，并且添加元素同样容易......但我不确定反过来的优势。

4

18 回答 18

143

没有人指出的一个优点是二叉搜索树允许您有效地进行范围搜索。

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

同时，如何在哈希表中进行范围搜索？您要么需要迭代每个存储桶空间，即 O(n)，要么必须查找 1、2、3、4 中的每一个是否存在，最多 5000 个。（0 到 5000 之间的键是无限集呢？例如键可以是小数）

于 2013-11-11T00:05:27.403 回答
102

请记住，二叉搜索树（基于引用）具有内存效率。他们不会保留比他们需要的更多的内存。

例如，如果哈希函数有一个 range R(h) = 0...100，那么您需要分配一个包含 100 个（指向）元素的数组，即使您只是对 20 个元素进行哈希处理。如果您要使用二叉搜索树来存储相同的信息，您将只分配所需的空间以及有关链接的一些元数据。

于 2010-11-08T22:11:38.933 回答
81

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

于 2010-11-08T22:11:13.650 回答
56

除了所有其他好评：

与二叉树相比，哈希表通常具有更好的缓存行为，需要更少的内存读取。对于哈希表，您通常只需要进行一次读取，然后才能访问保存数据的引用。二叉树，如果它是一个平衡的变体，需要按k * lg(n)顺序的内存读取某个常数 k。

另一方面，如果敌人知道您的散列函数，则敌人可以强制您的散列表进行碰撞，从而极大地影响其性能。解决方法是从一个族中随机选择散列函数，但 BST 没有这个缺点。此外，当哈希表压力增长过大时，您通常倾向于扩大和重新分配哈希表，这可能是一项昂贵的操作。BST 在这里的行为更简单，不会突然分配大量数据并进行重新散列操作。

树往往是最终的平均数据结构。它们可以充当列表，可以轻松拆分以进行并行操作，具有O(lg n)顺序的快速删除、插入和查找。他们没有做得特别好，但他们也没有任何过分恶劣的行为。

最后，与哈希表相比，BST 更容易在（纯）函数式语言中实现，并且它们不需要实现破坏性更新（上面 Pascal 的持久性论点）。

于 2010-11-09T00:01:05.550 回答
31

与哈希表相比，二叉树的主要优点是二叉树为您提供了两个使用哈希表无法（轻松、快速）执行的额外操作

  • 找到最接近（不一定等于）某个任意键值（或最接近上方/下方）的元素

  • 按排序顺序遍历树的内容

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

于 2010-11-08T22:25:25.240 回答
16

（平衡的）二叉搜索树还有一个优点是它的渐近复杂度实际上是一个上限，而哈希表的“恒定”时间是摊销时间：如果你有一个不合适的哈希函数，你最终可能会降级为线性时间，而不是常数。

于 2010-11-08T22:29:43.163 回答
11

哈希表在首次创建时会占用更多空间 - 它将为尚未插入的元素提供可用插槽（无论它们是否曾经插入过），二叉搜索树将仅与它需要的一样大是。此外，当哈希表需要更多空间时，扩展到另一个结构可能会很耗时，但这可能取决于实现。

于 2010-11-08T22:11:14.667 回答
10

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

遍历哈希表的条目没有多大意义，因为它们都分散在内存中。

于 2010-11-08T22:13:02.943 回答
8

二叉搜索树可以使用持久接口实现，其中返回新树但旧树继续存在。仔细实施后，新旧树共享它们的大部分节点。您无法使用标准哈希表执行此操作。

于 2010-11-08T22:19:18.773 回答
6

BST 还提供了 O(logn) 时间内的“findPredecessor”和“findSuccessor”操作（查找下一个最小和下一个最大的元素），这也可能是非常方便的操作。Hash Table 无法提供那个时间效率。

于 2012-09-20T17:55:07.520 回答
6

从破解编码采访，第 6 版

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

于 2016-05-29T18:47:32.967 回答
2

GCC C++ 案例研究

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

如C++ 中 STL 集的底层数据结构是什么？，在 GCC 6.4 中：

  • std::map使用 BST
  • std::unordered_map使用哈希图

因此，这已经指出了一个事实，即您无法有效地遍历哈希图，这可能是 BST 的主要优势。

然后，我还在Heap vs Binary Search Tree (BST)中对 hash map vs BST vs heap 的插入时间进行了基准测试，这清楚地突出了关键性能特征：

  • BST 插入是 O(log)，hashmap 是 O(1)。在这个特定的实现中，hashmap 几乎总是比 BST 快，即使是相对较小的尺寸

  • hashmap 虽然总体上要快得多，但在缩小的图中以单点形式显示了一些极慢的插入。

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

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

    这可能会使哈希图不适用于某些需要更强时间保证的实时应用程序。

在此处输入图像描述

有关的：

于 2021-01-06T09:18:28.373 回答
1

如果要以排序方式访问数据，则必须与哈希表并行维护排序列表。一个很好的例子是 .Net 中的字典。（参见http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx）。

这不仅会减慢插入速度，而且会比 b-tree 消耗更多的内存。

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

于 2010-11-08T22:34:21.593 回答
1

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

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

如果要查找大于 e41 且小于 e8 的范围值，BST 可以快速找到。

关键是用于避免冲突的哈希函数。当然，我们不能完全避免碰撞，在这种情况下，我们会求助于链接或其他方法。这使得检索在最坏的情况下不再是恒定的时间。

一旦填满，哈希表必须增加其存储桶大小并再次复制所有元素。这是 BST 不存在的额外费用。

于 2013-01-29T14:54:47.713 回答
1

如果在键上定义了一些总顺序（键是可比较的）并且您希望保留顺序信息，则二叉搜索树是实现字典的不错选择。

由于 BST 保留了订单信息，它为您提供了四个无法使用哈希表（有效地）执行的附加动态集操作。这些操作是：

  1. 最大
  2. 最低限度
  3. 接班人
  4. 前任

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

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

于 2018-05-19T16:46:19.280 回答
0

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

于 2015-04-05T17:34:31.977 回答
0

与字符串键一起使用时，二叉搜索树可以更快。特别是当字符串很长时。

二叉搜索树使用较小/较大的比较，这对于字符串来说很快（当它们不相等时）。因此，当找不到字符串时，BST 可以快速回答。当它被发现时，它只需要做一次完整的比较。

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

于 2018-10-13T11:32:16.617 回答
0

hashmap 是一个集合关联数组。因此，您的输入值数组被汇集到存储桶中。在开放式寻址方案中，您有一个指向存储桶的指针，每次您向存储桶添加新值时，您都会发现存储桶中的哪些位置有空闲空间。有几种方法可以做到这一点——你从桶的开头开始，每次都增加指针并测试它是否被占用。这称为线性探测。然后，您可以进行像 add 一样的二分搜索，在每次搜索可用空间时，将存储桶的开头与加倍或后退之间的差加倍。这称为二次探测。好的。现在这两种方法的问题是，如果桶溢出到下一个桶地址，那么你需要 -

  1. 将每个桶大小加倍- malloc(N 个桶)/更改哈希函数- 所需时间：取决于 malloc 实现
  2. 将每个较早的存储桶数据传输/复制到新的存储桶数据中。这是一个 O(N) 操作，其中 N 表示整个数据

好的。但是如果你使用链表就不应该有这样的问题，对吧？是的，在链表中你没有这个问题。考虑到每个桶都以链表开头，如果桶中有 100 个元素，则需要遍历这 100 个元素才能到达链表的末尾，因此 List.add(Element E) 将需要时间-

  1. 将元素散列到一个桶中——在所有实现中都是正常的
  2. 花时间找到所述桶-O（N）操作中的最后一个元素。

链表实现的优点是您不需要像开放寻址实现那样的内存分配操作和所有桶的 O(N) 传输/复制。

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

于 2017-08-20T23:24:40.897 回答