Функции расстановки
Много внимания исследователями было уделено тому, какой должна быть (первичная) функция расстановки. Основные требования к ней очевидны: она должна легко
вычисляться и распределять равномерно. Один из возможных подходов здесь заключается в следующем.
1. По символам строки s определяем положительное целое H. Преобразование одиночных символов в целые обычно можно сделать средствами языка реализации. В Паскале для этого служит функция ord, в Си при выполнении арифметических операций символьные значения трактуются как целые.
2. Преобразуем H, вычисленное выше, в номер элемента, т.е. целое между 0 и N - 1, где N - размер таблицы
расстановки, например, взятием остатка при делении H на N.
Функции расстановки, учитывающие все символы строки, распределяют лучше, чем функции, учитывающие только несколько символов, например, в конце или середине строки. Но такие функции требуют больше вычислений.
Простейший способ вычисления H - сложение кодов символов. Перед сложением с очередным символом можно умножить старое значение H на константу q. Т.е. полагаем H0 = 0, Hi = q*Hi-1 + ci для 1
q = 1 получаем простое сложение символов. Вместо сложения можно выполнять сложение ci и q*Hj-1 по модулю 2. Переполнение при выполнении арифметических операций можно игнорировать.
Функция Hashpjw, приведенная ниже [10], вычисляется, начиная с H = 0 (предполагается, что используются 32-битовые целые). Для каждого символа c сдвигаем биты H на 4 позиции влево и добавляем очередной символ. Если какой-нибудь из четырех старших бит H равен 1, сдвигаем эти 4 бита на 24 разряда вправо, затем складываем
по модулю 2 с H и устанавливаем в 0 каждый из четырех старших бит, равных 1.
| #define PRIME 211 #define EOS '\0' int Hashpjw(char *s) {char *p; unsigned H=0, g; for (p=s; *p!=EOS; p=p+1) {H=(H if (g=H&0xf0000000) {H=H^(g>>24); H=H^g; } } return H%PRIME; } |
