129

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

2

11 Answers 11

211

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;
}

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;
}

All the above is for C. For Java, use long, add L to the constant, replace >> with >>> and remove unsigned.

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

46
  • 2
    the first two lines are exactly the same! is there a typo here? Nov 23, 2012 at 9:39
  • 7
    No this is not a typo, the second line further mixes the bits. Using just one multiplication isn't as good. Nov 23, 2012 at 9:54
  • 3
    I changed the magic number because according to a test case I wrote the value 0x45d9f3b provides better confusion and diffusion, specially that if one output bit changes, each other output bit changes with about the same probability (in addition to all output bits change with the same probability if an input bit changes). How did you measure 0x3335b369 works better for you? Is an int 32 bit for you? Nov 23, 2012 at 13:38
  • 3
    I am searching for a nice hash function for 64 bit unsigned int to 32 bit unsigned int. Is for that case, above magic number will be same ? I shifted 32 bit instead of 16 bits.
    – alessandro
    Nov 30, 2012 at 9:23
  • 3
    I believe in that case a larger factor would be better, but you would need to run some tests. Or (this is what I do) first use x = ((x >> 32) ^ x) and then use the 32 bit multiplications above. I'm not sure what's better. You may also want to look at the 64-bit finalizer for Murmur3 Nov 30, 2012 at 10:12
54

Knuth's multiplicative method:

hash(i)=i*2654435761 mod 2^32

In general, you should pick a multiplier that is in the order of your hash size (2^32 in the example) and has no common factors with it. This way the hash function covers all your hash space uniformly.

Edit: The biggest disadvantage of this hash function is that it preserves divisibility, so if your integers are all divisible by 2 or by 4 (which is not uncommon), their hashes will be too. This is a problem in hash tables - you can end up with only 1/2 or 1/4 of the buckets being used.

26
  • 45
    It's a really bad hash function, albeit attached to a famous name.
    – Seun Osewa
    Aug 16, 2010 at 16:00
  • 6
    It's not a bad hash function at all if used with prime table sizes. Also, it is meant for closed hashing. If hash values are not uniformly distributed, multiplicative hashing ensures that collisions from one value are unlikely to "disturb" items with other hash values. Jun 3, 2011 at 7:28
  • 14
    For the curious, this constant is chosen to be the hash size (2^32) divided by Phi
    – awdz9nld
    May 31, 2012 at 11:50
  • 8
    Paolo: Knuth's method is "bad" in the sense that it does not avalanche on the upper bits
    – awdz9nld
    May 31, 2012 at 11:51
  • 13
    On closer inspection, it turns out 2654435761 is actually a prime number. So that's probably why it was chosen rather than 2654435769.
    – karadoc
    Dec 5, 2013 at 12:13
32

Depends on how your data is distributed. For a simple counter, the simplest function

f(i) = i

will be good (I suspect optimal, but I can't prove it).

7
  • 3
    The problem with this is that it's common to have large sets of integers that are divisible by a common factor (word-aligned memory adresses etc.). Now if your hash table happens to be divisible by the same factor, you end up with only half (or 1/4, 1/8, etc.) buckets used. Mar 20, 2009 at 16:56
  • 10
    @Rafal: That's why the response says "for a simple counter" and "Depends on how your data is distributed"
    – erikkallen
    Mar 21, 2009 at 12:17
  • 6
    That's actually the implementation by Sun of the method hashCode() in java.lang.Integer grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… Oct 4, 2012 at 16:56
  • 5
    @JuandeCarrion That is misleading because that is not the hash that is being used. After moving over to using power of two table sizes, Java rehashes every hash returned from .hashCode(), see here.
    – Esailija
    Jun 1, 2013 at 0:49
  • 8
    The identity function is fairly useless as a hash in many practical applications due to its distributive properties (or lack thereof), unless, of course, locality is a desired attribute
    – awdz9nld
    Jan 20, 2015 at 21:34
25

Fast and good hash functions can be composed from fast permutations with lesser qualities, like

  • multiplication with an uneven integer
  • binary rotations
  • xorshift

To yield a hashing function with superior qualities, like demonstrated with PCG for random number generation.

This is in fact also the recipe rrxmrrxmsx_0 and murmur hash are using, knowingly or unknowingly.

I personally found

uint64_t xorshift(const uint64_t& n,int i){
  return n^(n>>i);
}
uint64_t hash(const uint64_t& n){
  uint64_t p = 0x5555555555555555ull; // pattern of alternating 0 and 1
  uint64_t c = 17316035218449499591ull;// random uneven integer constant; 
  return c*xorshift(p*xorshift(n,32),32);
}

to be good enough.

A good hash function should

  1. be bijective to not lose information, if possible and have the least collisions
  2. cascade as much and as evenly as possible, i.e. each input bit should flip every output bit with probability 0.5.

Let's first look at the identity function. It satisfies 1. but not 2. :

identity function

Input bit n determines output bit n with a correlation of 100% (red) and no others, they are therefore blue, giving a perfect red line across.

A xorshift(n,32) is not much better, yielding one and half a line. Still satisfying 1., because it is invertible with a second application.

xorshift

A multiplication with an unsigned integer ("Knuth's multiplicative method") is much better, cascading more strongly and flipping more output bits with a probability of 0.5, which is what you want, in green. It satisfies 1. as for each uneven integer there is a multiplicative inverse.

knuth

Combining the two gives the following output, still satisfying 1. as the composition of two bijective functions yields another bijective function.

knuth•xorshift

A second application of multiplication and xorshift will yield the following:

proposed hash

Or you can use Galois field multiplications like GHash, they have become reasonably fast on modern CPUs and have superior qualities in one step.

   uint64_t const inline gfmul(const uint64_t& i,const uint64_t& j){           
     __m128i I{};I[0]^=i;                                                          
     __m128i J{};J[0]^=j;                                                          
     __m128i M{};M[0]^=0xb000000000000000ull;                                      
     __m128i X = _mm_clmulepi64_si128(I,J,0);                                      
     __m128i A = _mm_clmulepi64_si128(X,M,0);                                      
     __m128i B = _mm_clmulepi64_si128(A,M,0);                                      
     return A[0]^A[1]^B[1]^X[0]^X[1];                                              
   }
6
  • 1
    gfmul: The code appears to be pseudo-code, since afaik you can't use brackets with __m128i. Still very interesting. The first line appears to say "take an unitialized __m128i (I) and xor it with (parameter) i. Should I read this as initialize I with 0 and xor with i? If so, would it be the same as load I with i and perform a not (operation) on I?
    – Jan
    May 16, 2020 at 11:18
  • 1
    Why should a hash function be reversible? Jan 20 at 0:19
  • 2
    @VioletGiraffe If a hash is not bijective, it means that the output distribution cannot be uniform. If a hash is bijective, it means that it uses as much of the output space as possible. That is why it is recommended that a hash is bijective, making it reversible, but only disregarding computational feasibility. Jan 20 at 11:06
  • 1
    @VioletGiraffe If a hash is bijective it is invertible in principle. That does not mean that it is computationally feasible to invert it. Only very specific applications require that a hash be invertible easily. Crypographic applications require hashes to be very hard to invert. You can have a Bijective hash that is very hard to invert (if you want one let me know how to contact you, this comment is too short). And you can have a non-bijective hash that is easily reversible, up to the ambiguities. Jan 20 at 11:11
  • 1
    I see, thank you, I think now I understand why it's desirable for the hash function to be bijective (regardless of whether or not it is invertible in practice). Jan 20 at 11:48
7

This page lists some simple hash functions that tend to decently in general, but any simple hash has pathological cases where it doesn't work well.

7
  • 32-bits multiplicative method (very fast) see @rafal

    #define hash32(x) ((x)*2654435761)
    #define H_BITS 24 // Hashtable size
    #define H_SHIFT (32-H_BITS)
    unsigned hashtab[1<<H_BITS]  
    .... 
    unsigned slot = hash32(x) >> H_SHIFT
    
  • 32-bits and 64-bits (good distribution) at : MurmurHash

  • Integer Hash Function
0
5

I have been using splitmix64 (pointed in Thomas Mueller's answer) ever since I found this thread. However, I recently stumbled upon Pelle Evensen's rrxmrrxmsx_0, which yielded tremendously better statistical distribution than the original MurmurHash3 finalizer and its successors (splitmix64 and other mixes). Here is the code snippet in C:

#include <stdint.h>

static inline uint64_t ror64(uint64_t v, int r) {
    return (v >> r) | (v << (64 - r));
}

uint64_t rrxmrrxmsx_0(uint64_t v) {
    v ^= ror64(v, 25) ^ ror64(v, 50);
    v *= 0xA24BAED4963EE407UL;
    v ^= ror64(v, 24) ^ ror64(v, 49);
    v *= 0x9FB21C651E98DF25UL;
    return v ^ v >> 28;
}

Pelle also provides an in-depth analysis of the 64-bit mixer used in the final step of MurmurHash3 and the more recent variants.

1
  • 3
    This function is not bijective. For all v where v = ror(v,25), namely all 0 and all 1 it will produce the same output in two places. For all values v = ror64(v, 24) ^ ror64(v, 49), which are at least two more and the same with v = ror(v,28), yielding another 2^4 , totaling around around 22 unnecessary collisions. Two applications of splitmix are probably just as good and just as fast, but still invertible and collision-free. Sep 13, 2019 at 15:02
3

There's a nice overview over some hash algorithms at Eternally Confuzzled. I'd recommend Bob Jenkins' one-at-a-time hash which quickly reaches avalanche and therefore can be used for efficient hash table lookup.

2
  • 4
    That is a good article, but it is focused on hashing string keys, not integers. Jun 17, 2010 at 10:52
  • 1
    Just to be clear, although the methods in the article would work for integers (or could be adapted to), I assume there are more efficient algorithms for integers. Jun 17, 2010 at 11:06
3

For random hash values, some engineers said golden ratio prime number(2654435761) is a bad choice, with my testing results, I found that it's not true; instead, 2654435761 distributes the hash values pretty good.

#define MCR_HashTableSize 2^10

unsigned int
Hash_UInt_GRPrimeNumber(unsigned int key)
{
  key = key*2654435761 & (MCR_HashTableSize - 1)
  return key;
}

The hash table size must be a power of two.

I have written a test program to evaluate many hash functions for integers, the results show that GRPrimeNumber is a pretty good choice.

I have tried:

  1. total_data_entry_number / total_bucket_number = 2, 3, 4; where total_bucket_number = hash table size;
  2. map hash value domain into bucket index domain; that is, convert hash value into bucket index by Logical And Operation with (hash_table_size - 1), as shown in Hash_UInt_GRPrimeNumber();
  3. calculate the collision number of each bucket;
  4. record the bucket that has not been mapped, that is, an empty bucket;
  5. find out the max collision number of all buckets; that is, the longest chain length;

With my testing results, I found that Golden Ratio Prime Number always has the fewer empty buckets or zero empty bucket and the shortest collision chain length.

Some hash functions for integers are claimed to be good, but the testing results show that when the total_data_entry / total_bucket_number = 3, the longest chain length is bigger than 10(max collision number > 10), and many buckets are not mapped(empty buckets), which is very bad, compared with the result of zero empty bucket and longest chain length 3 by Golden Ratio Prime Number Hashing.

BTW, with my testing results, I found one version of shifting-xor hash functions is pretty good(It's shared by mikera).

unsigned int Hash_UInt_M3(unsigned int key)
{
  key ^= (key << 13);
  key ^= (key >> 17);    
  key ^= (key << 5); 
  return key;
}
6
  • 2
    But then why not shift the product right, so you keep the most-mixed bits? That was the way it was supposed to work
    – harold
    Feb 15, 2019 at 12:28
  • 1
    @harold, golden ratio prime number is carefully chosen, though I think it won't make any difference, but I will test to see if it's much better with the "the most-mixed bits". While my point is that "It's not a good choice." is not true, as the testing results show, just grab the lower part of the bits is good enough, and even better than many hash functions. Feb 15, 2019 at 13:18
  • (2654435761, 4295203489) is a golden ratio of primes. Feb 15, 2019 at 13:47
  • (1640565991, 2654435761) is also a golden ratio of primes. Feb 15, 2019 at 14:12
  • @harold, Shifting the product right becomes worse, even if just shifting right by 1 position (divided by 2), it still becomes worse (though still zero empty bucket, but longest chain length is bigger); shifting right by more positions, the result becomes more worse. Why? I think the reason is: shifting the product right makes more hash values not to be coprime, just my guess, the real reason involves number theory. Feb 16, 2019 at 6:29
1

I don't think we can say that a hash function is "good" without knowing your data in advance ! and without knowing what you're going to do with it.

There are better data structures than hash tables for unknown data sizes (I'm assuming you're doing the hashing for a hash table here ). I would personally use a hash table when I Know I have a "finite" number of elements that are needing stored in a limited amount of memory. I would try and do a quick statistical analysis on my data, see how it is distributed etc before I start thinking about my hash function.

1

The answer depends on a lot of things like:

  • Where do you intend to employ it?
  • What are you trying to do with the hash?
  • Do you need a crytographically secure hash function?

I suggest that you take a look at the Merkle-Damgard family of hash functions like SHA-1 etc

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.