ALG6

Rozdział 7. Algorytmy przeszukiwania

^r > dzielenie modulo R_mM: H(v) = v% R_max

Przykład:

^Dla ^, = 37 H(,,KOT")=(01011 01110 10100), % (37) ,₀ = (11732),₀=3.

Zalety:

• funkcja H łatwa do obliczenia.

Wady:

• otrzymana wartość zależy dość paradoksalnie - bardziej od R_mas niż od klucza!

Przykładowo gdy R_max jest parzyste, na pewno wszystkie otrzymane indeksy danych o kluczach parzystych będą również parzyste, ponadto dla pewnych dzielników wiele danych otrzyma ten sam indeks... Można temu częściowo zaradzić poprzez wybór R_imx jako liczby pierwszej, ale tu znowu będziemy mieli do czynienia z akumulacją elementów w pewnym obszarze tablicy - a wcześniej wyraźnie zażyczyliśmy sobie, aby funkcja H rozdzielała indeksy „sprawiedliwie'" po całej tablicy!

• w przypadku dużych liczb binarnych nie mieszczących się w reprezentacji wewnętrznej komputera, obliczenie modulo już nie jest możliwe przez zwykłe dzielenie arytmetyczne.

Co się tyczy ostatniej wady, to prostym rozwiązaniem dla ciągów tekstowych w C++ („wewnętrznie” są to przecież zwykłe ciągi bajtów!) jest następująca funkcja, bazująca na interpretacji tekstu jako szeregu cyfr ^-bitowych:

int H(char *s, int Rmax)

(

for (int lmp=0; *s!=NULL; s++)

Łmp=(64*tmp+(*s))% Rmax; return tmp;

)

mnożenie:

H(y) = [(((v*£)%0*ffma-y)] gdzie 0<0

<1

Powyższą formułę należy odczytywać następująco: klucz v jest mnożony przez pewną liczbę 6 z przedziału otwartego (OJ). Z wyniku bierzemy część ułam kową. mnożymy przez E_mm i ze wszystkiego liczymy część całkowitą.