IDictionary<TK, TV> 定义方法 IDictionary.ContainsKey(in TK) 和属性(property) IDictionary.Keys (类型 ICollection )。
我对 Dictionary 中此方法和属性的(渐近)复杂性感兴趣实现 IDictionary<TK, TV> .
考虑定义
IDictionary<int, string> dict = new Dictionary<int, string>();
int k = new Random().Next();
并考虑我们已经添加到字典dict n独一无二 KeyValuePair
调用的预期(渐近)复杂度是多少 dict.ContainsKey(k) ？我希望它在 O(1)但我没有在 documentation of Dictionary.ContainsKey 中找到它.
调用的预期(渐近)复杂度是多少 dict.Keys.Contains(k) ？我希望它在 O(1)但我没有在 documentation of Dictionary.Keys 中找到它也不在documentation of Dictionary.KeyCollection .如果在O(1)我不明白为什么要输入 IDictionary.Keys属性是 ICollection而不是 ISet (例如在 Java 中)。
最佳答案
自 IDictionary<K,V>只是一个接口(interface)，不是一个实现，那么它不提供任何性能保证。
对于内置 Dictionary<K,V>类型， ContainsKey 方法应该是 O(1):
Keys.Contains 方法实际上调用父字典的 ContainsKey方法，所以这也应该是 O(1):
(两条引文均摘自相关文档页面的“备注”部分。)
关于c# - Dictionary.Keys 返回的 KeyCollection 的操作速度有多快？ (。网)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5671512/