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 - сума не розрізняє порядок літер
