title: What the iteration cost on a HashSet also depend on the capacity of backing map?
body: <p>From the JavaDocs of <a href="http://docs.oracle.com/javase/6/docs/api/java/util/HashSet.html#contains%28java.lang.Object%29">HashSet</a>:</p>
  
  <blockquote>
    <p>This class offers constant time performance for the basic operations
    (add, remove, contains and size), assuming the hash function disperses
    the elements properly among the buckets. Iterating over this set
    requires time proportional to the sum of the HashSet instance's size
    (the number of elements) plus the "capacity" of the backing HashMap
    instance (the number of buckets). Thus, it's very important not to set
    the initial capacity too high (or the load factor too low) if
    iteration performance is important</p>
  </blockquote>
  
  <p>Why does iteration takes time proportional to the sum(number of elements in set+ capacity of backing map)  and not only to the number of elements in the set itself ? </p>
  
  <p>.</p>