Tabulky
Rozptýlená tabulka
 Tisk

Rozptýlená tabulka


Další možností, jak organizovat tabulku, je provádět výpočet adresy v tabulce z hodnoty klíče podle vzorce:


A = F(K,N)



Funkce F se nazývá transformační funkce . Problémem je nalézt tuto funkci F. Přitom lze často využít vlastností klíče.

Jednoduchá transformační funkce

Nejjednodušší transformační funkcí je lineární funkce, kdy klíčem je přirozené číslo v rozsahu B až B+N, kde B je libovolné přirozené číslo. Příkladem jsou např. čísla příjemek ve skladu, které jsou číslovány souvisle vzestupně.


Jiným jednoduchým algoritmem je výpočet adresy pro úložné místo ve skladu. Řady regálů (R) jsou značeny ´A´-´F´, souřadnice dálky (D) 1-50, výška (V) 1-10. Funkce F pak může mít tvar:


A = (ord(R) - ord(´A´)) * 500 + (V-1)*50 + D


Obecná transformační funkce - rozptýlení

Obecně však využití vlastností klíče není možné. Klíč si lze přestavit jako hodnotu v rozsahu 1 - 256L, kde L je délka klíče v bytech. Funkce F má zobrazit tuto hodnotu do rozsahu velikosti tabulky. Dalším požadavkem je zrovnoměrnění využití tabulky nezávisle na jistém shlukování původních hodnot klíčů. Těmto požadavkům vyhovuje např. funkce, která vypočítává z hodnoty klíče zbytkem po dělení délkou tabulky adresu v tabulce. Nejlepšího zrovnoměrnění hodnot dosáhneme, jestliže je počet položek tabulky prvočíslo, jinak dochází ke shlukování s periodou prvočinitelů počtů položek tabulky. Funkce transformující klíč na adresu se pak nazývá rozptylovací (hash) funkce.

Synonyma

Problémem je, že více hodnotám klíče může být přiřazena stejná adresa. Hodnoty klíče, kterým je přiřazena stejná adresa, se nazývají synonyma.


Implementace rozptýlené tabulky

Tabulku lze implementovat dostatečně dlouhých polem. Vzhledem k možnosti výskytu synonym se doporučuje maximální zaplnění tabulky 60-70%. Prvkem pole implementujícího tabulku je datový typ záznam, který obsahuje:



Řídící struktura tabulky obsahuje čtyři prvky:



Řešení synonym

Řešení synonym se provádí následujícím způsobem:



Je statisticky prokázáno, že pokud počet položek tabulky nepřekročí 60-70% délky tabulky, průměrný počet přístupů s využitím indexů OA a OB bude menší než 1.3.


Inicializace tabulky

Při inicializaci tabulky je nastaven maximální počet položek v tabulce, nulován skutečný počet položek v tabulce a v celé tabulce jsou všechny položky označeny jako zrušené a současně nulovány indexy OA a OB.


Vložení položky

Při vložení nové položky se kontroluje, zda index je v tabulce ještě místo. Pokud ano, provede se výpočet adresy, ošetří se synonyma a skutečný počet položek se zvýší o jedna.


Vyhledání položky

Vyhledání položky podle zadaného klíče se provádí výpočtem adresy. Pokud na vypočtené adrese není platná položka nebo požadovaný klíč se neshoduje s nalezeným, pak se pokračuje podle indexů OA a OB.

Průměrná četnost přístupu je menší než 1.3, bez ohledu na délku tabulky a počet obsazených položek.


Změna položky

Změna položky spočívá ve vyhledání podle klíče a změně uživatelské informace. Řídící struktura tabulky zůstává nezměněna.


Rušení položky

Rušení položky spočívá ve vyhledání podle klíče, nastavení indikace na zrušení úpravu indexů OA a OB, přičemž položky zůstávají na místě, a snížení skutečného počtu položek v tabulce o jednu.


Reorganizace

Reorganizace není nutná. Nevýhodou je, že nelze určit následující ani předcházející položku v tabulce ve smyslu seřazení podle abecedy.


Užití rozptýlené tabulky

Rozptýlené tabulky se používají, pokud je třeba rychle vyhledávat danou položku a nepotřebujeme zpracovávat metodou zpracuj nejbližší další položku vzestupně.



Příklad tabulky s rozptýlenými klíči je na obrázku . Položka DANA generuje stejnou adresu jako ALENA. Použije se další volné místo (10) a index OA položky (9) se nastaví na 10. Obdobně se řeší synonyma CYRIL a PAVEL. Adresu 6 generují synonyma ROBERT, LUDEK a ROSTISLAV. Zde se využije OA položky ROBERT (6) a OB položky LUDEK (7). Pokud by další klíč generoval adresu 7 použije se OA

adresy 7.