二叉树与链表与哈希表 [英] Binary Trees vs. Linked Lists vs. Hash Tables

问题描述

我要建一个符号表的一个项目我工作。我想知道什么人民的意见是对的各种方法的优点和缺点，可用于存储+创建符号表。

I'm building a symbol table for a project I'm working on. I was wondering what peoples opinions are on the advantages and disadvantages of the various methods available for storing + creating a symbol table.

我已经做搜索的公平一点，最常见的建议是二进制树或链表或哈希表。我想知道什么是以上所有的优点，还是缺点（我无法找到这样的东西）。

I've done a fair bit of searching and the most commonly recommended are binary trees or linked lists or hash tables. I was wondering what are the advantages and or disadvantages of all of the above (I can't find anything on this).

谢谢， 本

更新：我在C ++的工作。

Update: am working in c++

推荐答案

您的使用情况是presumably将是插入一次数据（例如，应用程序启动），然后进行大量的阅读，但几乎没有任何多余的插入

Your use case is presumably going to be "insert the data once (e.g., application startup) and then perform lots of reads but few if any extra insertions".

因此​​，你需要使用一种算法是快速的查找你需要的信息。

Therefore you need to use an algorithm that is fast for looking up the information that you need.

我思故哈希表是最合适的算法来使用，因为它只是生成密钥对象的哈希并用它来访问目标数据 - 它是O（1）。其他是O（N）（大小为N链表 - 您必须通过列表的一个迭代的时间，平均为N / 2次）和O（日志N）（二叉树 - 你一半的搜索空间每次迭代 - 只有当树是平衡的，所以这取决于具体的实现，一个不平衡的树可以有显著表现更差）

I'd therefore think the HashTable was the most suitable algorithm to use, as it is simply generating a hash of your key object and using that to access the target data - it is O(1). The others are O(N) (Linked Lists of size N - you have to iterate through the list one at a time, an average of N/2 times) and O(log N) (Binary Tree - you halve the search space with each iteration - only if the tree is balanced, so this depends on your implementation, an unbalanced tree can have significantly worse performance).

只要确保有足够的空间（桶）中的哈希表为您的数据（再保险公司，对这个职位Soraz的评论）。大多数框架实现（Java，.NET等）将是你不需要担心实现了质量的。

Just make sure that there are enough spaces (buckets) in the HashTable for your data (R.e., Soraz's comment on this post). Most framework implementations (Java, .NET, etc) will be of a quality that you won't need to worry about the implementations.

你做一个疗程的数据结构和算法上大学？

Did you do a course on data structures and algorithms at university?

这篇关于二叉树与链表与哈希表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！