Fibonacci Hash

June 19, 2018

Hash tables are ubiquitous in computing, and we’ve both used and implemented hash tables on several occasions; there is even a hash table implementation in the Standard Prelude. Most hash tables nowadays use the elements of an array as the heads of linked lists that store key/value pairs, so to access (store or fetch) a particular element the procedure is to calculate the hash value based on the key, convert the hash value to an index into the array, and scan down the appropriate linked list until you find the desired item.

The usual way to convert the hash value to an array index is to choose the array size prime, then take the hash value modulo the prime. That can be slow, because the modulo operation requires a division, which is always slow compared to other primitive arithmetic operations. Fibonacci hash replaces the division with multiplication and a shift, which often takes less than half the time.

Fibonacci hash works like this: Choose b the number of bits in an integer, usually either 32 or 64. Then compute 2b ÷ φ, where φ = (1 + √5) ÷ 2 ≈ 1.618; for b = 32 this quantity is 2654435769 and for b = 64 this quantity is 11400714819323198485. Then to compute the array index, multiply the hash value by the quantity shown above, allowing it to wrap around if the product exceeds the integer bounds, and shift right, leaving as many bits as desired. The array size should be a power of 2. Here is an implementation in C:

unsigned long long fibhash(unsigned long long h)
{
return (h * 11400714819323198485ull) >> 54
}

This returns a ten-bit value (since the 64 bit product is shifted right 54 bits) from 0 inclusive to 1024 exclusive, which is used as the index to the array. If you need more bits, just change the size of the shift.

Malte Skarupke describes the theory behind Fibonacci hash, which you should look at, because it includes some neat math; be sure not to miss the linked video from Vi Hart.

Your task is to implement Fibonacci hash in the language of your choice. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

3 Responses to “Fibonacci Hash”

  1. Daniel said

    Here’s a solution in Haskell.

    import Data.Bits

    fibhash :: Word -> Word
    fibhash h = (h * 11400714819323198485) `shiftR` 54

    Example (excluding out-of-range literal warning):

    > fibhash 123412341234
    831
    > fibhash 12341234123412341234
    269
    > fibhash 1234123412341234123412341234
    20
    
  2. Daniel said

    Formatted:

    import Data.Bits
    
    fibhash :: Word -> Word
    fibhash h = (h * 11400714819323198485) `shiftR` 54
    
  3. Milbrae said

    Another implementation in D

    import std.stdio;
    
    ulong fibhash(ulong n, ulong mul=11400714819323198485UL, ulong shift=54UL) {
    	return (n * mul) >> shift;
    }
    
    void main() {
    	1234567890UL.fibhash.writeln;
    }

    449

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: