Tabulka
Rozptylovací funkce
 Vytisknout studijní materiál

Rozptylovací funkce

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.

Multiplikativní metoda

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 φ.

Modulární metoda

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 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;

}