二叉树与链表与哈希表
我正在为我正在进行的一个项目build立一个符号表。 我想知道人们对各种可用于存储和创build符号表的方法的优缺点有何看法。
我已经做了一点search，最常见的是二叉树或链表或散列表。 以上所有的优点和缺点是什么？ （使用C ++）
你的用例大概是“插入数据一次（例如，应用程序启动），然后执行大量的读取，但如果任何额外的插入很less”。
因此，您需要使用快速查找所需信息的algorithm。
因此，我认为HashTable是最合适的algorithm，因为它只是生成一个关键对象的哈希值，并使用它来访问目标数据 – 它是O（1）。 其他的是O（N）（大小为N的链表 – 你必须一次遍历一个列表，平均N / 2次）和O（log N）（二叉树 – 你将search空间减半每次迭代 – 只有当树是平衡的，所以这取决于你的实现，一个不平衡的树可以有更差的性能）。
只要确保HashTable中有足够的空间（存储桶）用于存储数据（Re，Soraz对此post的评论）。 大多数框架实现（Java，.NET等）将具有一个质量，您不需要担心实现。
你在大学学习过数据结构和algorithm吗？
这些数据结构之间的标准折衷适用。
- 二叉树
- 中等的复杂性来实现（假设你不能从库中获得它们）
- 插入是O（logN）
- 查找是O（logN）
- 链接列表（未sorting）
- 执行复杂度低
- 插入是O（1）
- 查找是O（N）
- 哈希表
- 实施起来很复杂
- 插入平均是O（1）
- 查找平均为O（1）
每个人似乎都忘记了，对于小N来说，表中的IE几个符号，链表可以比散列表快得多，尽pipe理论上它的渐近复杂度确实更高。
有一个来自Pike“C语言程序devise笔记”的着名的“规则3”：当n很小时，花式algorithm很慢，n通常很小，花式algorithm有很大的常量，直到你知道n往往很大，不要幻想。“ http://www.lysator.liu.se/c/pikestyle.html
我不能从你的文章中知道你是否正在处理一个小N，但是要记住，大N的最好的algorithm对于小N来说不一定是好的。
这听起来像以下可能都是事实：
- 你的钥匙是string。
- 插入完成一次。
- 查找经常完成。
- 键值对的数量相对较小（比如说less于一个K左右）。
如果是这样的话，你可以考虑对这些其他结构进行sorting。 在插入过程中，这将比其他的执行更差，因为插入的sorting列表是O（N），而对于链表或散列表则是O（1），对于平衡的二叉树是O（log 2 N）。 但是，sorting列表中的查找可能比这些其他结构中的任何一个都快（我将稍后解释），所以可能会排在前面。 另外，如果一次执行所有的插入操作（或者在所有插入操作完成之前不需要查找），那么可以简化O（1）的插入操作，并且最后可以更快地进行分类。 更重要的是，sorting列表使用的内存less于其他任何结构，但唯一的方法可能是重要的是，如果你有很多小列表。 如果您有一个或几个大的列表，那么哈希表可能会超出sorting列表。
为什么使用sorting列表查找速度更快？ 那么，显然它比链表更快，而后者的O（N）查找时间。 使用二叉树，如果树保持完美平衡，查找只保留O（log 2 N）。 保持树平衡（例如红黑色）增加了复杂性和插入时间。 此外，对于链表和二叉树，每个元素都是一个单独分配的1个 节点 ，这意味着您将不得不取消引用指针，并可能跳转到可能广泛变化的内存地址，增加了caching未命中的机会。
至于散列表，你可能应该在StackOverflow上读一些 其他的问题 ，但是这里主要的关注点是：
- 在最坏的情况下，哈希表可能退化为O（N）。
- 散列的代价是非零的，在某些实现中它可能是重要的，特别是在string的情况下。
- 就像在链表和二叉树中一样，每个条目都是一个存储不仅仅是键和值的节点 ，在一些实现中也是分开分配的，所以你使用了更多的内存并增加了caching未命中的机会。
当然，如果你真的关心这些数据结构如何执行，你应该testing它们。 对于大多数常用语言，您应该没有什么问题可以find其中的任何一种。 在这些数据结构的每个数据结构上抛出一些真实的数据并且看看哪个性能最好。
- 一个实现可能预先分配一个节点数组，这将有助于caching未命中的问题。 我没有看到任何真正的链表或二叉树的实现（当然，我没有看到每一个），尽pipe你肯定可以推出自己的。 但是，由于节点对象必须大于键/值对，所以caching未命中的可能性仍然稍高。
我喜欢比尔的回答，但是它并不真正综合。
从三个select：
链接列表从O（n）中查找项目相对较慢。 所以如果你的桌子上有很多东西，或者你要做很多的查找，那么它们不是最好的select。 但是，他们很容易build立，也容易写。 如果桌子很小，并且/或者您只在build好桌子后进行一次小的扫描，那么这可能是您的select。
哈希表可以非常快。 然而，为了它的工作，你必须为你的inputselect一个好的散列，并且你必须select一个足够大的表来保存所有的东西，而不会有太多的散列冲突。 这意味着你必须知道你input的大小和数量。 如果你搞砸了，你最终会得到一个非常昂贵和复杂的链表。 我会说，除非事先知道表格的大小，否则不要使用散列表。 这不符合你的“接受”的答案。 抱歉。
那留下树木。 你在这里有一个select，虽然：平衡或不平衡。 通过在C和Fortran代码上研究这个问题，我发现了这个问题，因为符号表input往往是随机的，所以只能通过不平衡树来丢失一两棵树。 由于平衡树插入元素的速度较慢，实施起来较为困难，所以我不打扰他们。 但是，如果你已经可以访问好的debugging组件库（例如：C ++的STL），那么你可以继续使用平衡树。
有几件事要注意。
-
如果树是平衡的，二叉树只有O（log n）查找和插入复杂性。 如果你的符号以非常随机的方式插入，这应该不成问题。 如果他们按顺序插入，你将build立一个链表。 （对于你的具体应用，它们不应该是任何forms的顺序，所以你应该没问题。）如果有可能符号过于有序， 红黑树是更好的select。
-
哈希表给O（1）平均插入和查找的复杂性，但这里也有一个警告。 如果你的哈希函数不好（我的意思是非常糟糕），那么你最终也可能会在这里build立一个链表。 但是，任何合理的string散列函数都应该这样做，所以这个警告实际上只是为了确保你知道它可能发生。 你应该能够testing你的散列函数在你的input范围内没有太多的冲突，你会没事的。 另一个小缺点是如果你使用一个固定大小的哈希表。 大多数散列表实现在达到一定的大小时就会增长（加载因子更加精确，详情请看这里 ）。 这是为了避免在将十万个符号插入十个桶中时所遇到的问题。 这只会导致10个平均大小为10万的链表。
-
如果我有一个非常短的符号表，我只会使用一个链表。 这是最容易实现的，但是对于链表来说，最好的情况是另外两个选项的最坏情况。
其他评论集中在添加/检索元素，但是这个讨论并不是完整的，没有考虑如何迭代整个集合。 这里的简短答案是哈希表需要更less的内存来迭代，但树需要更less的时间。
对于散列表，迭代（键，值）对的内存开销不取决于表的容量或存储在表中的元素的数量; 实际上，迭代只需要一个或两个索引variables。
对于树木，所需的内存量总是取决于树的大小。 您可以在迭代时维护未访问节点的队列，也可以向树中添加更多指针以便于迭代（为了进行迭代，使树成为链接列表），但是无论如何，您必须为迭代分配额外的内存。
但是在时间安排方面，情况是相反的。 对于散列表，迭代所花费的时间取决于表的容量，而不是存储元素的数量。 因此，以10％的容量加载的表将比使用相同元素的链表重复10倍的时间！
当然这取决于几件事情。 我想说，一个链接列表是正确的，因为它作为一个符号表有几个适当的属性。 如果你已经有了一棵二叉树，那么就可以工作了，而且不必花时间去编写和debugging它。 我的select将是一个哈希表，我认为这或多或less是默认的这个目的。
这个问题通过C＃中的不同容器，但是它们在你使用的任何语言中都是相似的。
除非你希望你的符号表很小，否则我应该避开链表。 1000个物品的清单平均需要500次迭代才能find其中的任何物品。
二叉树可以更快，只要它是平衡的。 如果你坚持的内容，序列化的forms可能会被sorting，并且当它被重新加载时，结果树将是完全不平衡的结果，它将performance与链接列表相同 – 因为这是基本上它变成了什么。 平衡树algorithm解决了这个问题，但使整个shebang更复杂。
一个hashmap（只要你select一个合适的哈希algorithm）看起来是最好的解决scheme。 你没有提到你的环境，但几乎所有的现代语言都内置了一个HashMap。
