Uvedli jsme, že od rozptylovací funkce
h: K → { 0,1, ... m -1}
očekáváme, že každý klíč zobrazí (přibližně) stejně pravděpodobně na libovolnou z m hodnot, nezávisle na tom, kam je zobrazen jakýkoliv jiný klíč. Obecně, musíme znát charakteristiku výskytu klíčů v aplikaci, což není vždycky splněno.
Klíče mohou mít různý typ, od jednoduchých datových typů až k strukturovaným datovým typům, jakými jsou například objekty. Na druhé straně, každý typ klíče je v počítači reprezentován řetězcem 0 a 1, který můžeme vyjádřit jako (možná velice veliké) celé číslo. Tato reprezentace navíc umožní konstrukci rozptylovací funkce pomocí aritmetických operací a tím dosáhnout také dostatečné efektivnosti výpočtu hodnot rozptylovací funkce.
Uvažujme tabulku identifikátorů použitých v programu. Pro implementaci grafů jsme mimo jiné použili identifikátory vrchol a vrcholy a rozptylovací funkce by jim měla přiřadit různé pozice v tabulce i když jsou si v jistém smyslu blízké, například reprezentujeme-li je celým číslem.
Celou část reálného čísla r budeme označovat
Je-li c reálné číslo z intervalu 0 ≤ c < 1, potom hodnoty
jsou z oboru funkčních hodnot rozptylovací funkce a tedy zbývá transformovat hodnoty klíčů na interval 0 ≤ c < 1. Jsou-li hodnoty klíčů k omezeny, a ≤ k < b, potom odpovídající lineární transformace je
c = (k - a) / (b - a)
Uvažujme množinu klíčů K = { 1, 2, ..., 10 000 } a tabulku o velikosti m = 100. Potom a = 1, b = 10 001 a rozptylovací funkce h pro klíč k má hodnotu
Tato funkce zobrazí v tabulce všechny klíče k = 1, 2, ..., 100 na pozici 0, klíče k = 101, 102, ..., 200 na pozici 1, atd. Podmínku rovnoměrně náhodné distribuce bude splňovat jenom tehdy, jsou-li i klíče nezávisle a rovnoměrně náhodně rozděleny na celé množině svých hodnot. Viděli, jsem však, že obecně tento předpoklad spíše nebývá splněn.
Transformace klíče k na multiplikativní koeficient c, musí být „znáhodněna“ a přitom její výpočet musí zůstat efektivní. Tomu vyhovuje následující výpočet koeficientu c.
Zvolíme konstantu A z intervalu 0 < A < 1 a jako koeficient c vezmeme zlomkovou část součinu kA. Rozptylovací funkce potom je
Pro její efektivní implementaci na strojové úrovni zvolíme m = 2p. Nechť celočíselný klíč k je zobrazen slovem s w bity. Konstantu A zvolme ve tvaru q /2w, kde q je celé číslo zobrazené také jako slovo s w bity. Celočíselným násobením k.q získáme celočíselnou hodnotu s 2w bity uloženou ve dvou slovech s0 a s1 (obr.), přičemž s0 označuje slovo s bity nižších řádů součinu. Uvědomíme-li si, že k.A = k.q /2w , vidíme, že w bitů slova s1 obsahuje celou část a w bitů slova s0 obsahuje zlomkovou část součinu kA. Hodnotu rozptylovací funkce h(k) tedy tvoří p nejvýznamnějších bitů slova s0.
Jako konstanta A se doporučuje hodnota zlatého poměru, tj. φ = 0.618033... a q pak volíme tak, aby pro dané w bylo q /2w co nejblíže φ.
Uvedené verze multiplikativní metody vyžadovaly buď nezávislé a rovnoměrně náhodné rozdělení klíčů anebo vycházely ze znalosti jejich strojové realizace. Poměrně jednoduchá a efektivní metoda výpočtu rozptylové funkce je modulární metoda. Vychází z toho, že hodnoty
h(k) = k mod m (v Javě k % m ) jsou právě z množiny { 0,1, ... m -1 }.
V případě modulární metody však, nemůžeme volit m libovolně. Například je-li m = 2p, potom h(k) závisí jenom na p nejnižších bitech klíče k.
Uvažujme častý případ, kdy klíčem je řetězec ASCII znaků. ASCII kód zobrazuje znak řetězcem 7 bitů, rozeznává tedy 128 různých hodnot, které můžeme interpretovat jako celá čísla 0 až 127. Obecný řetězec α1α2...αn potom můžeme interpretovat jako zápis čísla se základem 128, kterého hodnota je
z1.128 n-1 + z2.128 n-2 + ... +zn.1280
kde zi je celočíselná interpretace znaku αi.
Zvolíme-li m=64, hodnota h(α1α2...αn ) závisí jenom na posledních 6 bitech hodnoty zn. Důvodem je, že všechny vyšší bity již k hodnotě, z které počítáme mod m připočítávají násobky m. Uvedenému efektu určitě zabráníme, zvolíme-li jako hodnotu m prvočíslo.
Obecně, mohou být řetězce znaků tak dlouhé, že uvedená číselná reprezentace přesáhne rozsah zobrazitelných celočíselných hodnot. V tomto případě můžeme s výhodou využít právě toho, že pro výpočet mod m nemusíme uvažovat násobky m, protože
(x.m + y) mod m = y mod m
Rozepsáním výpočtu reprezentace řetězce celým číslem pomocí Hornerova schématu pro výpočet h(α1α2...αn ) dostaneme
h(α1α2...αn ) = (z1.128 n-1 + z2.128 n-2 + ... +zn.1280) mod m =
(((z1.128 + z2).128 + ... +zn-1).128 + zn ) mod m =
((((0.128 + z1) mod m .128 + z2) mod m .128 + ... +zn-1) mod m .128 + zn ) mod m
Uvedený výraz vede na přímočarý zápis rozptylovací funkce h(klic, m), kde klic je proměnná typu řetězec.
static int h(String klic, int m) {
int h = 0;
for (int i = 0; i < klic.length(); i++)
h = (h * 128 + klic.charAt(i)) % m;
return h;
}