Skip to content

Instantly share code, notes, and snippets.

@obstschale
Created May 9, 2013 00:20
Show Gist options
  • Save obstschale/5544684 to your computer and use it in GitHub Desktop.
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.)
h(k) = ( (p0 * k + p1) % p2) % T
h(k) = ((438439 * k + 34723753) % 376307) % 10
@obstschale
Copy link
Author

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment