Универсальное хеширование
Для вычисления вероятности коллизий с S строками длины L с W битами на символ для хеша длины H битов, предполагая оптимальный универсальный хэш ( 1 ) Вы можете рассчитать вероятность столкновения на основе хеш-таблицы размера (количества сегментов) 'N`.
Прежде всего, мы можем предположить идеальную реализацию хеш-таблицы ( 2 ), которая идеально разбивает H бит в хэше на доступные сегменты N ( 3 ). Это означает, что H становится бессмысленным, кроме как ограничение для N.
W и 'L' являются просто основой для верхней границы S. Для более простой математики предположим, что строки длиной <<code>L просто дополняются до L специальным нулевым символом. Если нас интересовало, нас интересует наихудший случай, это 54 ^ L (26 * 2 + '_' + null), просто это смешное число, фактическое количество записей более полезно, чем набор символов и длина, поэтому мы просто будем работать так, как если бы S была переменной сама по себе.
Мы пытаемся поместить S предметов в N ведра.
Тогда это становится очень известной проблемой, парадоксом дня рождения
Решение этой проблемы для различных вероятностей и количества сегментов является поучительным , но если предположить, что у нас есть 1 миллиард блоков (то есть около 4 ГБ памяти в 32-битной системе), тогда нам потребуется только 37 КБ записей, прежде чем мы достигнем 50% -й шанс того, что они будут хотя бы одним столкновением. Учитывая, что пытаться избежать любых столкновений в хеш-таблице становится просто абсурдом.
Все это не означает, что нам не следует заботиться о поведении наших хеш-функций. Очевидно, что эти числа предполагают идеальные реализации , они являются верхней границей того, насколько хорошо мы можем получить. Плохая хэш-функция может привести к гораздо худшим коллизиям в некоторых областях, тратить часть возможного «пробела», никогда или редко используя его, что может привести к тому, что хеш-функции будут меньше оптимальных, и даже ухудшится до производительности, которая выглядит как список, но с гораздо хуже постоянных факторов.
Реализация .NET Framework хеш-функции строки невелика (в том смысле, что она могла бы быть лучше), но, вероятно, приемлема для подавляющего большинства пользователей и достаточно эффективна для вычисления.
Альтернативный подход: идеальное хеширование
Если вы хотите, чтобы вы могли генерировать так называемые совершенные хэши , это требует полного знания заранее введенных значений, однако это не часто бывает полезно. По аналогии с вышеприведенной математикой мы можем показать, что даже идеальное хеширование имеет свои пределы:
Напомним ограничение в 54 ^ L строк длиной L. Однако у нас есть только H битов (предположим, 32), что составляет около 4 миллиардов различных чисел. Так что если вы можете иметь действительно любую строку и любое их количество, тогда вы должны удовлетворить:
54 ^ L <= 2 ^ 32
И ее решение:
log2 (54 ^ L) <= 32
L * log2 54 <= 32
L <= 32 / log2 54 <= 5.56
Поскольку длины строк явно не могут быть дробными, максимальная длина у вас остается всего 5. Действительно, очень короткая.
Если вы знаете, что у вас когда-нибудь будет только набор строк размером менее 4 миллиардов, то идеальное хеширование позволит вам обработать любое значение L, но на практике ограничение набора значений может быть очень трудным, и вы должен знать их все заранее или ухудшить до того, что составляет базу данных строк -> хэш и добавить к ней при обнаружении новых строк.
Для этого упражнения универсальный хеш является оптимальным, так как мы хотим уменьшить вероятность любого столкновения, т. Е. Для любого входа вероятность его выхода x из набора возможностей R равна 1 /. Р.
Обратите внимание, что выполнить оптимальную работу по хешированию (и внутреннему группированию) довольно сложно, но следует ожидать, что встроенные типы будут разумными, если не всегда идеальными.
В этом примере я избежал вопроса о закрытой и открытой адресации. Это имеет некоторое отношение к вероятностям, вовлеченным, но не значительно