Выбор способа перевода ключевых слов в числовую форму
Вся информация, вводимая в компьютер, кодируется в соответствии с одной из систем кодирования (таблиц кодировки). В большинстве таких систем символы (цифры, буквы, служебные знаки) представляются однобайтовыми двоичными числами. В последних версиях Windows (NT, 2000) используется система кодировки Unicode, в которой символы представляются в виде двухбайтовых двоичных величин. Как правило, ключевые поля элементов таблиц – строки символов, Наиболее известные алгоритмы закрытого хэширования основаны на следующих методах [32]:
- деления;
- умножения;
- извлечения битов;
- квадрата;
- сегментации;
- перехода к новому основанию;
- алгебраического кодирования;
- вычислении значения CRC (см. соответствующую главу).
Далее мы рассмотрим только первые четыре метода. Остальные методы – сегментации, перехода к новому основанию, алгебраического кодирования – мы рассматривать не будем. Отметим лишь, что их используют либо в случае значительной длины ключевых слов, либо когда ключ состоит из нескольких слов. Информацию об этих методах можно получить в литературе.
Рассмотрение методов хэширования будет произведено на примере одной задачи. Это позволит лучше понять их особенности, преимущества, недостатки и возможные ограничения.
Необходимо разработать программу – фрагмент компилятора, которая собирает информацию об идентификаторах программы. Предположим, что в программе может встретиться не более М различных имен. Длину возможных имен ограничим восьмью символами. В качестве ключа используются символы идентификатора, какие и сколько – будем уточнять для каждого из методов. Элемент таблицы состоит из 10 байт: 1 байт признаков, 1 байт для хранения длины идентификатора и 8 байт для хранения символов самого идентификатора.
Метод деления
Этот простой алгоритм закрытого хэширования основан на использовании остатка деления значения ключа К на число, равное или близкое к числу элементов таблицы М:
А(К) = К mod M
В результате деления образуется целый остаток А(К), который и принимается за индекс блока в таблице. Чтобы получить конечный адрес в памяти, нужно полученный индекс умножить на размер элемента в таблице. Для уменьшения коллизий необходимо соблюдать ряд условий:
- Значение М выбирается равным простому числу.
- Значение М не должно являться степенью основания, по которому производится перевод ключей в числовую форму. Так, для алфавита, состоящего из первых пяти английских букв и пробела {a,b,c,d,e,' '} (см. пример выше), основание системы равно 6. Исходя из этого число элементов таблицы М не должно быть степенью 6Р.
Важно отметить случай, когда число элементов таблицы М является степенью основания машинной систем счисления (для микропроцессора Intel – это 2). Тогда операция деления (достаточно медленная) заменяется на несколько операций.
Метод умножения
Для этого метода нет ограничений на длину таблицы, свойственных методу деления. Вычисление хэш-адреса происходит в два этапа.
Первый этап – вычисление нормализованного хэш-адреса в интервале [0..1] по формуле:
F(K) = (С*К) mod 1,
Где С – некоторая константа из интервала [0..1], К – результат преобразования ключа в его числовое представление, mod 1 означает, что F(K) является дробной частью произведения С*К.
Второй этап – конечный хэш-адрес А(К) вычисляется по формуле:
А(К) = [M*F(K)],
Где М – размер хэш-таблицы, а скобки [ ] означают целую часть результата умножения.
Удобно рассматривать эти две формулы вместе:
А(К) = М*(С*К) mod 1. (2.4)