On Mon, Nov 29, 2010 at 09:31:37AM +0000, Sad Clouds wrote: > Joerg I was specifically talking about particular sequences of numbers > that result in high collision rates, not random numbers. For example, > if you take the following: > > 4, 8, 12, 16, 20 ... > > Every integer is a multiple of 4. Can you give me a full example of a > hash function for power of 2 hash table, that will perform as well as > a simple: > > interger % prime
I asked the Python Oracle for a 32bit number and got 3063404725. This results in hash(x,n) = ((3063404725ULL * x) >> 32) % n as function. For n=32 and 32 keys, I get 8 single collisions. For n=256 and 256 keys, I get 39 single collisions. Depending on the choosen random number, the collision rate will be higher or lower, but if it is too high, you can always just pick a different one and rehash. Theory says that the result is probalistically near a random distribution *independent* of the input. Joerg
