Well put. I'd like to add that, while hashing time is proportional to the key length, in practice it's very, very fast for all non-enormous keys, at least on mo

Well put. I'd like to add that, while hashing time is proportional to the key length, in practice it's very, very fast for all non-enormous keys, at least on modern processors. Compare with the cost of pointer-chasing in a tree, and hashing time starts to look pretty constant-ish. (Yes I'm handwaving around the details. So is everyone who talks about big-O notation in connection with real software.)