&#62; <i>If the list size is known, it's very easy to construct a hash table or hash set where collisions are extremely low and O(1) lookups are expected</i><p>If the list size isn't known, you can still do this, by doubling the size of the hash table whenever there are too many entries in it.