How fast is operation on KeyCollection returned by

问题:

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).

回答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, the ContainsKey method should be O(1):

This method approaches an O(1) operation.

The Keys.Contains method actually calls the parent dictionary's ContainsKey method, so that should also be O(1):

This method is an O(1) operation.

(Both quotes are taken from the "Remarks" section of the relevant documentation pages.)

回答2:

The first link you provided says, in the Remarks:

This method approaches an O(1) operation.

Also, if you click on the Contains method you'll see the same thing in the remarks:

This method is an O(1) operation.