Most often k is not a constant, but a function of n. If for example k would be ~ c * n then the average length of the lists of items in each bucket would be ~ n / (c * n) which is ~ 1 / c. Which is a constant.

Therefore the key lookup of the usual implementations of hashes has average complexity of o(1).

Of course this implementation forces you to recreate the hash when the number of keys grows over some limit which can be time consuming.

Jenda

P.S.: I just looked at the number of buckets in the Perl hashes (I iteratively added elements, watched the number of buckets and printed the number of elements and buckets after every rehashing). This is the results: