---
created_at: '2013-08-19T10:43:40.000Z'
title: Integer Hash Function (1997)
url: https://gist.github.com/badboy/6267743
author: antirez
points: 49
story_text: ''
comment_text: 
num_comments: 15
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1376909020
_tags:
- story
- author_antirez
- story_6236473
objectID: '6236473'
year: 1997

---
Original link:
[http://www.concentric.net/~Ttwang/tech/inthash.htm](http://www.concentric.net/%7ETtwang/tech/inthash.htm)  
Taken from:
[http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm](http://web.archive.org/web/20071223173210/http://www.concentric.net/%7ETtwang/tech/inthash.htm)  
Reformatted using pandoc

# [](#integer-hash-function)Integer Hash Function

Thomas Wang, Jan 1997

last update Mar 2007

Version 3.1

## [](#abstract)Abstract

An integer hash function accepts an integer hash key, and returns an
integer hash result with uniform distribution. In this article, we will
be discussing the construction of integer hash functions.

## [](#introduction)Introduction

Hash table is an important data structure. All elementary data structure
text books contain some algorithms of hash table. However, all too often
the treatment of hash function is discussed as an after-thought. Thus
examples abound in systems where the poor choice of the hash function
resulted in inferior performance.

Certainly the integer hash function is the most basic form of the hash
function. The integer hash function transforms an integer hash key into
an integer hash result. For a hash function, the distribution should be
uniform. This implies when the hash result is used to calculate hash
bucket address, all buckets are equally likely to be picked. In
addition, similar hash keys should be hashed to very different hash
results. Ideally, a single bit change in the hash key should influence
all bits of the hash
result.

## [](#hash-function-construction-principles)Hash Function Construction Principles

A good mixing function must be reversible. A hash function has form h(x)
-\> y. If the input word size and the output word size are identical,
and in addition the operations in h() are reversible, then the following
properties are true.

1.  If h(x1) == y1, then there is an inverse function h\_inverse(y1) ==
    x1
2.  Because the inverse function exists, there cannot be a value x2 such
    that x1 \!= x2, and h(x2) == y1.

The case of h(x1) == y1, and h(x2) == y1 is called a collision. Using
only reversible operations in a hash function makes collisions
impossible. There is an one-to-one mapping between the input and the
output of the mixing function.

Beside reversibility, the operations must use a chain of computations to
achieve avalanche. Avalanche means that a single bit of difference in
the input will make about 1/2 of the output bits be different. At a
point in the chain, a new result is obtained by a computation involving
earlier results.

For example, the operation a = a + b is reversible if we know the value
of 'b', and the after value of 'a'. The before value of 'a' is obtained
by subtracting the after value of 'a' with the value of 'b'.

## [](#knuths-multiplicative-method)Knuth's Multiplicative Method

In Knuth's "The Art of Computer Programming", section 6.4, a
multiplicative hashing scheme is introduced as a way to write hash
function. The key is multiplied by the golden ratio of 2^32 (2654435761)
to produce a hash result.

Since 2654435761 and 2^32 has no common factors in common, the
multiplication produces a complete mapping of the key to hash result
with no overlap. This method works pretty well if the keys have small
values. Bad hash results are produced if the keys vary in the upper
bits. As is true in all multiplications, variations of upper digits do
not influence the lower digits of the multiplication
result.

## [](#robert-jenkins-96-bit-mix-function)Robert Jenkins' 96 bit Mix Function

[Robert
Jenkins](/web/20071223173210/http://www.burtleburtle.net/bob/hash/doobs.html)
has developed a hash function based on a sequence of subtraction,
exclusive-or, and bit shift.

All the sources in this article are written as Java methods, where the
operator '\>\>\>' represents the concept of unsigned right shift. If the
source were to be translated to C, then the Java 'int' data type should
be replaced with C 'uint32\_t' data type, and the Java 'long' data type
should be replaced with C 'uint64\_t' data type.

The following source is the mixing part of the hash function.

    int mix(int a, int b, int c)
    {
      a=a-b;  a=a-c;  a=a^(c >>> 13);
      b=b-c;  b=b-a;  b=b^(a << 8);
      c=c-a;  c=c-b;  c=c^(b >>> 13);
      a=a-b;  a=a-c;  a=a^(c >>> 12);
      b=b-c;  b=b-a;  b=b^(a << 16);
      c=c-a;  c=c-b;  c=c^(b >>> 5);
      a=a-b;  a=a-c;  a=a^(c >>> 3);
      b=b-c;  b=b-a;  b=b^(a << 10);
      c=c-a;  c=c-b;  c=c^(b >>> 15);
      return c;
    }

Variable 'c' contains the input key. When the mixing is complete,
variable 'c' also contains the hash result. Variable 'a', and 'b'
contain initialized random bits. Notice the total number of internal
state is 96 bits, much larger than the final output of 32 bits. Also
notice the sequence of subtractions rolls through variable 'a' to
variable 'c' three times. Each row will act on one variable, mixing in
information from the other two variables, followed by a shift operation.

Subtraction is similar to multiplication in that changes in upper bits
of the key do not influence lower bits of the addition. The 9 bit shift
operations in Robert Jenkins' mixing algorithm shifts the key to the
right 61 bits in total, and shifts the key to the left 34 bits in total.
As the calculation is chained, each exclusive-or doubles the number of
states. There are at least 2^9 different combined versions of the
original key, shifted by various amounts. That is why a single bit
change in the key can influence widely apart bits in the hash result.

The uniform distribution of the hash function can be determined from the
nature of the subtraction operation. Look at a single bit subtraction
operation between a key, and a random bit. If the random bit is 0, then
the key remains unchanged. If the random bit is 1, then the key will be
flipped. A carry will occur in the case where both the key bit and the
random bit are 1. Subtracting the random bits will cause about half of
the key bits to be flipped. So even if the key is not uniform,
subtracting the random bits will result in uniform distribution.

## [](#32-bit-mix-functions)32 bit Mix Functions

Based on an original suggestion on Robert Jenkin's part in 1997, I have
done some research for a version of the integer hash function. This is
my latest version as of January 2007. The specific value of the bit
shifts are obtained from running the accompanied search program.

    public int hash32shift(int key)
    {
      key = ~key + (key << 15); // key = (key << 15) - key - 1;
      key = key ^ (key >>> 12);
      key = key + (key << 2);
      key = key ^ (key >>> 4);
      key = key * 2057; // key = (key + (key << 3)) + (key << 11);
      key = key ^ (key >>> 16);
      return key;
    }

(~x) + y is equivalent to y - x - 1 in two's complement representation.

By taking advantages of the native instructions such as 'add
complement', and 'shift & add', the above hash function runs in 11
machine cycles on HP 9000 workstations.

Having more rounds will strengthen the hash function by making the
result more random looking, but performance will be slowed down
accordingly. Simulation seems to prefer small shift amounts for inner
rounds, and large shift amounts for outer
rounds.

## [](#robert-jenkins-32-bit-integer-hash-function)Robert Jenkins' 32 bit integer hash function

    uint32_t hash( uint32_t a)
    {
       a = (a+0x7ed55d16) + (a<<12);
       a = (a^0xc761c23c) ^ (a>>19);
       a = (a+0x165667b1) + (a<<5);
       a = (a+0xd3a2646c) ^ (a<<9);
       a = (a+0xfd7046c5) + (a<<3);
       a = (a^0xb55a4f09) ^ (a>>16);
       return a;
    }

This version of integer hash function uses operations with integer
constants to help producing a hash value. I suspect the actual values of
the magic constants are not very important. Even using 16 bit constants
may still work pretty well.

These magic constants open up the construction of perfect integer hash
functions. A test program can vary the magic constants until a set of
perfect hashes are found.

## [](#using-multiplication-for-hashing)Using Multiplication for Hashing

Using multiplication requires a mechanism to transport changes from high
bit positions to low bit positions. Bit reversal is best, but is slow to
implement. A viable alternative is left shifts.

Using multiplication presents some sort of dilemma. Certain machine
platforms supports integer multiplication in hardware, and an integer
multiplication can be completed in 4 or less cycles. But on some other
platforms an integer multiplication could take 8 or more cycles to
complete. On the other hand, integer hash functions implemented with bit
shifts perform equally well on all platforms.

A compromise is to multiply the key with a 'sparse' bit pattern, where
on machines without fast integer multiplier they can be replaced with a
'shift & add' sequence. An example is to multiply the key with (4096 + 8

  - 1), with an equivalent expression of (key + (key \<\< 3)) + (key
    \<\< 12).

On most machines a bit shift of 3 bits or less, following by an addition
can be performed in one cycle. For example, Pentium's 'lea' instruction
can be used to good effect to compute a 'shift & add' in one cycle.

Function hash32shiftmult() uses a combination of bit shifts and integer
multiplication to hash the input key.

    public int hash32shiftmult(int key)
    {
      int c2=0x27d4eb2d; // a prime or an odd constant
      key = (key ^ 61) ^ (key >>> 16);
      key = key + (key << 3);
      key = key ^ (key >>> 4);
      key = key * c2;
      key = key ^ (key >>> 15);
      return key;
    }

## [](#64-bit-mix-functions)64 bit Mix Functions

    public long hash64shift(long key)
    {
      key = (~key) + (key << 21); // key = (key << 21) - key - 1;
      key = key ^ (key >>> 24);
      key = (key + (key << 3)) + (key << 8); // key * 265
      key = key ^ (key >>> 14);
      key = (key + (key << 2)) + (key << 4); // key * 21
      key = key ^ (key >>> 28);
      key = key + (key << 31);
      return key;
    }

The longer width of 64 bits require more mixing than the 32 bit version.

## [](#64-bit-to-32-bit-hash-functions)64 bit to 32 bit Hash Functions

One such use for this kind of hash function is to hash a 64 bit virtual
address to a hash table index. Because the output of the hash function
is narrower than the input, the result is no longer one-to-one.

Another usage is to hash two 32 bit integers into one hash value.

    public int hash6432shift(long key)
    {
      key = (~key) + (key << 18); // key = (key << 18) - key - 1;
      key = key ^ (key >>> 31);
      key = key * 21; // key = (key + (key << 2)) + (key << 4);
      key = key ^ (key >>> 11);
      key = key + (key << 6);
      key = key ^ (key >>> 22);
      return (int) key;
    }

## [](#parallel-operations)Parallel Operations

If a CPU can dispatch multiple instructions in the same clock cycle, one
can consider adding more parallelism in the formula.

For example, for the following formula, the two shift operations can be
performed in parallel. On certain platforms where there are multiple
ALUs but a single shifter unit, this idea does not offer a speed
increase.

    key ^= (key << 17) | (key >>> 16);

For 32 bit word operations, only certain pairs of shift amounts will be
reversible. The valid pairs include: (17,16) (16,17) (14,19) (19,14)
(13,20) (20,13) (10,23) (23,10) (8,25) (25,8)

Multiplication can be computed in parallel. Any multiplication with odd
number is reversible.

    key += (key << 3) + (key << 9); // key = key * (1 + 8 + 512)

On certain machines, bit rotation can be performed in one cycle. Any odd
number bits rotation can be made reversible when exclusive-or is applied
to the un-rotated key with one particular bit set to 1 or 0.

    key = (key | 64) ^ ((key >>> 15) | (key << 17));

However, on certain machine and compiler combinations, this code
sequence can run as slow as 4 cycles. 2 cycles: a win, 3 cycles: tie,
more than 3 cycles: a loss.

## [](#pseudo-random-usages)Pseudo Random Usages

There has been queries whether these mix functions can be used for
pseudo random purposes. Although the out does look random to the naked
eye, the official recommendation is to use a real pseudo random number
generator instead, such as the [Mercenne
Twister](/web/20071223173210/http://www.math.sci.hiroshima-u.ac.jp/%7Em-mat/MT/emt.html).

The hash functions listed in this article were only tested for hashing
purpose. No tests of randomness were performed.

## [](#test-program)Test Program

This is a [test
program](/web/20071223173210/http://www.concentric.net/%7ETtwang/tech/testchange.java)
testing the choices of the shift amounts with regard to the resulting
avalanche property. The program detects if a certain bit position has
both changes and no changes, based on a single bit flip. Promising
candidates are further tested to verify the percentage chance of bit
flip is sufficiently close to 50% for all input and output bit pairs.

The test program prints out the name of the algorithm under test,
followed by the list of shift amounts that pass the avalanche test.

## [](#power-of-2-hash-table-size)Power of 2 Hash Table Size

Programmer uses hash table size that is power of 2 because address
calculation can be performed very quickly. The integer hash function can
be used to post condition the output of a marginal quality hash function
before the final address calculation is done.

    addr = inthash(marginal_hash_value) & (tablesize - 1);

Using the inlined version of the integer hash function is faster than
doing a remaindering operation with a prime number\! An integer
remainder operation may take up to 18 cycles or longer to complete,
depending on machine architecture.

## [](#conclusions)Conclusions

In this article, we have examined a number of hash function construction
algorithms. Knuth's multiplicative method is the simplest, but has some
known defects. Robert Jenkins' 96 bit mix function can be used as an
integer hash function, but is more suitable for hashing long keys. A
dedicated hash function is well suited for hashing an integer number.

We have also presented an application of the integer hash function to
improve the quality of a hash value.

Give feedbacks to <wang@cup.hp.com>
