Иллюстрированный самоучитель по задачам и примерам Assembler

Выбор способа перевода ключевых слов в числовую форму

Вся информация, вводимая в компьютер, кодируется в соответствии с одной из систем кодирования (таблиц кодировки). В большинстве таких систем символы (цифры, буквы, служебные знаки) представляются однобайтовыми двоичными числами. В последних версиях 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)
Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.