72

我正在为我正在处理的项目构建符号表。我想知道人们对存储和创建符号表的各种方法的优缺点有何看法。

我进行了相当多的搜索，最常见的推荐是二叉树或链表或哈希表。以上所有的优点和缺点是什么？（在 C++ 中工作）

4

10 回答 10

76

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

  • 二叉树
    • 实现的中等复杂度（假设您无法从库中获取它们）
    • 插入是 O(logN)
    • 查找是 O(logN)
  • 链表（未排序）
    • 实现复杂度低
    • 插入是 O(1)
    • 查找是 O(N)
  • 哈希表
    • 实施复杂度高
    • 插入平均为 O(1)
    • 查找平均为 O(1)
于 2008-12-16T12:25:34.957 回答
48

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

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

因此，我认为 HashTable 是最适合使用的算法，因为它只是生成密钥对象的哈希并使用它来访问目标数据 - 它是 O(1)。其他是 O(N) （大小为 N 的链接列表 - 您必须一次遍历列表一个，平均 N/2 次）和 O(log N) （二叉树 - 您将搜索空间减半每次迭代 - 仅当树是平衡的，所以这取决于您的实现，不平衡的树的性能可能会明显变差）。

只需确保 HashTable 中有足够的空间（桶）用于您的数据（Re，Soraz 对这篇文章的评论）。大多数框架实现（Java、.NET 等）都具有您无需担心实现的质量。

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

于 2008-12-16T12:28:35.590 回答
43

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

Pike's Notes on Programming in C 中有一句名言：“规则 3。当 n 小时，花哨的算法很慢，而 n 通常很小。花哨的算法有很大的常数。直到你知道 n 经常会很大，别花里胡哨。” http://www.lysator.liu.se/c/pikestyle.html

我无法从您的帖子中判断您是否会处理小 N，但请始终记住，大 N 的最佳算法不一定适用于小 N。

于 2008-12-16T13:21:16.450 回答
8

听起来以下可能都是真的：

  • 你的键是字符串。
  • 插入完成一次。
  • 经常进行查找。
  • 键值对的数量相对较少（比方说，少于 K 左右）。

如果是这样，您可能会考虑对任何其他结构进行排序列表。这在插入过程中会比其他的表现更差，因为排序列表在插入时是 O(N)，而对于链表或哈希表是 O(1)，并且 O(log 2N) 平衡二叉树。但是在排序列表中查找可能比任何其他结构都快（我将很快解释这一点），因此您可能会排在首位。此外，如果您一次执行所有插入（或者在所有插入完成之前不需要查找），那么您可以将插入简化为 O(1) 并在最后进行更快的排序。更重要的是，排序列表使用的内存比任何其他结构都少，但唯一可能重要的是如果您有许多小列表。如果您有一个或几个大列表，那么哈希表可能会胜过排序列表。

为什么使用排序列表查找会更快？好吧，很明显它比链表快，后者的查找时间为 O(N)。对于二叉树，如果树保持完美平衡，查找仅保持 O(log 2 N)。保持树平衡（例如红黑）增加了复杂性和插入时间。此外，对于链表和二叉树，每个元素都是单独分配的1 node，这意味着您必须取消引用指针并可能跳转到可能变化很大的内存地址，从而增加缓存未命中的机会。

至于哈希表，您可能应该在 StackOverflow 上阅读其他几个问题，但这里的主要兴趣点是：

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

当然，如果您真的关心这些数据结构中的任何一个将如何执行，您应该测试它们。对于大多数常用语言，您应该可以轻松找到其中任何一个的良好实现。将一些真实数据放在这些数据结构中的每一个上，看看哪个表现最好，应该不会太难。

  1. 实现可以预先分配节点数组，这将有助于解决缓存未命中问题。我在链表或二叉树的任何实际实现中都没有看到这一点（当然，我并不是每个都见过），尽管你当然可以自己动手。但是，缓存未命中的可能性仍然略高，因为节点对象必然大于键/值对。
于 2008-12-16T14:34:00.343 回答
7

我喜欢比尔的回答，但它并没有真正综合起来。

从三个选择中：

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

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

留下树木。不过，您在这里有一个选择：平衡或不平衡。通过研究我们这里的 C 和 Fortran 代码上的这个问题，我发现符号表输入往往是足够随机的，如果不平衡树，你只会损失大约一两个树级别。鉴于平衡树插入元素的速度较慢且难以实现，因此我不会打扰它们。但是，如果您已经可以访问很好的调试组件库（例如：C++ 的 STL），那么您不妨继续使用平衡树。

于 2008-12-16T14:32:58.553 回答
6

有几点需要注意。

  • 如果树是平衡的，二叉树只有 O(log n) 查找和插入复杂度。如果您的符号以非常随机的方式插入，这应该不是问题。如果它们按顺序插入，您将构建一个链表。（对于您的特定应用程序，它们不应该按任何顺序排列，所以应该没问题。）如果符号有可能过于有序，红黑树是更好的选择。

  • 哈希表的平均插入和查找复杂度为 O(1)，但这里也有一个警告。如果您的哈希函数很糟糕（我的意思是非常糟糕），您最终也可以在这里构建一个链表。但是，任何合理的字符串散列函数都应该这样做，所以这个警告实际上只是为了确保您知道它可能会发生。您应该能够测试您的哈希函数在您的预期输入范围内没有太多冲突，您会没事的。另一个小缺点是如果您使用的是固定大小的哈希表。大多数哈希表实现在达到一定大小时都会增长（更精确的负载因子，请参见此处详情）。这是为了避免将一百万个符号插入十个桶时遇到的问题。这只会导致十个平均大小为 100,000 的链表。

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

于 2008-12-16T13:09:01.343 回答
1

其他评论集中在添加/检索元素上，但是如果不考虑迭代整个集合需要什么，这个讨论是不完整的。这里的简短回答是哈希表需要更少的内存来迭代，但树需要更少的时间。

对于哈希表，迭代 (key, value) 对的内存开销不取决于表的容量或表中存储的元素数量；事实上，迭代应该只需要一个或两个索引变量。

对于树，所需的内存量始终取决于树的大小。您可以在迭代时维护未访问节点的队列，也可以向树添加额外的指针以便于迭代（为了迭代的目的，使树像链表一样），但无论哪种方式，您都必须为迭代分配额外的内存.

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

于 2009-01-16T00:21:11.587 回答
0

当然，这取决于几件事。我会说链表是正确的，因为它几乎没有合适的属性可以用作符号表。如果您已经拥有二叉树并且不必花时间编写和调试它，二叉树可能会起作用。我的选择是哈希表，我认为这或多或少是此目的的默认值。

于 2008-12-16T12:24:28.513 回答
0

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

于 2008-12-16T12:25:10.637 回答
0

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

二叉树可以更快，只要它是平衡的。如果您要保留内容，则序列化表单可能会被排序，并且当它重新加载时，结果树将完全不平衡，并且它的行为与链表相同 - 因为那是基本上它变成了什么。平衡树算法解决了这个问题，但使整个 shebang 更加复杂。

哈希图（只要您选择合适的哈希算法）看起来是最好的解决方案。您没有提到您的环境，但几乎所有现代语言都内置了 Hashmap。

于 2008-12-16T12:29:23.140 回答