什么样的数据结构能够以最快的速度进行搜索和插入功能？

这个问题几乎说明了这一切，但我正在构建一个编译器，并试图决定用于我的符号表的什么样的数据结构。考虑到符号表所需的唯一功能是搜索和插入，我希望使用可以尽快完成这些操作的数据结构。有什么建议么？什么样的数据结构能够以最快的速度进行搜索和插入功能？

2010-02-21 adhanlon

Hash tables非常常用于此。使用N分箱和采用每个符号中的字母总和（模N）的散列函数的简单实现在插入和搜索时应该非常接近O（1）。

2010-02-21 22:48:13

散列函数你的建议是很坏的哈希函数的复杂性，它使所有字谜碰撞。系统散列函数会更好（如果OP最喜欢的语言中有一个）。 – 2010-02-21 23:01:33

我将不得不找出一个更好的散列函数来使用，但散列表似乎是符号表的方式。 – adhanlon 2010-02-21 23:04:57

任何人都知道标准模板库的SET容器如何以符号表的形式执行？ – adhanlon 2010-02-21 23:14:37

Dictionary/Hashtable如果我没有弄错，查找速度为O（1）。

2010-02-21 22:46:33

关于散列表查找 - 只有在没有或几个冲突发生时才是O（1） - 所以假设您有适当的散列函数，它通常是O（1），但在最糟糕的情况下，它可能会以O（N ）。对数据大小的良好估计至关重要。

而且你还要考虑时间，你打算使用

2010-11-06 22:56:08 PJK

回答