Введение
Хаш-функция без коллизий
В информатике, совершенная хеш-функция h для множества S — это хеш-функция, которая отображает различные элементы из S в множество из m целых чисел без коллизий. В математических терминах, это инъективная функция. Совершенные хеш-функции могут использоваться для реализации таблицы поиска с постоянным временем доступа в худшем случае. Совершенная хеш-функция, как и любая другая хеш-функция, может использоваться для реализации хеш-таблиц, с тем преимуществом, что не требуется реализовывать обработку коллизий. Кроме того, если ключи не содержатся в данных и известно, что запрошенные ключи будут валидными, то сами ключи не нужно хранить в таблице поиска, что позволяет экономить место. Недостатком совершенных хеш-функций является то, что множество S должно быть известно для построения совершенной хеш-функции. Нединамические совершенные хеш-функции необходимо перестраивать при изменении S. Для часто изменяющихся S можно использовать динамические совершенные хеш-функции, но это требует дополнительных затрат памяти.
Динамическая идеальная хешировка
Использование идеальной хэш-функции наиболее эффективно в ситуациях, когда требуется часто обращаться к большому набору данных S, который редко изменяется. Это объясняется тем, что любое изменение набора S может привести к потере свойства идеальности хэш-функции для измененного набора. Методы, которые обновляют хэш-функцию при каждом изменении набора, называются динамическим идеальным хешированием, однако они относительно сложны в реализации.
Минимальная идеальная хеш-функция
Минимально совершенная хеш-функция — это совершенная хеш-функция, которая отображает n ключей в n последовательных целых чисел – обычно числа от 0 до n − 1 или от 1 до n. Более формально это можно выразить так: пусть j и k — элементы некоторого конечного множества S. Тогда h является минимально совершенной хеш-функцией тогда и только тогда, когда h(j) = h(k) влечет за собой j = k (инъективность), и существует целое число a, такое что область значений h равна [a, a+n-1]. Доказано, что универсальная схема минимального совершенного хеширования требует не менее ⌈log₂n⌉ битов на ключ. Предполагая, что S — множество размера n, содержащее целые числа в диапазоне [0, N], известно, как эффективно построить явную минимально совершенную хеш-функцию из S в [0, n-1], которая использует O(n) битов памяти и поддерживает константное время вычисления. На практике существуют схемы минимального совершенного хеширования, которые используют примерно 1,56 бита на ключ, если предоставлено достаточно времени.
Сохранение заказа
Минимальная идеальная хеш-функция F сохраняет порядок, если ключи заданы в некотором порядке a1, a2, ..., an и для любых ключей aj и ak, j < k влечет за собой F(aj) < F(ak). В этом случае значение функции – это просто позиция каждого ключа в отсортированном порядке всех ключей. Простой способ реализации сохраняющих порядок минимальных идеальных хеш-функций с постоянным временем доступа – использовать (обычную) идеальную хеш-функцию для хранения таблицы поиска позиций каждого ключа. Это решение требует битов, что оптимально в ситуации, когда функция сравнения для ключей может быть произвольной. Однако, если ключи a1, a2, ..., an – целые числа, взятые из множества , то можно построить сохраняющую порядок хеш-функцию, используя только битов памяти. Более того, эта граница известна как оптимальная.
Связанные конструкции
В то время как хорошо спроектированные хэш-таблицы обеспечивают амортизированное среднее время O(1) (амортизированное среднее постоянное время) для поиска, вставки и удаления, большинство алгоритмов хэш-таблиц подвержены возможным временам в худшем случае, которые значительно больше. Время O(1) в худшем случае (постоянное время даже в худшем случае) было бы предпочтительнее для многих приложений, включая сетевые маршрутизаторы и кэши памяти. Лишь немногие алгоритмы хэш-таблиц поддерживают время поиска в худшем случае O(1) (постоянное время поиска даже в худшем случае). К ним относятся: совершенный хешинг, динамический совершенный хешинг, хешинг кукушкой, хешинг с пропуском и расширяемый хешинг.