logo标签列表

ContainsKey和TryGetValue的性能如何？

c#.netalgorithmbig-o
10

我正在为面试做准备，一些常见的面试问题，例如计算字符串中字符出现频率，需要将所有字符放入Hashtable/Dictionary中，以获得O(n)的算法运行时间。 我的问题是，使用ContainsKey和TryGetValue 来检查一个键是否已插入到Hashtable中会对性能产生影响吗？ 对于类似这样使用ContainsKey或TryGetValue 的问题，我仍然可以拥有O(n)的算法吗？

1个回答
11

假设哈希函数很好且冲突不多，那么每个操作都是O(1)。

至于这些操作如何工作...我建议您阅读有关哈希表的文献。

@alexD -- 记住，在最优情况下，它是O(1)。使用世界上最糟糕的哈希算法的哈希表将把每个项放入单个链表桶或类似的桶中，并在排序重复项时接近O(N)。 :) - Joe
1
TryGetValue似乎比ContainsKey更快，因为后者需要进行两次哈希查找才能匹配 - 先是测试，然后是检索。 - Chris
@Chris：是的，我希望它会更快 - 但不是在算法复杂度方面，其中常数因素并不重要。 - Jon Skeet
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接