Databases
StackOverflow2013
Postsdbo
POHow fast is operation on KeyCollection returned by Dictionary.Keys ? (.NET)
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow fast is operation on KeyCollection returned by Dictionary.Keys ? (.NET)
    text
    copied!<p><a href="http://msdn.microsoft.com/en-us/library/s4ys34ea.aspx" rel="nofollow"><code>IDictionary&lt;TK, TV&gt;</code></a> defines method <a href="http://msdn.microsoft.com/en-us/library/htszx2dy.aspx" rel="nofollow"><code>IDictionary.ContainsKey(in TK)</code></a> and property <a href="http://msdn.microsoft.com/en-us/library/1ebzfbyx.aspx" rel="nofollow"><code>IDictionary.Keys</code></a> (of type <code>ICollection</code>). I'm interested in (asymptotic) complexity of this method and property in <a href="http://msdn.microsoft.com/en-us/library/xfhwa508.aspx" rel="nofollow"><code>Dictionary</code></a> implementation of <a href="http://msdn.microsoft.com/en-us/library/s4ys34ea.aspx" rel="nofollow"><code>IDictionary&lt;TK, TV&gt;</code></a>.</p> <p>Consider definitions </p> <pre><code>IDictionary&lt;int, string&gt; dict = new Dictionary&lt;int, string&gt;(); int k = new Random().Next(); </code></pre> <p>and consider that we have added to the dictionary <code>dict</code> <code>n</code> unique <code>KeyValuePair</code>s.</p> <p>What is expected (asymptotic) complexity of a call <code>dict.ContainsKey(k)</code>? I hope it's in <code>O(1)</code> but I did not find it in <a href="http://msdn.microsoft.com/en-us/library/kw5aaea4.aspx" rel="nofollow">documentation of <code>Dictionary.ContainsKey</code></a>.</p> <p>What is expected (asymptotic) complexity of call <code>dict.Keys.Contains(k)</code>? I hope it's in <code>O(1)</code>but I did not find it in <a href="http://msdn.microsoft.com/en-us/library/yt2fy5zk.aspx" rel="nofollow">documentation of <code>Dictionary.Keys</code></a> nor in <a href="http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx" rel="nofollow">documentation of <code>Dictionary.KeyCollection</code></a>. If it is in <code>O(1)</code> I don't understand why type of <code>IDictionary.Keys</code> property is <code>ICollection</code> and not <code>ISet</code> (like in Java for example).</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload