二进制搜索树优于哈希表的优点

Question

二进制搜索树比哈希表有什么优势？

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

Answer 1

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

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

虽然,如何在哈希表中进行范围搜索？您需要迭代每个存储区空间,即O(n),或者您必须查找1,2,3,4 ...高达5000中的每一个是否存在.(0到5000之间的键是无限集的？例如键可以是小数)

Answer 2

请记住,二进制搜索树(基于参考)是内存有效的.他们不会保留比他们需要更多的内存.

例如,如果散列函数有一个范围R(h) = 0...100,那么你需要分配一个100(指向)元素的数组,即使你只是散列20个元素.如果您使用二叉搜索树来存储相同的信息,则只需要分配所需的空间,以及一些关于链接的元数据.

Answer 3

二叉树的一个"优点"是可以遍历以按顺序列出所有元素.这对于哈希表来说并非不可能,但对于散列结构的设计而言,这不是正常操作.

Answer 4

除了所有其他好评:

与二叉树相比,散列表通常具有更好的缓存行为,需要更少的内存读取.对于哈希表,在访问包含数据的引用之前,通常只会发生一次读取.二叉树,如果它是一个平衡变量,需要某些常数k 的k*lg(n)内存读取顺序.

另一方面,如果敌人知道您的哈希函数,则敌人可以强制执行您的哈希表以进行冲突,从而严重影响其性能.解决方法是从一个系列中随机选择哈希函数,但是BST没有这个缺点.此外,当哈希表压力增长太多时,您经常倾向于放大并重新分配哈希表,这可能是一个昂贵的操作.BST在这里具有更简单的行为,并且不会突然分配大量数据并进行重复操作.

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

最后,与哈希表相比,BST在(纯)函数语言中更容易实现,并且它们不需要实现破坏性更新(上面的Pascal 的持久性参数).

Answer 5

二进制树优于哈希表的主要优点是二叉树为您提供了两个额外的操作,您无法使用哈希表(轻松,快速)执行这些操作

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

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

这两个是连接的 - 二叉树以排序的顺序保存其内容,因此需要排序顺序的事情很容易.

Answer 6

(平衡)二叉搜索树还具有以下优点:其渐近复杂度实际上是上限,而散列表的"常量"时间是分摊的时间:如果您具有不合适的散列函数,则最终可能降级为线性时间而不是常数.

Answer 7

哈希表在第一次创建时会占用更多空间 - 它将为尚未插入的元素提供可用的插槽(无论是否插入它们),二进制搜索树将只需要它所需的大小是.此外,当哈希表需要更多空间时,扩展到另一个结构可能非常耗时,但这可能取决于实现.

Answer 8

二进制搜索树可以使用持久性接口实现,其中返回新树但旧树继续存在.仔细实施,新旧树共享大部分节点.您不能使用标准哈希表执行此操作.

Answer 9

二叉树搜索和插入速度较慢,但​​具有中缀遍历的非常好的功能,这实际上意味着您可以按排序顺序遍历树的节点.

迭代哈希表的条目只是没有多大意义,因为它们都散布在内存中.

Answer 10

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

Answer 11

来自破解编码面试，第 6 版

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