I read the section on sequential numbers as just illustrating a worst-case scenario of the case that could happen with either a naive hasher or malicious input.
As far as I can see all the graphs but one use random numbers, so hashing won't add anything given good randomness.
> Note that even if you reduce modulo a prime > n, you'll still have the identity over the first n numbers.
Which can be great! E.g. Python uses the identity function for number hashes, because if you're inserting mostly sequential numbers into a dict this gives you better cache performance.
> Python uses the identity function for number hashes, because if you're inserting mostly sequential numbers into a dict this gives you better cache performance.
That's a good idea when you control both the hash function and the hashtable implementation, as in the Python interpreter, so you can make assumptions on both sides.
My point was that when using composable templates, as in the STL, the hash function should not make any assumptions about the hash table, and vice versa.
As far as I can see all the graphs but one use random numbers, so hashing won't add anything given good randomness.
I've heard good arguments why linear probing should perform as well as quadratic probing when using Robin Hood bucket stealing, e.g. http://codecapsule.com/2013/11/11/robin-hood-hashing/#commen...
> Note that even if you reduce modulo a prime > n, you'll still have the identity over the first n numbers.
Which can be great! E.g. Python uses the identity function for number hashes, because if you're inserting mostly sequential numbers into a dict this gives you better cache performance.