二叉树与链接列表与哈希表

我正在为我正在进行的项目构建一个符号表.我想知道人们对可用于存储和创建符号表的各种方法的优点和缺点的看法.

我做了很多搜索,最常推荐的是二叉树或链表或哈希表.以上所有优点和缺点是什么？(在c ++中工作)

1> Darron..：

---

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

二叉树

实现的中等复杂性(假设您无法从库中获取它们)

插入是O(logN)

查找是O(logN)

链接列表(未排序)

实施的复杂性低

插入是O(1)

查找是O(N)

哈希表

实施的复杂性很高

插入物平均为O(1)

查找平均为O(1)

---

此外,我认为哈希表与正确平衡的二叉树一样容易实现.但这是非常主观的.

---

是的,实施复杂性是主观的.但我认为最小链表比最小哈希表更简单.然后添加自动平衡与冲突,并在完全不调整订单时调整大小.

---

对于未排序的链表,插入是O(1),而不是O(N),当与双重链接时,O(1)删除通常是使用它们的动机,而不是它们的实现复杂性.另一个动机是他们可以无限制地成长,没有复制.不是说我在这种情况下建议一个.

2> JeeBee..：

---

您的用例可能是"插入数据一次(例如,应用程序启动),然后执行大量读取,但很少有额外的插入".

因此,您需要使用快速查找所需信息的算法.

因此,我认为HashTable是最合适的算法,因为它只是生成密钥对象的哈希并使用它来访问目标数据 - 它是O(1).其他是O(N)(大小为N的链表 - 你必须一次遍历列表,平均N/2次)和O(log N)(二进制树 - 你用搜索空间减半每次迭代 - 只有在树是平衡的时候,这取决于你的实现,不平衡的树可能会有明显更差的性能).

只需确保HashTable中有足够的空间(存储桶)用于您的数据(Re,Soraz对此帖子的评论).大多数框架实现(Java,.NET等)都具有您不必担心实现的质量.

您是否在大学开设过数据结构和算法课程？

---

没有离开高中......所以没有.所有自学:)

---

如果桶的数量是总集合的很大一部分,则仅适用于哈希表查找的O(1).即如果你在512个存储桶中存储100万个条目,那么你仍然会进行2048个直接比较pr查找,这超过100万的log(n)(或13个直接比较pr查找)

---

具有质量哈希算法的哈希表的质量实现将给出O(1).二进制树的错误实现也可能比O(log N)更差.因此,对于问题的级别,说哈希表是O(1)可能已经足够好了.

---

@Stephan:详细说明.我声称哈希表是迄今为止用于符号表的最常见数据结构.

3> Joel Borggré..：

---

每个人似乎忘记的是,对于小N,IE表中的符号很少,链表可以比哈希表快得多,尽管理论上它的渐近复杂性确实更高.

Pike的C编程注释中有一个着名的qoute:"规则3.当n很小时,花式算法很慢,而n通常很小.花式算法有很大的常数.直到你知道n经常变大,不要花哨." http://www.lysator.liu.se/c/pikestyle.html

我不能从你的帖子中看出你是否会处理一个小N,但是要记住,大N的最佳算法不一定对小N有好处.

---

什么会定义N大？

---

这是依赖于实现的.如果您碰巧知道用于计算哈希值的算法,那么您可以看出它与n/2身份比较(链表的平均值)或log(n)身份比较(二叉树的平均值)相比有多贵. .

---

对于花哨的算法,"调试奇怪错误的时间"要高得多.保持简单,直到简单证明是站不住脚的.

4> P Daddy..：

---

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

你的钥匙是字符串.

插入一次完成.

查找经常进行.

键值对的数量相对较小(例如,小于K左右).

如果是这样,您可以考虑对这些其他结构中的任何一个进行排序.在插入期间,这将比其他表现更差,因为排序列表在插入时为O(N),而对于链表或散列表为O(1),并且为O(log ₂₎N)用于平衡二叉树.但是,排序列表中的查找可能比任何其他结构更快(我将在稍后解释),因此您可能会排在最前面.此外,如果您一次执行所有插入(或者在完成所有插入之前不需要查找),那么您可以简化插入到O(1)并在结尾处进行更快速的排序.更重要的是,排序列表比其他任何结构使用更少的内存,但这可能很重要的唯一方法是,如果你有许多小列表.如果您有一个或几个大型列表,那么哈希表可能会超出排序列表.

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

至于哈希表,你应该读一对夫妇的其他问题在这里StackOverflow上,但主要兴趣点这里:

在最坏的情况下,哈希表可以退化为O(N).

散列的成本是非零的,并且在一些实现中它可能是重要的,特别是在字符串的情况下.

与链表和二叉树一样,每个条目都是一个存储不仅仅是键和值的节点,在某些实现中也单独分配,因此您使用更多内存并增加缓存未命中的可能性.

当然,如果您真的关心这些数据结构中的任何一个将如何执行,您应该测试它们.对于大多数常见语言,您应该很难找到任何这些的良好实现.在每个数据结构中抛出一些真实数据并查看哪些表现最佳,这应该不会太困难.

_{实现可以预先分配节点数组,这将有助于缓存未命中问题.我没有在链接列表或二叉树的任何实际实现中看到这一点(当然不是我见过的每一个),尽管你可以自己推出.但是,由于节点对象必然大于键/值对,因此缓存未命中的可能性稍高.}

5> T.E.D...：

---

我喜欢比尔的答案,但它并没有真正合成的东西.

从三个选择:

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

哈希表可以非常快.但是,要使它工作,你必须为你的输入选择一个好的哈希,并且你必须选择一个足够大的表来保存所有内容而不会产生大量的哈希冲突.这意味着您必须了解输入的大小和数量.如果搞砸了,最终会得到一套非常昂贵且复杂的链表.我会说,除非你提前知道表格的大小,否则不要使用哈希表.这不同意你的"接受"答案.抱歉.

那留下了树木.你有一个选择:平衡或不平衡.通过在C和Fortran代码上研究这个问题我发现的是,符号表输入往往是随机的,你只能通过不平衡树而失去一两个树级别.鉴于平衡树插入元素的速度较慢且难以实现,我不打扰它们.但是,如果您已经可以访问很好的调试组件库(例如:C++的STL),那么您可以继续使用平衡树.

6> Bill the Liz..：

---

有几点需要注意.

如果树是平衡的,则二叉树仅具有O(log n)查找和插入复杂度.如果您的符号以非常随机的方式插入,这应该不是问题.如果它们按顺序插入,您将构建链接列表.(对于您的特定应用,它们不应该是任何顺序,所以您应该没问题.)如果符号有可能太有序,红黑树是更好的选择.

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

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