title: O(1) hash look ups?
body: <p>I ran across an assertion that HashSet&lt;T&gt;.Contains() is an O(1) operation.  This surprised me since every discussion of hashing I've encountered mentions the possibility of collisions, potentially leading to O(n) run time.</p>
  
  <p>Being curious, I looked into documentation for HashSet&lt;T&gt;.Contains and also HashTable.Contains.  The documentation for both methods make that same claim.</p>
  
  <p>When I look in reflector, HashSet&lt;T&gt;.Contains() is implemented with a for loop, going through a list of slots containing values which have the same hash.</p>
  
  <p>Now admittedly, those same discussions of hashing have also mentioned that a good hashing algorithm avoids collisions and under those circumstances the lookup will indeed be O(1).  But my understanding of Big O notation is that it's the worst-case runtime time, not best.</p>
  
  <p>So is the O(1) claim incorrect? Or am I missing something?</p>