IDictionary<TK, TV> http://msdn.microsoft.com/en-us/library/s4ys34ea.aspx定义方法IDictionary.ContainsKey(in TK) http://msdn.microsoft.com/en-us/library/htszx2dy.aspx和财产IDictionary.Keys http://msdn.microsoft.com/en-us/library/1ebzfbyx.aspx（类型ICollection）。
我对此方法和属性的（渐近）复杂性感兴趣Dictionary http://msdn.microsoft.com/en-us/library/xfhwa508.aspx实施IDictionary<TK, TV> http://msdn.microsoft.com/en-us/library/s4ys34ea.aspx.
考虑定义
IDictionary<int, string> dict = new Dictionary<int, string>();
int k = new Random().Next();
并认为我们已经添加到字典中dict n unique KeyValuePairs.
调用的预期（渐近）复杂度是多少dict.ContainsKey(k)？我希望它在O(1)但我没有找到它的文档Dictionary.ContainsKey http://msdn.microsoft.com/en-us/library/kw5aaea4.aspx.
调用的预期（渐近）复杂度是多少dict.Keys.Contains(k)？我希望它在O(1)但我没有找到它的文档Dictionary.Keys http://msdn.microsoft.com/en-us/library/yt2fy5zk.aspx nor in 的文档Dictionary.KeyCollection http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx。如果是在O(1)我不明白为什么类型IDictionary.Keys财产是ICollection并不是ISet（例如在 Java 中）。
Since IDictionary<K,V>只是一个接口，而不是实现，那么它不提供任何性能保证。
对于内置Dictionary<K,V>类型，即ContainsKey http://msdn.microsoft.com/en-us/library/kw5aaea4.aspx方法应该是 O(1)：
此方法的操作接近 O(1)。 http://msdn.microsoft.com/en-us/library/kw5aaea4.aspx
The Keys.Contains http://msdn.microsoft.com/en-us/library/cc673071.aspx方法实际上调用父字典的ContainsKey方法，所以也应该是 O(1)：
此方法是一个 O(1) 操作。 http://msdn.microsoft.com/en-us/library/cc673071.aspx
（这两个引文均取自相关文档页面的“备注”部分。）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
