Comment by denormalfloat

That's not what big O notation is about. It represents the growth rate. In a the case of a hash table, the size of the thing you are hashing is not affected by the number of items present in the hash table. Putting a trillion bit integer into a hash table of other integers is still O(1); it's a constant.