哪种数据结构的搜索和插入功能的执行速度最快？
哪种数据结构的搜索和插入功能的执行速度最快？
提问于 2010-02-22 06:42:52
这个问题几乎说明了一切，但我正在构建一个编译器，并试图决定将哪种数据结构用于我的符号表。考虑到符号表需要的唯一功能是搜索和插入，我想使用一种可以尽可能快地完成这些操作的数据结构。有什么建议吗？
回答 3
Stack Overflow用户
回答已采纳
发布于 2010-02-22 06:48:13
Hash tables通常用于此目的。使用mod和一个哈希函数(取每个符号中字母的总和( N N) )的简单实现在插入和搜索时应该非常接近O(1)。
Stack Overflow用户
发布于 2010-02-22 06:46:34
如果我没记错的话，Dictionary/Hashtable的查找速度是O(1)。
Stack Overflow用户
发布于 2010-11-07 06:56:08
关于哈希表查找-只有当没有或很少发生冲突时，它才是O(1) -所以假设你有适当的哈希函数，它通常是O(1)，但在最坏的情况下，它可能会以O(N)结束。良好的数据大小估计是至关重要的。
此外，还应考虑要使用的散列函数的时间复杂性
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2307752
复制相关文章
相似问题
腾讯云开发者
