title: What is the lookup time complexity of HashSet<T>(IEqualityComparer<T>)?
body: <p>In C#.NET, I like using HashSets because of their supposed O(1) time complexity for lookups.  If I have a large set of data that is going to be queried, I often prefer using a HashSet to a List, since it has this time complexity.</p>
  
  <p>What confuses me is the constructor for the HashSet, which takes IEqualityComparer as an argument:</p>
  
  <p><a href="http://msdn.microsoft.com/en-us/library/bb359100.aspx">http://msdn.microsoft.com/en-us/library/bb359100.aspx</a></p>
  
  <p>In the link above, the remarks note that the "constructor is an O(1) operation," but if this is the case, I am curious if lookup is still O(1).</p>
  
  <p>In particular, it seems to me that, if I were to write a Comparer to pass in to the constructor of a HashSet, whenever I perform a lookup, the Comparer code would have to be executed on every key to check to see if there was a match.  This would not be O(1), but O(n).</p>
  
  <p>Does the implementation internally construct a lookup table as elements are added to the collection?</p>
  
  <p>In general, how might I ascertain information about complexity of .NET data structures?</p>