1

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

4

1 回答 1

2

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

  1. 哈希函数（确定分布）
  2. 表如何处理冲突？试探？桶？（大多数实现使用存储桶）。
  3. 表可以调整大小吗？它如何调整大小？小增量？2的幂？质数？
  4. ETC...
于 2009-05-21T05:26:04.720 回答