Re:Perl 11
by CydeWeys on Wednesday October 24, 2018 @07:52AM
(#18291565)
Hashtables are typically considered amortized O(1) for insert and retrieve. The atrocious worst-case performance doesn't happen in common implementations because the hashtable gets enlarged before or when it occurs (and these resizes still allow for amortized O(1) performance).
And logarithmic growth in the key size is definitely not as bad as logarithmic growth in the number of nodes in a tree to traverse, because going from calculating e.g. a key size of 28 to 29 bits is not a big deal at all, but going from 28 to 29 levels in your tree means an entirely new memory lookup to grab that one node. The hash calculation is always cheap, whereas traversing a tree thrashes caches -- you only need one memory lookup in a hashtable, whereas you need logN in a tree. Those lookups are orders of magnitude more expensive time-wise than the simple integer math involved in calculating the hash.
And logarithmic growth in the key size is definitely not as bad as logarithmic growth in the number of nodes in a tree to traverse, because going from calculating e.g. a key size of 28 to 29 bits is not a big deal at all, but going from 28 to 29 levels in your tree means an entirely new memory lookup to grab that one node. The hash calculation is always cheap, whereas traversing a tree thrashes caches -- you only need one memory lookup in a hashtable, whereas you need logN in a tree. Those lookups are orders of magnitude more expensive time-wise than the simple integer math involved in calculating the hash.