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

Question

二进制搜索树在哈希表上的优点是什么？

哈希表可以查找theta（1）时间中的任何元素，并且添加一个元素同样容易....但是我不确定相反的优势。

Answer 1

请记住，二进制搜索树（基于参考）是记忆效率的。他们没有保留比需要更多的记忆。

例如，如果哈希函数具有范围 R(h) = 0...100, ，然后您需要分配100个（指针）元素的数组，即使您只是哈希20元素。如果您要使用二进制搜索树来存储相同的信息，则只会根据需要分配尽可能多的空间，以及有关链接的一些元数据。

Answer 2

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

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

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

Answer 3

二进制树的一个“优势”是，它可能会经过列出所有元素的顺序。哈希表并非不可能，但不是正常的操作，即在哈希结构中设计。

Answer 4

除了所有其他好评论：

与二进制树相比，哈希表通常具有更好的缓存行为，需要更少的内存读取。对于哈希表，通常只在访问持有数据的参考之前就只会产生单个读取。二进制树，如果是平衡的变体，则需要按顺序 k * lg（n） 记忆读取一些常数k。

另一方面，如果敌人知道您的哈希功能，那么敌人可以强制执行您的哈希桌子来碰撞，从而极大地阻碍了其性能。解决方法是从一个家庭中随机选择函数，但BST没有这种不利地位。另外，当哈希表压力增长太多时，您通常会倾向于放大和重新分配哈希表，这可能是一个昂贵的操作。 BST在这里具有更简单的行为，并且不会突然分配大量数据并进行重新进行操作。

树木往往是最终的平均数据结构。它们可以充当列表，可以轻松拆分以进行并行操作，快速删除，插入和查找 o（lg n）. 。他们什么都不做 特别 好吧，但是他们的行为也没有过多。

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

Answer 5

二进制树在哈希表上的主要优点是，二进制树为您提供了两个其他操作（轻松，快速）使用哈希表提供的操作

• 找到最接近（不一定等于）一些任意钥匙值的元素（或以上/下方最接近）

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

两者是连接的 - 二进制树以排序顺序保持其内容，因此需要分类顺序的事情很容易做到。

Answer 6

（平衡的）二进制搜索树还具有一个优势，即其渐近复杂性实际上是上限，而哈希表的“恒定”时间是摊销时间：如果您具有不合适的哈希功能，则最终可能会退化为线性时间，而不是恒定。

Answer 7

首次创建时，标志性将占用更多空间 - 它将为尚待插入的元素提供可用的插槽（无论它们是否曾经插入），二进制搜索树只会尽可能大是。另外，当台式桌子需要更多空间时，扩展到另一个结构 可以 耗时，但这可能取决于实施。

Answer 8

可以用 执着的 接口，返回一棵新树，但旧树继续存在。仔细实施的新树木分享了大多数节点。您不能使用标准哈希表来执行此操作。

Answer 9

二进制树的搜索和插入较慢，但具有infix遍历的非常好的功能，这实际上意味着您可以按顺序通过树的节点迭代。

通过哈希表的条目进行迭代，因为它们都散布在记忆中，这是没有多大意义的。

Answer 10

BST还提供了O（logN）时间中的“ Findpredecoremer”和“ FindSuccessor”操作（查找下一个最小和下一个最大的元素），这也可能是非常方便的操作。哈希表无法在此时间效率下提供。

Answer 11

从 破解编码访谈，第六版

我们可以使用平衡的二进制搜索树（BST）实现哈希表。这给了我们O（log n）查找时间。由于我们不再分配大型阵列，因此可能会使用更少的空间。我们还可以按键迭代键，有时可能会很有用。

Answer 12

如果要以分类的方式访问数据，则必须与哈希表平行维护分类列表。一个很好的例子是.net中的字典。 （看 http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx).

这不仅具有放缓的插入物的副作用，而且比B-Tree所消耗的内存量更大。

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

Answer 13

这也取决于用途，哈希允许找到精确的匹配。如果您想查询一个范围，那么BST就是选择。假设您有很多数据E1，E2，E3 ..... en。

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

如果您想找到大于E41且小于E8的范围值，则BST可以很快找到。

关键是用于避免碰撞的哈希功能。当然，我们不能完全避免发生碰撞，在这种情况下，我们诉诸于链接或其他方法。这使得在最坏情况下不再恒定时间。

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

Answer 14

hashmap是一个集合的关联阵列。因此，您的输入值数组被汇总到存储桶中。在一个开放的寻址方案中，您有一个指向桶的指针，每次在存储桶中添加新值时，都会在存储桶中找到自由空间的位置。有几种方法可以做到这一点 - 您从桶的开头开始，每次都会递增指针并测试其是否占据。这称为线性探测。然后，您可以进行二进制搜索，例如添加，每次搜索自由空间时，您可以将水桶开头和向后加倍或向下加倍的差异加倍。这称为二次探测。好的。现在，这两种方法中的问题是，如果存储桶溢出到下一个存储桶地址，那么您需要 -

1. 每个存储桶尺寸 - malloc（n个存储桶）/更改所需的哈希功能时间：取决于malloc实现
2. 将/复制每个早期存储桶数据传输到新的存储桶数据中。这是一个O（n）操作，其中n表示整个数据

好的。但是，如果您使用linkedlist，那应该不是问题吗？是的，在链接列表中，您没有这个问题。考虑每个存储桶以链接列表开头，如果您的存储桶中有100个元素，则需要您穿越这100个元素才能到达linkedlist的末尾，因此list.add（element e）将花费时间 -

1. 哈希元素达到一个平常的元素，如所有实现
2. 花点时间在上述铲斗O（n）操作中找到最后一个元素。

LinkedList实现的优点是，您不需要内存分配操作，而O（n）的转移/副本如开放式地址实现的情况。

因此，最小化O（n）操作的方法是将实现转换为二进制搜索树的实现，其中查找操作为O（log（log（n）），您可以根据其值将元素添加到其位置。 BST的附加功能是它已排序！

Answer 15

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

Answer 16

如果键在其上定义了一些总订单（键），并且您想保留订单信息，则二进制搜索树是实现字典的理想选择。

当BST保留订单信息时，它为您提供了四个其他动态设置操作，这些操作无法（有效）使用哈希表执行。这些操作是：

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

所有这些操作都像每个BST操作一样具有O（H）的时间复杂性。此外，所有存储的密钥都保留在BST中，从而使您仅通过按顺序遍历树即可获得按键的排序序列。

总而言之，如果您想要的只是操作插入，删除和删除，则哈希表的性能是无与伦比的。但是，如果您想要上面列出的任何或所有操作，则应使用BST，最好是自我平衡的BST。

Answer 17

与字符串键一起使用时，二进制搜索树可以更快。尤其是弦长的时候。

二进制搜索树使用比较较小/更大的比较，这对于字符串而言是快速的（当它们不相等时）。因此，当找不到字符串时，BST可以快速回答。当发现它时，只需进行一个完整的比较即可。

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

Answer 18

哈希表的主要优点是它几乎在〜= o（1）中完成所有操作。它非常易于理解和实施。它确实有效地解决了许多“面试问题”。因此，如果您想破解编码面试，请用哈希桌结交最好的朋友;-)