Dictionary.Keys返回的KeyCollection上的操作有多快？(.净)

Question

IDictionary<TK, TV>定义方法IDictionary.ContainsKey(in TK)和属性IDictionary.Keys(类型ICollection).我对(渐近)此方法的复杂性和Dictionary实现中的属性感兴趣IDictionary<TK, TV>.

考虑定义

IDictionary<int, string> dict = new Dictionary<int, string>();
int k = new Random().Next();

并考虑到我们已经添加到字典中的dict n唯一KeyValuePairs.

什么是预期(渐近)呼叫的复杂性dict.ContainsKey(k)？我希望它在,O(1)但我没有在文档中Dictionary.ContainsKey找到它.

呼叫的复杂性是什么(渐近)dict.Keys.Contains(k)？我希望它在,O(1)但我没有在文档中Dictionary.Keys或在文档中Dictionary.KeyCollection找到它.如果是O(1)我不明白,为什么类型的IDictionary.Keys属性ICollection,而不是ISet(像Java中的例子).

Answer 1

由于IDictionary<K,V>它只是一个接口,而不是一个实现,因此它不提供任何性能保证.

对于内置Dictionary<K,V>类型,该ContainsKey方法应为O(1):

该方法接近O(1)操作.

该Keys.Contains方法实际上调用了父类字典的ContainsKey方法,因此它也应该是O(1):

该方法是O(1)操作.

(两个引用均来自相关文档页面的"备注"部分.)

Answer 2

您提供的第一个链接在备注中说:

该方法接近O(1)操作.

此外,如果您单击该Contains方法,您会在备注中看到相同的内容:

该方法是O(1)操作.