One of the reasons perl went to randomizing hashes was people were deliberately using bad hash data to create DOS's ... HASH's with the wrong data become O(n) -- slightly worse than linear search due to the overhead, but in the IDEAL case, they are O(1). That's why I ***thought*** on the average, they'd grow at ~ the square root of n, but it's largely dependent on # keys and size of hash table. When #keys ~<=~ 70% hash table size, you get near O(1)...

wikipedia says it is possible with a self-balancing hash tree (brain hurts just thinking about intermixing one of those with a hash tree...) to reduce worst case to O(log n), but its not usually worth the tradeoff in algorithmic complexity -- sorta like me trying to improve on 'map' and 1 hash lookup... ;-)