Вопрос 5: Хеширование как обобщение для хранения множества в массиве битов
Хеш-таблица — это обобщение способа хранения множества целых чисел (ключей) в форме вектора битов на случай, когда мощность универсума U очень велика по отношению к мощности множеств, с которыми нужно работать. Функция отображения преобразует значения ключей к интервалу [0, m – 1], где m — размер хеш-таблицы, m ≪ |U|. Очевидно, что при этом каждому индексу хеш-таблицы будет соответствовать много различных значений ключей. Поэтому, во-первых, в хеш-таблице приходится хранить не биты, а сами значения ключей, а во-вторых, имеется возможность размещать в ней более одного ключа для каждого значения функции отображения (разрешать коллизии).
Количество возможных коллизий можно уменьшить, если выполнить два условия:
Выбрать размер хеш-таблицы с запасом:
Если размер таблицы превышает мощность хранимого множества более чем вдвое, вероятность коллизии становится меньше 0,5. Если мощность множества заранее неизвестна, то выбирают некоторый начальный размер, а когда его оказывается недостаточно, таблицу перестраивают с увеличением размера (обычно вдвое);
Подобрать определённую функцию отображения (хеш-функцию):
Такую, чтобы все ячейки таблицы были востребованы по возможности с равной вероятностью, независимо от того какое распределение имеют хранящиеся в таблице ключи;