Таблица T вСуть этой новой функции хеширования иногда можно изменить, чтобы получить минимальную, идеальную функцию хеширования по скромному списку слов.Фактически, обычно можно выбрать точное значение функции для конкретного слова.Например, Кнут [3] иллюстрирует идеальное хеширование с помощью алгоритма, который отображает список из 31 общих английских слов на уникальные целые числа от -10 до 30. Таблица T , представленная в таблице II, отображает эти же 31 слово нацелые числа от 1 до 31 в алфавитном порядке.
Хотя процедура построения таблицы в Таблице II слишком сложна, чтобы подробно описывать ее здесь, следующие основные моменты позволят заинтересованному читателю повторитьпроцесс:
- Таблица T была создана псевдослучайной перестановкой целых чисел (0 ... 255).
- Один за другим, желаемые значениябыли назначены слова в списке.Каждое назначение выполнялось путем обмена двумя элементами в таблице.
- Для каждого слова первым кандидатом для обмена был T [ h [ n - 1] 10 C [ n ]], последний элемент таблицы, на который есть ссылка при вычислении хеш-функции для этого слова.
- Элемент таблицы можетне подлежит обмену, если на него ссылались во время хеширования ранее назначенного слова или если на него ранее ссылались в хешировании того же слова.
- Если необходимый обмен был запрещен правилом 4, внимание было перенесено наранее указанный элемент таблицы, T [h [ n - 2] ⊕ C [ n - 1]].
Процедура не всегда успешна.Например, при использовании кодов символов ASCII, если слово «a» хэшируется до 0, а слово «i» хэшируется до 15, получается, что слово «in» должно хешировать до 0. Первоначальные попытки отобразить 31 слово Кнута нацелые числа (0 ... 30) потерпели неудачу именно по этой причине.Переход к диапазону (1 ... 31) был специальной тактикой, позволяющей обойти эту проблему.
Повреждает ли это вмешательство в T статистическое поведение функции хеширования?Не серьезно.Когда 26 662 словарных статей хэшируются в 256 блоков, результирующее распределение по-прежнему существенно не отличается от равномерного (χ² = 266,03, 255 df, p = 0,30).Хеширование 128 случайно выбранных словарных слов привело в среднем к 27,5 коллизиям против 26,8 с неизмененным T .Когда эта функция расширяется, как описано выше, для получения 16-битных индексов хеширования, тот же тест приводит к значительно большему количеству коллизий (4870 против 4721 с неизмененным T ), хотя распределение по-прежнему незначительно отличаетсяиз униформы (χ² = 565,2, 532 df, p = 0,154).