二叉树与链表与哈希表

我在做一个项目的符号表。我想知道人们对存储和创建符号表的各种方法的优缺点有什么看法。

我已经做了相当多的搜索，最常见的推荐是二叉树、链表或哈希表。以上所有方法的优点和缺点是什么？(使用 c + +)

87946 次浏览
小开

当然，这取决于几个因素。我想说，链表是正确的，因为它几乎没有合适的属性作为一个符号表工作。如果您已经有一个二进制树，并且不需要花费时间编写和调试它，那么二进制树也许可以工作。我的选择将是一个哈希表，我认为这或多或少是这个目的的默认值。

小开

这个问题 会遍历 C # 中的不同容器，但是它们在您使用的任何语言中都是相似的。

小开

应用这些数据结构之间的标准权衡。

  • 二叉树
    • 要实现的中等复杂性(假设您无法从库中获得它们)
    • 插入是 O (logN)
    • 查找是 O (logN)
  • 链表(未排序)
    • 实现的复杂性低
    • 插入是 O (1)
    • 查找是 O (N)
  • 哈希表
    • 实现的高度复杂性
    • 插入平均为 O (1)
    • 查找平均为 O (1)
小开
最佳答案

您的用例可能是“插入数据一次(例如，应用程序启动) ，然后执行大量的读操作，但是如果有额外的插入，则很少执行”。

因此，您需要使用一种快速的算法来查找所需的信息。

因此，我认为 HashTable 是最适合使用的算法，因为它只是生成关键对象的散列，并使用它来访问目标数据——它是 O (1)。其他的是 O (N)(大小为 N 的链表——你必须一次迭代一个链表，平均 N/2次)和 O (log N)(二叉树——你在每次迭代中将搜索空间减半——只有在树是平衡的情况下，所以这取决于你的实现，一个不平衡的树可能会有明显更差的性能)。

只需要确保 HashTable 中有足够的空间(桶)来存放数据(参考 Soraz 对这篇文章的评论)。大多数框架实现(Java，。NET 等)的特性，您不必担心实现的问题。

你在大学里学过数据结构和算法吗？

小开

除非您希望您的符号表很小，否则我应该避开链表。一个包含1000个条目的列表平均需要500次迭代才能找到其中的任何条目。

二叉树可以更快，只要它是平衡的。如果你持久化内容，序列化的表单很可能会被排序，当它被重新加载时，结果树将完全不平衡，它的行为将与链表相同——因为它基本上已经变成了这样。平衡树算法解决了这个问题，但是使整个过程更加复杂。

散列表(只要选择合适的散列算法)看起来是最佳解决方案。您没有提到您的环境，但是几乎所有的现代语言都内置了一个散列表。

小开

有几件事要注意。

  • 如果二叉树是 平衡，那么二叉树只有 O (logn)查找和插入复杂度。如果您的符号是以一种相当随机的方式插入的，那么这应该不是一个问题。如果它们是按顺序插入的，那么您将构建一个链表。(对于您的特定应用程序，它们不应该按任何类型的顺序排列，所以应该没问题。)如果有一个机会，符号将太有序，一个 红-黑树是一个更好的选择。

  • 散列表提供 O (1)平均插入和查找复杂度，但这里也有一个警告。如果您的散列函数不好(我的意思是 真的不好) ，您可能会在这里建立一个链表。但是，任何合理的字符串散列函数都应该这样做，所以这个警告实际上只是为了确保您意识到它可能发生。您应该能够测试散列函数在预期的输入范围内没有多少冲突，这样就没问题了。另一个小缺点是，如果使用的是固定大小的哈希表。大多数哈希表实现在达到一定大小时会增长(更精确地说，是加载因子，详见 给你)。这是为了避免将一百万个符号插入到十个桶中时出现的问题。这只会导致10个链表，平均大小为100,000。

  • 如果我有一个非常短的符号表，我只会使用一个链表。这是最容易实现的，但是链表的最佳情况性能是其他两个选项的最差情况性能。

小开

每个人似乎都忘记了，对于小 Ns，IE 表中的少量符号，链表可以比哈希表快得多，尽管理论上它的渐近复杂度确实更高。

派克关于 C 语言编程的笔记中有一句名言: “规则3。当 n 很小时，花哨的算法会很慢，而且 n 通常很小。花哨的算法有很大的常量。在你知道 n 经常变大之前，不要想太多。”http://www.lysator.liu.se/c/pikestyle.html

我不能从你的文章中判断你是否要处理一个小 N，但是请记住，对于大 N 来说最好的算法对于小 N 来说并不一定是好的。

小开

我喜欢比尔的回答，但它并不能真正综合事物。

来自三个选择:

链表查找(O (n))中的项相对较慢。因此，如果表中有 很多项，或者要进行大量查找，那么它们不是最佳选择。然而，它们很容易构建，也很容易编写。如果表很小，并且/或者在构建之后只对其进行一次小扫描，那么这可能是您的选择。

散列表的速度非常快。然而，为了让它正常工作，您必须为您的输入选择一个好的哈希表，并且您必须选择一个足够大的表来容纳所有内容，而不会有大量的哈希冲突。这意味着你必须知道输入的大小和数量。如果您搞砸了这一点，您最终将得到一组非常昂贵和复杂的链表。我要说的是，除非你提前知道大致的表会有多大，否则不要使用哈希表。这与你“接受”的答案不一致。对不起。

那就只剩下树了。你可以选择平衡还是不平衡。通过研究 C 和 Fortran 代码中的这个问题，我发现符号表的输入往往是足够随机的，如果不平衡树，只会损失一两个树级。考虑到平衡树插入元素的速度较慢，实现起来也较困难，我不会为它们操心。但是，如果您已经访问了调试好的组件库(例如: C + + 的 STL) ，那么您可以继续使用平衡树。

小开

听起来下面这些可能都是真的:

  • 你的钥匙是绳子。
  • 插入只完成一次。
  • 经常进行查找。
  • 键值对的数量相对较少(比如，少于一个 K 左右)。

如果是这样，您可以考虑在这些其他结构中选择一个排序列表。在执行插入操作时，这种方法的性能会比其他方法差，因为在插入操作中，排序列表是 O (N) ，而对于链表或散列表，排序列表是 O (1) ，对于平衡二叉搜索树，排序列表是 O (log2N)。但是排序列表中的查找可能比其他任何结构都要快(我将在稍后解释这一点) ，因此您可能会占据上风。另外，如果一次执行所有插入(或者在所有插入完成之前不需要查找) ，那么可以简化对 O (1)的插入，并在最后进行一次快得多的排序。更重要的是，排序列表比其他任何结构使用更少的内存，但是这种情况发生的唯一可能的方式是您有许多小列表。如果您有一个或几个大列表，那么散列表的性能很可能优于排序列表。

为什么使用排序列表查找可能更快？很明显，它比链表快，后者的 O (N)查找时间。对于二叉树，只有当树保持完全平衡时，查找才保持 O (log2N)。保持树的平衡(例如，红-黑)增加了复杂性和插入时间。此外，对于链表和二进制树，每个元素都是一个单独分配的 1 节点，这意味着您将不得不取消引用指针，并可能跳转到可能存在很大差异的内存地址，从而增加缓存丢失的几率。

至于散列表，您可能应该阅读 StackOverflow 上 其他问题的 有几个，但这里的主要兴趣点是:

  • 在最坏的情况下，哈希表可以退化为 O (N)。
  • 散列的成本是非零的，并且在某些实现中，它可能非常重要，特别是在字符串的情况下。
  • 与链表和二进制树一样，每个条目都是一个 节点，它存储的不仅仅是键和值，在某些实现中也是单独分配的，因此您将使用更多的内存，并增加缓存丢失的可能性。

当然，如果您真的关心这些数据结构中的任何一个将如何执行，那么您应该对它们进行测试。对于大多数常用语言来说，找到这些语言的良好实现应该不成问题。将您的一些真实数据抛向这些数据结构中的每一个，并看看哪一个执行得最好，这应该不会太困难。

  1. 实现可以预先分配节点数组，这将有助于解决缓存丢失问题。我在任何实际的链表或二进制树实现中都没有看到这种情况(当然，我并没有看到每一个链表或二进制树) ，尽管您当然可以自己滚动。不过，缓存丢失的可能性还是稍高一些，因为 节点对象必须比键/值对大。
小开

其他注释集中在添加/检索元素上，但是如果不考虑在整个集合中迭代所需的代码，这个讨论就不完整。这里的简短答案是，散列表需要更少的内存来迭代，但是树需要更少的时间。

对于哈希表，在(键，值)对上进行迭代的内存开销并不取决于表的容量或存储在表中的元素数量; 实际上，迭代只需要一个或两个索引变量。

对于树，所需的内存总是取决于树的大小。您可以在迭代时维护一个未访问节点队列，也可以向树中添加额外的指针，以便更容易地进行迭代(为了进行迭代，使树像链表一样) ，但无论哪种方式，您都必须为迭代分配额外的内存。

但在时机方面，情况恰恰相反。对于哈希表，迭代所需的时间取决于表的容量，而不是存储元素的数量。因此，一个以10% 的容量加载的表比一个具有相同元素的链表要花费大约10倍的时间来迭代！


提交答案