Be careful here, because you hash the element, granted that may take O(n) where n is bits in the element, but n usually denotes the number of elements in a list, which can obviously be much larger and is thus far more important. EDIT: in part because the number of bits in each element doesn't "grow"; it's usually fixed.