Метод деления для хеш-значений

Question

Предположим, что строка из r символов хэшируется в m слотов, обрабатывая ее как число с основанием-128, а затем используя метод деления.Число m легко представить в виде 32-разрядного компьютерного слова, но строка из r символов, рассматриваемая как число радиуса-128, занимает много слов.Как мы можем применить метод деления для вычисления значения хеша символьной строки, не используя более чем постоянное количество слов хранения вне самой строки?

Answer 1

Вы можете использовать метод / правило Хорнера .

y = 0
for i = (n - 1) downto 0
    y = (ai + 128y) mod m
return y

Answer 2

Для любого n-значного числа в основании r:

number=a0*r^0+a1*r^1+a2*r^2+...+a(n-1)*r^(n-1)

Чтобы вычислить значение этого числа mod m, мы делаем

(a0*r^0+a1*r^1+a2*r^2+...+a(n-1)*r^(n-1))%m

Но обратите внимание, что

(a0*r^0+a1*r^1+a2*r^2+...+a(n-1)*r^(n-1))%m
   = ((a0*r^0)%m + (a1*r^1)%m+(a2*r^2)%m+...+(a(n-1)*r^(n-1))%m)%m
   = (sum over 0<=i<n: (ai*r^i)%m)%m

Таким образом, вы можете просто выполнять итерацию по одному символу за раз, вычисляя значение (ai ^ ri)% m и накапливая сумму.

Код (в Python):

def hash_code(s,radix,mod):
        pwr=1 # radix^0=1
        answer=0
        for index,character in enumerate(s):
            answer=(answer+(ord(character)*pwr)%mod)%mod
            pwr=(pwr*radix)%mod # radix^(i+1)=radix*radix^i
        return answer

Не забудьте использовать оператор% после каждой операции, чтобы избежать переполнения (хотя в Python это строго не требуется).