Comment Knuth a-t-il dérivé A?

Lorsque nous interprétons les clés comme des nombres naturels, nous pouvons utiliser la formule suivante.

h (k) = ⌊ m (k A mod 1) ⌋

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

Ce que j'ai du mal à comprendre, c'est comment nous choisissons la valeur de A où:

0 < A < 1

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

Selon Knuth, une valeur optimale est:

A \approx (\sqrt{5} - 1) / 2 = 0.6180339887...

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

Donc, ma question est de savoir comment Knuth est arrivé à cela et comment pourrais-je calculer une valeur optimale pour mes données spécifiques?

hash-function ChaosPandion
la source

Je trouve juste intéressant que

A = 1 + ϕ

$A = 1+\phi$ ... et googler qui a en fait fait référence à "Knuth fait valoir que la multiplication répétée par le nombre d'or minimisera les écarts dans l'espace de hachage, et c'est donc un bon choix pour combiner ensemble plusieurs clés pour en former un. "

Ahmed Masud

Si je me souviens bien, cela est expliqué dans l'un des exercices dans quel sens est bien réparti dans l'intervalle unitaire. Je n'ai pas le livre à vérifier maintenant.

k A \mod 1

$kA \mod 1$

Radu GRIGore

@RaduGRIGore c'est un théorème bien connu que est un modulo uniformément distribué pour tout irrationnel (théorème 6.3 des "Nombres irrationnels" de Niven). Peut-être que est le meilleur choix dans un certain sens.

A, 2 A, \dots

$A, 2A, \ldots$

1

$1$

A

$A$

A = 1 + ϕ

$A=1+\phi$

didest

Il n'y a pas de "plus optimal"; c'est comme dire "plus mieux". Soit c'est la valeur optimale, soit ce n'est pas le cas.

Jeffε

Il convient de souligner que cette valeur est également utilisée par les processus naturels. Plus précisément, l' angle doré régit le placement des pétales, des fleurons, etc. dans de nombreuses plantes. Une rotation de cet angle peut être appliquée à plusieurs reprises lorsque vous placez des points autour d'un cercle et les points seront régulièrement espacés (dans un facteur constant).

James King

Comment Knuth a-t-il dérivé A?

Réponses: