 Data Structures and Algorithms with Object-Oriented Design Patterns in C++     ## Fibonacci Hashing

The final variation of hashing to be considered here is called the Fibonacci hashing method  . In fact, Fibonacci hashing is exactly the multiplication hashing method discussed in the preceding section using a very special value for a. The value we choose is closely related to the number called the golden ratio.

The golden ratio  is defined as follows: Given two positive numbers x and y, the ratio is the golden ratio if the ratio of x to y is the same as that of x+y to x. The value of the golden ratio can be determined as follows: There is an intimate relationship between the golden ratio and the Fibonacci numbers . In Section it was shown that the Fibonacci number is given by where and !

In the context of Fibonacci hashing, we are interested not in , but in the reciprocal, , which can be calculated as follows: The Fibonacci hashing method is essentially the multiplication hashing method in which the constant a is chosen as the integer that is relatively prime to W which is closest to . The following table gives suitable values of a for various word sizes.

 W a 40503 2654435769 11400714819323198485

Why is special? It has to do with what happens to consecutive keys when they are hashed using the multiplicative method. As shown in Figure , consecutive keys are spread out quite nicely. In fact, when we use to hash consecutive keys, the hash value for each subsequent key falls in between the two widest spaced hash values already computed. Furthermore, it is a property of the golden ratio, , that each subsequent hash value divides the interval into which it falls according to the golden ratio! Figure: Fibonacci Hashing      Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.