|
|||
Tabulky podle organizace
1. Tabulky s přímým přístupem
k ® Ak je zobrazení prosté, každá položka v tabulce má své místo jednoznačně určené hodnotou Ak přímo odvozenou z k, tedy odpadá vyhledávání.
Přímé adresování je vhodné není-li velikost│K│množiny klíčů K velká.
Příklad: tabulka odkazů na oddíly slovníku (A, B, C, . . . ) = veliká tabulka. Vhodné pro tabulky s malou množinou klíčů (startovní listina běžců malého závodu, ve které jsou údaje o závodníkovi, jeho čase..aj.)
Tabulka je v tomto případě implementována pomocí pole velikosti k, jehož prvky budou obsahovat reference na prvky tabulky, respektive null nejsou-li využity.
Klíče všech prvků dynamické množiny jsou různé a prvky jsou reprezentovány objekty třídy Prvek
class Prvek {
int klic;
String data;
...
Prvek(int klic, String data) {
this.klic = klic;
this.data = data;
}
}
Rozhraní ADT tabulky s přímým adresováním bude tvořeno následujícími operacemi.
class Tabulka {
// rozhrani ADT
Tabulka()
Prvek hledej(int)
vloz(Prvek)
vyber(Prvek)
}
Tabulka bude reprezentována polem t velikosti │K│, jehož prvky budou obsahovat reference na prvky tabulky, resp. null nejsou-li využity.
class Tabulka {
Prvek[] t = new Prvek[│K│];
Tabulka() {
for(int i = 0; i < t.length; i++) {
t[i] = null;
}
}
Implementace dalších operací je zřejmá:
Prvek hledej(int k) {
return t[k];
}
void vloz (Prvek x) {
t[x.klic] = x;
}
void vyber (Prvek x) {
t[x.klic] = null;
}
Všechny operace jsou rychlé, potřebný čas je O(1).
Uvedený přístup je ilustrován na příkladu 
startujících se startovními čísly
1 až 365, přičemž startující s čísly 3,101 a 364 ke startu nenastoupili.
Alternativní implementace by mohla namísto referencí na prvky dynamické množiny v poli implementujícím tabulku obsahovat přímo samotné prvky. Navíc, jsou-li prvky přímo v tabulce, známe jejich klíč na základě indexu a nemusíme klíč uchovávat v prvku samotném. Musíme ovšem být schopni poznat, že prvek pole je prázdný.
Poznamenejme, že operace vloz a vyber nemají jako parametr klíč a data, resp. klíč, ale ukazatel na prvek množiny. Důvodem takové konstrukce může být existence prvků množiny před jejich organizací v tabulce. Příkladem může být pole všech přihlášených závodníků, ale do tabulky jejich umístnění a dosáhnutého výkonu vložíme jenom ty závodníky, kteří nastoupili a závod dokončili. Obdobně, byl-li některý závodník diskvalifikován, bude z tabulky výsledků vybrán.
2. Obyčejné vyhledávací tabulky
3. Tabulky s rozptýlenými položkami (hash-tables)
k ® Ak se nazývá rozptylovací funkce, jsou na ni kladeny speciální požadavky, které již byly vysvětleny v předešlé kapitole.
Množina A, prvků identifikovaných klíčem, je daleko menší než množina všech hodnot klíče A << K. Velikost tabulky je tedy také << K. V tabulce budou nyní prvky množiny identifikované svým klíčem zpřístupňovány pomocí indexu s hodnotami 0 až m-1. Potřebujeme tedy hodnotu klíče prvku transformovat na hodnotu indexu, musíme tedy definovat Hash - funkci:
h: K ® {0,1, ... , m-1}
, kterou budeme nazývat také rozptylovací funkcí.
Nevyhnutelně tedy musí nastat, že rozptylová funkce zobrazí obecně dva a více různých klíčů na stejný index. Tento jev nazýváme kolizí.
V ideálním případě, kdy je rozptylová funkce dostatečně náhodná, budou za předpokladu, že m > A, budou všechny klíče aktuální množiny prvků zobrazeny na různé hodnoty indexu.. Naopak v nejhorším případě se klíče všech prvků aktuální množiny zobrazí na jeden index.
Obecně nemůžeme kolize vyloučit.
V zásadě existují dvě možnost ipři postupu, kdy vkládám do tabulky a pa pozice v tabulce je již obsazena. Prví je vnější řetězení prvků, kterých klíče rozptylová funkce zobrazí na stejnou hodnotu. Druhou je otevřené adresování, kdy v případě kolize je prvek množiny systematicky uložen a následně hledán v tabulce. V tomto případě ale musí být m > A. V pvním případě přichází doo úvahy všechny možnosti tj M < A, m = A a M > A.
4. Tabulky se zřetězenými položkami
-viz.dále
Na základě organizace tabulky provádíme vyhledávání prvku
Kllíčům přiřadíme číselné hodnoty (převedeme do vysoké číselné soustavy) - tzv. transformace klíče (pro zrychlení porovnání)
Př. : Novák ® 345.
Kromě primárního klíče máme také možnost hledat podle klíče sekundárního.
Vyhledávání prvku v tabulce s přímým přístupem bude probráno v další kapitole.