Math
Хеши и корзины
Сортировочный стол: ключи — бумажные бирки, каретка хеширует каждую и бросает в корзину с номером хеша, коллизия — два разных ключа в одной корзине. Хеш — именованная функция: сумма кодов, многочлен с основанием 31, FNV-1a — или равномерный оракул, стоящий за кривой дней рождения. Отредактируй ключ, посмотри вычисление хеша по символам, переверни один бит и сосчитай сдвинувшиеся биты хеша; сравни две функции на одних ключах.
Что происходит
Двадцать три человека в комнате чаще делят день рождения, чем нет, и та же арифметика задаёт размер хеш-таблицы. Здесь ключи — настоящие строки, а хеш — ИМЕНОВАННАЯ функция: сумма кодов символов, многочлен с основанием 31, FNV-1a — или равномерный оракул, у которого нет ключа вовсе и который стоит за кривой. Каретка на рельсе хеширует бирку и бросает её в корзину с номером-индексом; бирка, упавшая на другую, — коллизия, и оба ключа остаются подсвеченными. Лист считает хеш пробного ключа по символам, переворачивает один бит ключа и считает сдвинувшиеся биты хеша. Три вопроса разведены: коллизии, равномерность (χ² загрузок против n/m, ожидание m − 1) и лавина; гистограмма, ровная на случайных словах, — не приговор функции: дай сумме букв список анаграмм, и все ключи лягут в одну корзину. Ничто из этого — не криптостойкость.
Уравнения модуля
Уравнения n ключей равномерно по m корзинам P(хотя бы одна коллизия) = 1 − произведение (1 − i/m), ТОЧНО: n = 23, m = 365 -> 0.50729723432398566; n = 50 -> 0.97037357957798842 ожидаемое число пустых корзин = m·(1 − 1/m)^n ТОЧНО - а не привычное m·e^(−n/m): при n = m = 100 они равны 36.603234127322921 и 36.787944, и разница заметна ключей до первой коллизии в среднем: sqrt(pi·m/2) + 2/3 = 24.611199639354552 при m = 365 (по подсчёту 24.6767 за 20 000 запусков) максимальная нагрузка при n = m ведёт себя как ln n / ln ln n - это АСИМПТОТИКА, а не формула: измеренное отношение РАСТЁТ, 1.32 при m = 64, 1.49 при 256, 1.55 при 1024 поэтому она проверяется как двусторонняя оценка и как монотонная тенденция, но никогда не сравнивается с одним числом измерено по сравнению с точной кривой (по 20 000 запусков): n = 10 -> 0.11605 против 0.11695; n = 23 -> 0.50800 против 0.50730; n = 70 -> 0.99920 против 0.99916 именованные функции от ключа k = c₁c₂…c_n (коды символов), все по модулю 2³²: сумма: h = Σ c_i; основание 31: h ← 31·h + c_i; FNV-1a: h₀ = 2166136261, h ← (h исключающее ИЛИ c_i)·16777619 корзина = h mod m; равномерный оракул берёт корзину из начального значения генератора и НОМЕРА ключа - самого ключа у него нет равномерность: χ² = Σ (load_j − n/m)² / (n/m) по m корзинам; равномерная раздача даёт m − 1 ± √(2(m − 1)) лавинный эффект: среднее по ключам от Hamming(h(k), h(k′)) при изменении ОДНОГО бита ключа k; идеальная функция меняет 16 из 32 измерено (начальное значение 20260913, 40 случайных слов по 64 корзинам): FNV-1a 7 коллизий, χ² 46.4, лавинный эффект 14.6; основание 31: 9, 52.8, 6.2; сумма: 8, 52.8, 2.05; оракул: 9, 59.2, без битов 40 анаграмм одного слова при суммировании: 39 коллизий, одна цепочка из 40, χ² = 2520 - сумма не различает порядок букв
