Dave Korn wrote:
Please, nobody bring up the old saw that prime numbers are a good choice for
hashtable sizes. They aren't, they're a crude workaround for a poor hash
function.
Well on a machine with a fast modulus operation, the crude workaround
is often the most efficient algorithm in practice.
One thing to realize is that hashing only has good average performance.
So your O(N) is talking about average case performance, whereas the
O(NlogN) for a tree search is worst case. That's comparing apples and
oranges. It is worrisome to have the possibility of really bad
performance for a particular bad luck case.
That's not how minimal perfect hashing works, which was one of the main
suggestions.
Right, in the case where you can do minimal perfect hashing, of course
the consideration of average case performance does not apply.
cheers,
DaveK
