asp.net：在字典中按键搜索值的时间复杂度是常数时间还是log2(n)？

Question

我需要 dotnet 中的一个数据结构，我可以在恒定时间内搜索一个项目。这意味着数据结构应该在内部实现索引。字典对于此目的或其他目的有用吗？

Answer 1

是的，使用 Dictionary<>（如果您使用的是旧版本的 .NET，则使用 Hashtable）。确保您填充到字典中的对象具有良好的哈希值（针对您在字典中用作键的对象，查看重写 GetHashCode() 和 Equals()）。如果您的数据对象的哈希码性能较差，性能就会开始下降。是的，为了回答你的问题，在哈希表/字典中查找应该是相对恒定的时间（书籍通常说它是 O(1)，但这是有争议的）。查找性能将由许多因素决定：

1. 哈希函数（决定分布）
2. 表如何处理碰撞？试探？水桶？（大多数实现都使用存储桶）。
3. 桌子可以调整大小吗？它如何调整大小？小增量？2 的幂？质数？
4. ETC...