Programming Praxis

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 2^b ÷ φ, 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.

Pages: 1 2