Yes, this looks very much like a logarithmic increase, doesn't it? And it jives with what you say about using n/log(n) buckets. If there are n items in the hash and m buckets, then the amortized cost of any hash operation is O(1+n/m). If indeed Perl is using n/log(n) buckets, this makes all hash operations logarithmic.

I'm pretty sure this implies that if you scale the number of buckets proportional to n (instead of n/log(n)), you will get constant-time operations. But perhaps something yucky happens when you try to implement such a creature. Or perhaps I am confusing hashes with other amortized structures (where I know for a fact that certain operations are constant-time). In either case, the empirical evidence suggests I should retract my assertion about constant amortized hashes in Perl. Is there an internals geek around who can shed light on the actual implementation used?