On Jan 13, 2016, at 1:45 PM, Simon Slavin <slavins at bigfraud.org> wrote: > > On 13 Jan 2016, at 7:36pm, Warren Young <wyml at etr-usa.com> wrote: > >> Wouldn?t that be log2(100) = 6.6 or log(100 = 4.6 maximum node visits? >> >> Most hash table implementations have logarithmic lookup time, not linear. > > You're quite right.
No, not entirely. :) Hash tables are not inherently balanced, so depending on the input data and the hashing scheme used, it could be as bad as 100 visits. A good hashing algorithm reduces that worst case chance to near zero, but some amount of imbalance is to be expected. The logarithmic values are best typical case, not worst case. Contrast a red-black or AVL tree, which is *always* balanced. That?s why C++ STL implementations use one of those two for std::map and such. The efficiency guarantees in the C++ standard disallow implementing them in terms of hash tables. Later (C++11) they added std::unordered_map and friends with different restrictions tat allow hash table implementations.
