Как Кнут узнал А?

При интерпретации ключей как натуральных чисел мы можем использовать следующую формулу.

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

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

Что мне трудно понять, так это то, как мы выбираем значение A, где:

0 < A < 1

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

Согласно Кнуту оптимальное значение:

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

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

Итак, мой вопрос: как Кнут пришел к этому и как я мог рассчитать оптимальное значение для моих конкретных данных?

hash-function ChaosPandion
источник

Мне просто интересно, что

A = 1 + ϕ

$A = 1+\phi$ ... и поиск в Google, который фактически привел ссылку на «Кнут утверждает, что повторное умножение на золотое сечение минимизирует разрывы в хэш-пространстве, и, таким образом, это хороший выбор для объединения нескольких ключей в один».

Ахмед Масуд

Если я правильно помню, это объяснялось в одном из упражнений, в каком смысле хорошо распределены в единичном интервале. У меня сейчас нет книги, чтобы проверить.

k A \mod 1

$kA \mod 1$

Раду GRIGore

@RaduGRIG. Это хорошо известная теорема о том что равномерно распределены по модулю для любого иррационального (теорема 6.3 «Нерациональных чисел» Нивена). Возможно, - лучший выбор в некотором смысле.

A, 2 A, \dots

$A, 2A, \ldots$

1

$1$

A

$A$

A = 1 + ϕ

$A=1+\phi$

didest

Нет такой вещи, как «более оптимальный»; это все равно что сказать "лучше". Либо это оптимальное значение, либо нет.

Джефф

Стоит отметить, что это значение также используется естественными процессами. В частности, золотой угол определяет расположение лепестков, цветочков и т. Д. На многих растениях. Поворот на этот угол может применяться несколько раз при размещении точек вокруг круга, и точки будут равномерно распределены (с постоянным коэффициентом).

Джеймс Кинг

См. Упражнение 9 раздела 6.4 «Искусство компьютерного программирования» .

Любой иррациональный будет работать, потому что разбивает наибольший разрыв (я использую обозначение для ). $A$ $\{kA\}$ $\{A\}, \{2A\}, \ldots, \{(k-1)A\}$ $\{x\}$ $x\mod 1$

Но если или , у него есть специальное свойство: это единственные значения, для которых ни один из двух вновь созданных пробелов не более чем в два раза длиннее, чем Другой. $A = \phi^{-1}$ $A = \phi^{-2}$

didest
источник

Кроме того, размер наименьшего зазора максимально велик.

Джеффс

Как Кнут узнал А?

Ответы: