Хеширование строковых ключей

До сих пор рассматривались алгоритмы хеширования целочисленных ключей. Не менее часто на практике приходится работать со строковыми ключами. Хеширование таких ключей обычно начинают с того, что преобразуют строковое значение в число, а затем используют один из описанных выше алгоритмов хеширования целочисленных ключей.

Следует подчеркнуть, что способ преобразования строки в число не менее важен для качественного хеширования, чем дальнейшее преобразование полученного числа. Пусть, например, в результате непродуманного преобразования все строковые ключи отображаются только в множество четных целых чисел. Это значит, что половина возможных значений числовых ключей не будет использоваться, а это затруднит хорошее рассеяние остальных значений. Если же преобразование строки настолько неудачно, что количество разных значений числового ключа получается меньше, чем размер хеш-таблицы, то уже никакая изощренная хеш-функция не сможет это компенсировать.

Хорошее рассеяние строковых ключей возможно только в том случае, если результат преобразования в число существенно зависит от каждого символа строки. Обычно это достигается следующим образом. Строка разбивается на отрезки длиной от 2 до 4 байт, каждый из которых рассматривается как двоичное число. Затем с помощью циклического повторения некоторой несложной операции полученные числа «сворачиваются» в одно число. Что это может быть за операция? Очень хорошо подходит логическая операция «Исключающее ИЛИ» (XOR), которая на любом процессоре выполняется как одна машинная команда и при этом существенно зависит от каждого бита каждого из своих операндов. Другой хороший кандидат – обыкновенная операция целочисленного сложения. В этом случае, однако, может возникнуть переполнение разрядной сетки; ничего страшного, но лучше все-таки не терять переполняющие разряды и прибавлять их к младшим разрядам результата.

Весьма желательно перед каждым сложением или XOR применять к ранее накопленному результату операцию циклического сдвига на один разряд. (Для не знающих Ассемблера: циклическим сдвигом называется сдвиг двоичных разрядов влево или вправо, при котором биты, выходящие за разрядную сетку, переносятся на противоположный конец числа.) Если не делать сдвиг, то некоторые строки, отличающиеся друг от друга только перестановкой букв, будут давать одинаковые числовые значения.

В принципе, полученные таким образом числовые ключи обычно бывают хорошо рассеяны на множестве всех целых чисел. Однако случается и иначе. Часто ключ бывает описан как строковая переменная достаточно большой длины, но при этом большая часть реально встречающихся ключей состоит из одного-двух-трех символов, дополненных справа пробелами до нужной длины. При этом все хитрые способы свертки ключа будут «месить» в основном одни и те же машинные слова, соответствующие пробелам.

Для большей уверенности в хорошем рассеивании ключей желательно применить к свернутому ключу описанные выше алгоритмы хеширования целочисленного ключа.

Для ключей, принадлежащих к иным типам данных (вещественные числа, даты и т.п.), можно аналогичным образом придумать способы преобразования в целые числа с перемешиванием.