Created
May 9, 2013 00:20
-
-
Save obstschale/5544684 to your computer and use it in GitHub Desktop.
A good hash function is a bit like a random number generator. Given a regular pattern of input, the output appears chaotic. A good hash function for integers is where p0, p1, and p2 are large primes. (T does not have to be prime.)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
h(k) = ( (p0 * k + p1) % p2) % T | |
h(k) = ((438439 * k + 34723753) % 376307) % 10 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Aside: Not only does this look like a random number generator, but it is a good random number generator. To get 16-bit pseudo-random numbers, use
unsigned R0 = seed
R_(n+1) = ((R_n + p_0) * p_1) MOD p_2
Return R_(n+1) MOD 2^(16)