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?

Improve this question
$\endgroup$
6
  • 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, 2012 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, 2012 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$
    – didest
    Jan 7, 2012 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, 2012 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, 2012 at 20:31

1 Answer 1

Reset to default
20
$\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.

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ Also, the size of the smallest gap is as large as possible. $\endgroup$
    – Jeffε
    Jan 7, 2012 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.