Dictionary.Keys 返回的 KeyCollection 操作有多快？ （。网）
IDictionary定义方法IDictionary.ContainsKey（TK 中） 和属性 IDictionary.Keys（类型为 ICollection）。 我对此方法和属性的（渐近）复杂性感兴趣 Dictionary IDictionary。
考虑定义
IDictionary<int, string> dict = new Dictionary<int, string>();
int k = new Random().Next();
并考虑我们已向字典中添加了 dict n 个唯一的 KeyValuePair。
调用 dict.ContainsKey(k) 的预期（渐近）复杂度是多少？我希望它在 O(1) 中，但我没有在 Dictionary.ContainsKey 的文档。
调用 dict.Keys.Contains(k) 的预期（渐近）复杂度是多少？我希望它在 O(1) 中，但我没有在 Dictionary.Keys 的文档，也不在 Dictionary.KeyCollection 的文档。如果它在 O(1) 中，我不明白为什么 IDictionary.Keys 属性的类型是 ICollection 而不是 ISet< /code> （例如 Java 中的代码）。
IDictionary<TK, TV> defines method IDictionary.ContainsKey(in TK) and property IDictionary.Keys (of type ICollection).
I'm interested in (asymptotic) complexity of this method and property in Dictionary implementation of IDictionary<TK, TV>.
Consider definitions
IDictionary<int, string> dict = new Dictionary<int, string>();
int k = new Random().Next();
and consider that we have added to the dictionary dict n unique KeyValuePairs.
What is expected (asymptotic) complexity of a call dict.ContainsKey(k)? I hope it's in O(1) but I did not find it in documentation of Dictionary.ContainsKey.
What is expected (asymptotic) complexity of call dict.Keys.Contains(k)? I hope it's in O(1)but I did not find it in documentation of Dictionary.Keys nor in documentation of Dictionary.KeyCollection. If it is in O(1) I don't understand why type of IDictionary.Keys property is ICollection and not ISet (like in Java for example).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
由于
IDictionary只是一个接口，而不是一个实现，因此它不提供任何性能保证。对于内置
Dictionary类型，ContainsKey方法应该是 O(1)：Keys.Contains方法实际上调用父字典的ContainsKey方法，因此也应该是 O(1)：（两者引用取自相关文档页面的“备注”部分。）
Since
IDictionary<K,V>is only an interface, not an implementation, then it doesn't provide any performance guarantees.For the built-in
Dictionary<K,V>type, theContainsKeymethod should be O(1):The
Keys.Containsmethod actually calls the parent dictionary'sContainsKeymethod, so that should also be O(1):(Both quotes are taken from the "Remarks" section of the relevant documentation pages.)
您提供的第一个链接在备注中说道：
另外，如果您单击
包含方法 你会在注释中看到同样的事情：The first link you provided says, in the Remarks:
Also, if you click on the
Containsmethod you'll see the same thing in the remarks: