19

我很想知道使用自平衡树技术存储项目而不是使用哈希表的原因是什么。

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

我看到对于少量值，哈希函数会增加成本，但我总是可以将哈希函数与键一起保存以加快查找速度。

我知道哈希表比直接实现红黑树更难实现，但在实际实现中，难道不想多花点功夫吗？

我看到对于哈希表，发生冲突是正常的，但是对于允许将键保存在哈希表本身中的双哈希等开放寻址技术，问题并没有减少到不倾斜的效果对于这样的实现，走向红黑树？

我很好奇我是否完全遗漏了哈希表的一个缺点，它仍然使红黑树在实际应用程序（如文件系统等）中非常可行的数据结构。

4

6 回答 6

21

这是我能想到的：

  1. 有些数据不能被散列（或者散列太昂贵），因此不能存储在散列表中。
  2. 树按照您需要的顺序（排序）保存数据，而不是插入顺序。即使您通过它运行一个链表，您也不能（有效地）使用哈希表来做到这一点。
  3. 树具有更好的最坏情况性能
于 2010-07-16T13:55:02.607 回答
6

存储分配是另一个考虑因素。每次填充散列表中的所有存储桶时，都需要分配新的存储空间并重新散列所有内容。如果您提前知道数据的大小，则可以避免这种情况。另一方面，平衡树根本不会遇到这个问题。

于 2010-07-16T14:17:43.253 回答
2

在我看来，自平衡树作为学术主题非常有效。而且我不知道任何可以被称为“红黑树的直接实现”的东西。

在现实世界中，记忆墙使它们的效率远低于纸上的。

考虑到这一点，哈希表是不错的选择，特别是如果您不以学术风格练习它们（忘记表大小限制，您会神奇地解决表调整大小问题和几乎所有冲突问题）。

一句话：保持简单。如果这对您来说很简单，那么这对您的计算机来说也很简单。

于 2010-07-16T13:45:19.353 回答
2

只是想添加：

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

  • 与哈希表相比，树通常具有更高的内存效率，并且在无需对输入键的分布和可能的冲突等进行任何分析的情况下实现起来也更简单。

于 2011-07-20T22:50:14.177 回答
1

我能想到的几个原因：

  1. 树是动态的（空间复杂度为 N），而哈希表通常实现为固定大小的数组，这意味着它们通常会以 K 大小进行初始化，其中 K > N，因此即使您在一个hashmap，你可能还有 100 个占用内存的空槽。这样做的另一个效果是：

  2. 增加基于数组的哈希表的大小是昂贵的（O（N）平均时间，O（N log N）最坏情况），而树可以在恒定时间（O（1））+（定位插入点的时间(O(log N))

  3. 树中的元素可以按排序顺序收集（使用 ex: in-order-traversal）。因此，您经常会得到一个排序列表，作为树木的免费福利。
  4. 与 hashmap 相比，树可以具有更好的最坏情况性能，具体取决于 hashmap 的实现方式（例如：带有链接的 hashmap 将有 O(N) 最坏情况，而自平衡树可以保证 O(log N) 最坏情况操作）。

自平衡树和哈希图在最好的最坏情况下（假设哈希图确实处理冲突）的最坏情况效率为 O(log N)，但哈希图可以具有更好的平均情况性能（通常接近 O (1))，而树将有一个常数 O(log N)。这是因为即使你的 hashmap 可以在 O(1) 中找到插入索引，它也必须考虑 hash colissions（多个元素散列到相同的数组索引），因此在最好的情况下会降级为自平衡树（如hashmap的Java实现），即hashmap中的每个元素都可以实现为一棵自平衡树，存储所有已经散列到给定数组单元格的元素。

于 2018-04-04T09:16:03.540 回答
0

我认为如果您想查询一系列键而不是一个键，自平衡树结构将比哈希表结构执行得更好。

于 2014-03-13T14:29:09.630 回答