9
$\begingroup$

When interpreting keys as natural numbers we can use the following formula.

\begin{equation} h(k) = \lfloor m (kA\bmod{1}) \rfloor \end{equation}

What I am having trouble understanding is how we choose the value of A where:

\begin{equation} 0 < A < 1 \end{equation}

According to Knuth an optimal value is:

\begin{equation} A \thickapprox (\sqrt{5} - 1) / 2 = 0.6180339887... \end{equation}

So my question is how did Knuth come to this and how could I calculate an optimum value for my specific data?

$\endgroup$
  • 3
    $\begingroup$ I just find it interesting that $A = 1+\phi$ ... and googling that actually brought a reference to "Knuth argues that repeated multiplication by the golden ratio will minimize gaps in the hash space, and thus it's a good choice for combining together multiple keys to form one." $\endgroup$ – Ahmed Masud Jan 6 '12 at 20:28
  • 1
    $\begingroup$ If I recall correctly it's explained in one of the exercises in what sense $kA \mod 1$ are nicely spread in the unit interval. I don't have the book now to check, though. $\endgroup$ – Radu GRIGore Jan 7 '12 at 1:09
  • 1
    $\begingroup$ @RaduGRIGore it's a well-known theorem that $A, 2A, \ldots$ is uniformly-distributed modulo $1$ for any irrational $A$ (theorem 6.3 of Niven's "Irrational Numbers"). Perhaps $A=1+\phi$ is the best choice in some sense. $\endgroup$ – Diego de Estrada Jan 7 '12 at 2:30
  • 2
    $\begingroup$ There is no such thing as "more optimum"; that's like saying "more best". Either it is the optimum value or it isn't. $\endgroup$ – Jeffε Jan 7 '12 at 18:45
  • 2
    $\begingroup$ It's worth pointing out that this value is also used by natural processes. Specifically, the golden angle governs the placement of petals, florets, etc. in many plants. A rotation by this angle can be applied repeatedly when placing points around a circle and the points will be evenly spaced (within a constant factor). $\endgroup$ – James King Jan 7 '12 at 20:31
19
$\begingroup$

See exercise 9 of section 6.4 of The Art of Computer Programming.

Any irrational $A$ would work, because $\{kA\}$ breaks up a largest gap of $\{A\}, \{2A\}, \ldots, \{(k-1)A\}$ (I use the notation $\{x\}$ for $x\mod 1$).

But if $A = \phi^{-1}$ or $A = \phi^{-2}$, it has a special property: these are the only values for which neither of the two newly created gaps is more than twice as long as the other.

$\endgroup$
  • 7
    $\begingroup$ Also, the size of the smallest gap is as large as possible. $\endgroup$ – Jeffε Jan 7 '12 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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