代码之家 › 专栏 › 技术社区 › adhanlon

什么数据结构具有最快的搜索和插入功能时间?

big-o language-agnostic time data-structures

2

adhanlon · 技术社区 · 16 年前

这个问题基本上说明了一切,但我正在构建一个编译器,并试图决定我的符号表使用哪种数据结构。考虑到符号表只需要一个搜索和一个插入,我想使用一个数据结构,它可以尽可能快地完成这些任务。有什么建议吗?

3 回复 | 直到 10 年前

1

2

Robert Karl 16 年前

Hash tables 是非常常用的。一个简单的实现 N 在插入和搜索时,接收每个符号(mod n)中字母总和的bin和hash函数应该非常接近o(1)。

2

Mike Trpcic 16 年前

Dictionary/Hashtable 如果我没弄错的话,查找速度是0(1)。

3

1

PJK 15 年前

关于哈希表查找——只有在没有或很少发生冲突的情况下才是O(1)——所以假设您有适当的哈希函数,它通常是O(1),但在最坏的情况下,它可能以O(n)结束。对数据大小的良好估计至关重要。

您还应该考虑您打算使用的散列函数的时间复杂性。