title: Does Guava's ImmutableSet membership method mimic java.util.HashSet#contains?
body: <p>I need to ensure that a certain <code>Set&lt;String&gt;</code> I create is not modified somewhere else in the code. Of course, I ended up using Guava's <a href="http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/collect/ImmutableSet.html" rel="nofollow">ImmutableSet</a> for this.</p>
  
  <p>This immutable set is quite large (approx. 59K Strings), and I have to perform a <code>Set#contains</code> check every time a particular method is called. So I was wondering if there is any way of specifying the look-up in big set. Guava's documentation says:</p>
  
  <blockquote>
    <p>A high-performance, immutable Set with reliable, user-specified
    iteration order. Does not permit null elements.</p>
  </blockquote>
  
  <p>What does <code>user-specified iteration</code> mean if the immutable set is created by calling <code>ImmutableSet#copyOf(aHashSet)</code>? Will the performance of <code>contains(String)</code> be adversely affected if I use <code>ImmutableSet#contains</code> instead of <code>HashSet#contains</code>? To be more precise, my question is the following:</p>
  
  <p><em>With a decent hash function and not too many elements getting in the same bucket, one would expect <code>HashSet#contains</code> to be O(1). Will an ImmutableSet created using <code>copyOf</code> adhere to this?</em></p>
  
  <p>There are two reasons behind my suspicion that this might not be the case:</p>
  
  <ol>
  <li><p><a href="https://groups.google.com/forum/#!topic/guava-discuss/I7yPpa5Hlpg" rel="nofollow">Guava forum discussion on precisely this question</a> (didn't seem to provide a conclusive answer though).</p></li>
  <li><p>It's not clear to me whether <code>ImmutableSet#contains</code> defers to <code>java.util.Set#contains</code> (i.e., the implementation in <code>HashSet</code>, in my case) or <code>com.google.common.collect.ImmutableCollection#contains</code>. If it is the latter, then <code>ImmutableSet#contains</code> will be an O(n) operation.</p></li>
  </ol>