logo标签列表

哈希表与自平衡搜索树

hashtablered-black-tree
20

我很好奇，有什么理由可以超越使用哈希表而使用自平衡树技术来存储项。

我知道哈希表无法维护插入顺序，但我总是可以在顶部使用链表来存储插入顺序序列。

我知道对于少量的值来说，哈希函数有额外的成本，但我总是可以将哈希函数与键一起保存以进行更快的查找。

我了解到，相对于直接实现红黑树，哈希表的实现难度更大，但在实际实现中，人们会愿意为此付出更多的代价吗？

我知道使用哈希表时发生冲突是正常的，但使用双重散列等开放地址技术可以将键保存在哈希表本身中，这样问题是否已经减少到不将优势倾向于红黑树的程度了呢？

我很好奇，是否严格地说，我错过了哈希表的缺点，这些缺点使得红黑树在实际应用（如文件系统等）中仍然是可行的数据结构。

2
两种数据结构都有优缺点。你应该选择更适合你的问题的那一个。 - Nick Dandoulakis
6个回答
21

以下是我能想到的：

  1. 有一些数据无法被散列（或者散列成本太高），因此无法存储在哈希表中。
  2. 树按你需要的顺序（排序）保存数据，而不是插入顺序。即使你通过哈希表运行链表，也无法有效地实现这一点。
  3. 在最坏情况下，树的性能更好。
  1. 如果您无法生成哈希键，那么如何生成一个键来确定节点在树中的位置？如果您可以为节点定位生成一个键，为什么不能将其用作哈希键呢？
  2. 为什么您不能使用哈希表+链表有效地完成这项任务？您能提供更多解释吗？请记住，链表本质上只是针对排序进行了优化的树。
  3. 树的最佳情况是log(N)。哈希始终是常数。碰撞对两种结构都有相同的影响。那么树如何具有更好的最坏情况性能呢？
 - Jake
4
1- 通过比较元素。拥有某种顺序并不意味着可以对其进行哈希处理。 2- 因为。 3- 在树结构中不存在碰撞的情况。 - unbeli
  1. 你正在比较的项目是关键。所有二进制数据都可以通过某种方法进行哈希处理，计算机中的所有数据都是二进制数据。如果键很大，那么比较树的比较函数可能会变得昂贵，但这可能会对树的比较函数产生相同的影响。
  2. 搜索树具有有序节点。只有在列表具有一组用于对元素排序的键的情况下，才能对列表进行排序。如果两个节点具有相同的键，则会发生冲突。
 - Jake
2
1- 不正确。3- 关于键的不正确之处：对于搜索树，您不需要任何键。如果插入一个与现有条目相等的条目，则与哈希冲突相反，不会影响性能。理解原因是您的家庭作业。 - unbeli
7

存储分配是另一个需要考虑的问题。每当哈希表中的所有桶都被填满时，您需要分配新的存储空间并重新哈希所有内容。如果您事先知道数据的大小，可以避免这种情况。另一方面，平衡树则完全不会受到此问题的影响。

1
但是该操作的分摊成本仍然为O（1），所以您真的认为这是一个劣势吗？ - Vaibhav Bajpai
3
大多数情况下，可能不需要。但在实时应用中，是的。 - Odrade
3

我想补充一下：

  • 平衡二叉树在获取数据时具有可预测的时间 [log n]，与数据类型无关。在估计应用程序的响应时间时，这对于你的应用程序可能非常重要。[哈希表的响应时间可能是不可预测的]。请记住，在大多数常见用例中，对于较小的n，内存查找的性能差异几乎没有关系，系统的瓶颈将在其他地方，有时您只想使系统更简单易于调试和分析。

  • 与哈希表相比，树通常更节省内存，并且更容易实现，无需分析输入密钥的分布和可能的冲突等。

2
在我看来，自平衡树作为学术主题是非常好的。我不知道有什么可以被称为“红黑树的直接实现”的东西。
在现实世界中，内存瓶颈使它们远不如论文中那样高效。
考虑到这一点，哈希表是不错的替代方案，特别是如果你不按学术风格来使用它们（忘记表大小限制，你就可以神奇地解决表调整问题和几乎所有冲突问题）。
总之：保持简单。如果对你来说很简单，那对你的计算机也是很简单的。
2
你能解释一下如何“忘记表尺寸限制”吗？你只是建议我们忽略它，还是有其他意思？ - Odrade
3
你认为C++标准库的实现算不算学术话题？Java和.NET容器呢？ 你应该知道，std::map大多数情况下被实现为平衡二叉搜索树；GNU libstdc++使用红黑树来实现std::map。 - Fingolfin
1
保持简单。如果对你来说很简单，那么对你的计算机也是很简单的。这并不是一个很好的建议，想想斐波那契堆——高度复杂但非常高效。同样适用于例如SSS*游戏树搜索或Thorup路径查找... - PawelP
1
@Odrade -- 我认为他的意思是让你的表格尽可能大，这样碰撞的可能性就会很小，并且不要担心它有多满或多空（调整大小以节省内存）。 - Alex Leibowitz
1
我认为，如果你想查询一段键而不是一个键，自平衡树结构会比哈希表结构更好。
这听起来很像是个人观点。你有任何数据/参考资料来支持你的说法吗？ - Floris
1
在哈希表中查询一系列键可能意味着需要确切地知道哪些位置有键，哪些位置没有。您需要为您认为在查询间隔内的每个可能的键重复哈希操作。使用树，您只需定位间隔的开头，然后按顺序遍历树，直到查询间隔的末尾即可。 - Cesar
1
我能想到的几个原因如下：
  1. 树是动态的（空间复杂度为N），而哈希表通常实现为数组，其大小固定，这意味着它们经常会被初始化为K大小，其中K > N，因此即使您在哈希映射中只有1个元素，您可能仍然有100个空插槽占用内存。这样做的另一个影响是：
  2. 增加基于数组的哈希表的大小成本高昂（平均时间为O（N），最坏情况为O（N log N）），而树可以在常数时间（O（1））内增长+（定位插入点的时间（O（log N））
  3. 树中的元素可以按排序顺序收集（使用例如：中序遍历）。因此，您通常会获得一份免费奖励的排序列表。
  4. 根据哈希表的实现方式，树可以具有更好的最坏情况性能（例如：使用链接的哈希表将具有O（N）的最坏情况，而自平衡树可以保证所有操作的O（log N）最坏情况）。
自平衡树和哈希表在最坏情况下的效率都是O(log N)，但哈希表的平均情况性能更好（通常接近于O(1)），而树的复杂度为O(log N)。这是因为虽然哈希表可以在O(1)时间内定位插入索引，但它必须考虑哈希冲突（多个元素散列到相同的数组索引），因此在最好的情况下会降级为自平衡树（如Java实现的哈希表），即哈希表中的每个元素都可以实现为一个自平衡树，存储所有已散列到给定数组单元格的元素。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接