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:

1       => 8
9       => 16
18      => 32
34      => 64
70      => 128
130     => 256
258     => 512
514     => 1024
1024    => 2048
2052    => 4096
4098    => 8192
8193    => 16384
16386   => 32768
32768   => 65536
65538   => 131072
Perl 5.8.0 built for MSWin32-x86-multi-thread
[download]