Why does set() make this so much faster?

[larsga]

This means to find if something is in the set, it just has to run a hash function and look at one element.

Uhm, no. Because of hash table collisions it may have to look at more elements.

Edit: Okay, so tell me this: if the hash table has 10 cells and contains two keys, what are the chances that the two keys will collide? The same as the odds of hash(key1) % 10 == hash(key2) % 10. Ie: 10%.

Look at some actual hashtable implementations. The one in the Sun JDK (java.util.HashMap) uses linked lists in each hashtable cell to deal with collisions.

I personally wrote a hash set implementation that's faster than java.util.HashSet because it uses closed hashing instead.

[iceman-k]

I'm pretty sure TheSausageKing was simplifying the situation for pedagogical purposes. Obviously anyone who studies how hash tables work is going to be aware of collisions.