Jak Knuth wyprowadził A?

Interpretując klucze jako liczby naturalne, możemy użyć następującej formuły.

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

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

Trudno mi zrozumieć, w jaki sposób wybieramy wartość A, gdzie:

0 < A < 1

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

Według Knutha optymalna wartość to:

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

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

Więc moje pytanie brzmi: jak do tego doszedł Knuth i jak mogę obliczyć optymalną wartość dla moich konkretnych danych?

hash-function

— ChaosPandion
źródło

Po prostu uważam za interesujące, że ... i googlowanie, które faktycznie przyniosło odniesienie do „Knuth twierdzi, że wielokrotne mnożenie przez złoty współczynnik zminimalizuje luki w przestrzeni mieszania, a zatem jest to dobry wybór do łączenia razem wiele kluczy, aby utworzyć jeden ”.

A = 1 + ϕ

$A = 1+\phi$

— Ahmed Masud

Jeśli dobrze pamiętam, wyjaśniono to w jednym z ćwiczeń, w którym sensie są ładnie rozłożone w przedziale jednostkowym. Jednak nie mam teraz książki do sprawdzenia.

k A \mod 1

$kA \mod 1$

— Radu GRIGore

@RaduGRIGore to dobrze znane twierdzenie, że jest równomiernie rozłożonym modułem dla dowolnego irracjonalnego (twierdzenie 6.3 „Liczb nieracjonalnych” Niven). Być może jest w pewnym sensie najlepszym wyborem.

A, 2 A, \dots

$A, 2A, \ldots$

1

$1$

A

$A$

A = 1 + ϕ

$A=1+\phi$

— zrobił

Nie ma czegoś takiego jak „bardziej optymalny”; to tak, jakby powiedzieć „lepiej”. Albo jest to optymalna wartość, albo nie.

— Jeffε

Warto zauważyć, że z tej wartości korzystają również naturalne procesy. W szczególności złoty kąt reguluje umieszczanie płatków, różyczek itp. W wielu roślinach. Obracanie o ten kąt może być stosowane wielokrotnie podczas umieszczania punktów wokół koła, a punkty będą równomiernie rozmieszczone (w ramach stałego współczynnika).

— James King

Zobacz ćwiczenie 9 w sekcji 6.4 sztuki programowania komputerowego .

Wszelkie irracjonalne działałoby, ponieważ niszczy największą lukę (używam notacji dla ). $A$ $\{kA\}$ $\{A\}, \{2A\}, \ldots, \{(k-1)A\}$ $\{x\}$ $x\mod 1$

Ale jeśli lub , ma specjalną właściwość: są to jedyne wartości, dla których żadna z dwóch nowo utworzonych luk nie jest ponad dwukrotnie dłuższa niż inny. $A = \phi^{-1}$ $A = \phi^{-2}$

— didest
źródło

Również rozmiar najmniejszej szczeliny jest tak duży, jak to możliwe.

— Jeffε