Сборник по задачам и примерам Assembler


Поиск в таблице - часть 13


А(К) = К mod M

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

  • Значение М выбирается равным простому числу.
  • Значение М не должно являться степенью основания, по которому производится перевод ключей в числовую форму. Так, для алфавита, состоящего из первых пяти английских букв и пробела {a,b,c,d,e,' '} (см. пример выше), основание системы равно 6. Исходя из этого число элементов таблицы М не должно быть степенью 6Р.

Важно отметить случай, когда число элементов таблицы М является степенью основания машинной систем счисления (для микропроцессора Intel — это 2). Тогда операция деления (достаточно медленная) заменяется на несколько операций.

Метод умножения

Для этого метода нет ограничений на длину таблицы, свойственных методу деления. Вычисление хэш-адреса происходит в два этапа:

1. Вычисление нормализованного хэш-адреса в интервале [0..1] по формуле:

F(K) = (С*К) mod 1,

где С — некоторая константа из интервала [0..1], К — результат преобразования ключа в его числовое представление, mod 1 означает, что F(K) является дробной частью произведения С*К.

2. Конечный хэш-адрес А(К) вычисляется по формуле А(К) = [M*F(K)], где М — размер хэш-таблицы, а скобки [] означают целую часть результата умножения.

Удобно рассматривать эти две формулы вместе:

А(К) = М*(С*К) mod 1. (2.4)

Кнут в качестве значения С рекомендует использовать «золотое сечение» — величину, равную ((л/5)-1)/2«0,6180339887. Значение F(K) можно формировать с помощью как команд сопроцессора, так и целочисленных команд. Команды сопроцессора вам хорошо известны и трудностей с реализацией формулы (2.4) не возникает. Интерес представляет реализация вычисления А(К) с помощью целочисленных команд. Правда, в отличие от реализации сопроцессором здесь все же Удобнее ограничиться условием, когда М является степенью 2. Тогда процесс вычисления с использованием целочисленных команд выглядит так:




- Начало -  - Назад -  - Вперед -



Книжный магазин