二叉树 vs. 链表 vs. 哈希表 [英] 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 and creating a symbol table.

我进行了大量搜索，最常推荐的是二叉树、链表或哈希表.以上所有的优点和/或缺点是什么?(在 C++ 中工作)

I've done a fair bit of searching and the most commonly recommended are binary trees or linked lists or hash tables. What are the advantages and or disadvantages of all of the above? (working in c++)

推荐答案

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

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.

因此，我认为 HashTable 是最适合使用的算法，因为它只是生成关键对象的散列并使用它来访问目标数据 - 它是 O(1).其他的是 O(N)(大小为 N 的链表——你必须一次遍历一个列表，平均 N/2 次)和 O(log 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).

只要确保 HashTable 中有足够的空间(存储桶)来存放您的数据(R.e.，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?

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