obstschale/hash_function.c

Created May 9, 2013 00:20

Star () You must be signed in to star a gist
Fork () You must be signed in to fork a gist

Learn more about clone URLs
Clone this repository at <script src="https://gist.github.com/obstschale/5544684.js"></script>
Save obstschale/5544684 to your computer and use it in GitHub Desktop.

Download ZIP

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.)

Raw

hash_function.c

	h(k) = ( (p0 * k + p1) % p2) % T

	h(k) = ((438439 * k + 34723753) % 376307) % 10

Author

obstschale commented Jun 19, 2013

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