What integer hash function are good that accepts an integer hash key?

by

I found the following algorithm provides a very good statistical distribution. Each input bit affects each output bit with about 50% probability. There are no collisions (each input results in a different output). The algorithm is fast except if the CPU doesn’t have a built-in integer multiplication unit. C code, assuming int is 32 bit (for Java, replace >> with >>> and remove unsigned):

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

The magic number was calculated using a special multi-threaded test program that ran for many hours, which calculates the avalanche effect (the number of output bits that change if a single input bit is changed; should be nearly 16 on average), independence of output bit changes (output bits should not depend on each other), and the probability of a change in each output bit if any input bit is changed. The calculated values are better than the 32-bit finalizer used by MurmurHash, and nearly as good (not quite) as when using AES. A slight advantage is that the same constant is used twice (it did make it slightly faster the last time I tested, not sure if it’s still the case).

You can reverse the process (get the input value from the hash) if you replace the 0x45d9f3b with 0x119de1f3 (the multiplicative inverse):

unsigned int unhash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

For 64-bit numbers, I suggest to use the following, even thought it might not be the fastest. This one is based on splitmix64, which seems to be based on the blog article Better Bit Mixing (mix 13). 

uint64_t hash(uint64_t x) {
    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;
}

For Java, use long, add L to the constant, replace >> with >>> and remove unsigned. In this case, reversing is more complicated:

uint64_t unhash(uint64_t x) {
    x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3);
    x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089);
    x = x ^ (x >> 30) ^ (x >> 60);
    return x;
}

Update: You may also want to look at the Hash Function Prospector project, where other (possibly better) constants are listed.

More Related Contents:

  1. hash function for string
  2. Algorithm to find the smallest number in an array in C [closed]
  3. Recursive C function
  4. Finding target sum of two numbers in array
  5. How to remove blank spaces from buffer [closed]
  6. What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?
  7. Algorithm: efficient way to remove duplicate integers from an array
  8. What is the fastest substring search algorithm?
  9. how to rasterize rotated rectangle (in 2d by setpixel)
  10. Point in Polygon Algorithm
  11. What common algorithms are used for C’s rand()?
  12. Magic number in boost::hash_combine
  13. Matrix multiplication: Small difference in matrix size, large difference in timings
  14. Enumerate factors of a number directly in ascending order without sorting?
  15. Project Euler Question 14 (Collatz Problem)
  16. read line by line in the most efficient way *platform specific*
  17. How do you print the EXACT value of a floating point number?
  18. Time complexity of a recursive algorithm
  19. Finding all the unique permutations of a string without generating duplicates
  20. Objective C: SHA1
  21. Print all the permutations of a string in C
  22. Given an audio stream, find when a door slams (sound pressure level calculation?)
  23. find if 4 points on a plane form a rectangle?
  24. Linked list recursive reverse
  25. Generating a uniform distribution of INTEGERS in C
  26. Reductions in parallel in logarithmic time
  27. Finding out the duplicate element in an array
  28. Does C have any tools for doing string addition?
  29. Extend a line segment a specific distance
  30. QuickSort and Hoare Partition

Leave a Comment