S organizací dat ve formě tabulky se setkáváme odedávna. Často jde nejenom o dynamickou množinu, ale i statickou množinu, kdy se tabulka nemění je-li jednou vytvořena.
Před věkem počítačů, případně kalkulaček, v technické praxi se pro výpočty používali matematické tabulky. V nich byly uvedeny pro jednotlivá čísla například hodnoty jejich logaritmů, převrácených hodnot, mocnin ap.
V individuálních sportovních disciplinách má každý z přihlášených účastníků přiděleno startovní číslo. Pro rychlé zjištění, kdo má určité startovní číslo, je opět vhodná tabulka startujících seřazených podle startovního čísla.
Odpovídající abstrakce je organizace dat, kde podle jednoznačné hodnoty klíče prvku množiny zpřístupňujeme další hodnoty uložené v prvku množiny (připomeňme, že s tímto způsobem práce s daty jsme se setkali u ADT BVS).
V případě matematických tabulek je klíčem číslo a zjistíme jeho logaritmus, převrácenou hodnotu, atd. V tabulce startujících je klíčem startovní číslo a z tabulky zjistíme jméno startujícího a případně další uchovávané informace jako věk, nejlepší dosavadní výkon ap.
Pokud vytvoříme tabulku převrácených hodnot pro čísla od 1 do 1000, potom obsahuje tuto hodnotu pro každou hodnotu klíče. Efektivní implementace takové tabulky je pole, kde klíč je přímo indexem prvku, ve kterém je uchovávaná hodnota. Nalezení této hodnoty je O(1). Tabulka přihlášených účastníků sportovního klání má stejnou vlastnost.
Obecně nemusí množina prvků obsahovat prvky se všemi klíči. Někteří z přihlášených účastníků sportovního závodu nenastoupí, například ze zdravotních důvodů, jiní závod nedokončí. Prvky množiny reprezentující pořadí a výkon závodníků, kteří dosáhli cíle, tedy nemusí obsahovat každou z možných hodnot klíče, kterým je přidělené startovní číslo.
Pro implementaci této množiny je možné uvažovat spojový seznam, ve kterém každý prvek obsahuje startovní číslo, pořadí, výkon a ukazatel na další prvek. Nalezení pořadí a výkonu účastníka se zadaným startovním číslem je potom O(n).
Pokud jsou startovní čísla přidělována náhodně, můžeme množinu účastníků, kteří dosáhli cíl, organizovat jako BVS, například vytvářením BVS vkládáním vrcholu s uvedenými údaji, když účastník závodu dosáhl cíle. Vyhledání pořadí a výkonu účastníka se zadaným startovním číslem je potom, jak již víme, O(log2 n).
Na druhé straně je možné předpokládat, že poměrně malá část, v řádu několika procent, účastníků závodu se nedostaví na start nebo závod nedokončí. V takové situaci si můžeme dovolit vytvořit pole pro všechny hodnoty klíče, přičemž některé pozice nebudou obsazeny, což je cena za to, že přístup k informacím o pořadí a výkonu závodníka bude O(1). Přitom nároky na paměť jsou o málo větší než je velikost paměti nutná na uložení požadovaných informací. Abstrakci takovéto organizace dat budeme říkat tabulka s přímým adresováním.
Uvažujme kvalitativně jinou situaci. Sledujme počet výskytů slov v nějakém textu, přičemž uvažujeme jejich základní tvar a ať text má 8 000 slov (cca 15 stránek jako je tato). Pokusme se aplikovat předcházející přístup. Možná slova jsou ze slovní zásoby uvedené ve slovníku jazyka a lexikografické pořadí daného slova, tj. pořadí v jakém je uvedeno ve slovníku, určí index prvku pole, ve kterém budeme uchovávat počet výskytů daného slova. Slovníky pro běžně vzdělaného člověka uvádějí asi 50 000 slov. Pokud v uvedeném textu bude každé slovo použito průměrně desetkrát, budeme potřebovat pole o padesáti tisíci prvcích pro 50 000 různých klíčů, ze kterého využijeme 7 000/10 = 700 prvků, tj. 1,4%. Taková cena za přístup O(1) k informaci kolikrát se dané slovo v našem textu nachází je jistě příliš veliká.
Uvedená situace může být ještě horší. V univerzitních databázích je každý student identifikován svým osobním číslem. Na ZČU je toto „číslo“ tvořeno následovně. První znak je písmeno identifikující fakultu, následující dvě číslice jsou poslední dvě číslice roku nástupu a další tři číslice jednoznačně identifikují studenta v rámci roku, ve kterém nastoupil studium. Osobní číslo studenta univerzity, množina klíčů, tedy má potenciálně 2 600 000 hodnot. Každý student univerzity si může zapsat předmět X, jehož kapacita je například 200 studentů. Pro uchovávaní výsledků studentů v tomto předmětu uvedeným způsobem bychom potřebovali pole s 2 600 000 prvky, z nichž by bylo využito 200, tj. méně než 0,01%, přičemž výsledky studenta se zadaným osobním číslem můžeme vložit nebo zjistit v O(1).
V těchto případech vzniká otázka, zda-li nelze mít pro uložení prvků množiny pole o velikosti úměrné skutečnému počtu prvků množiny a nikoliv pole o velikosti počtu všech klíčů, a aby přístup k prvkům množiny podle klíče byl O(1).
Odpověď je kladná. Musíme ovšem, místo přímého použití hodnoty klíče jako indexu, umět z jeho klíče vypočítat index prvku pole kde je prvek množiny uložen. Takové organizaci dat budeme říkat rozptylová (hash) tabulka, kterou se budeme zabývat v následujícím článku.
Přímé adresování je vhodné není-li velikost│K│množiny klíčů K velká. Obdobně jako jsme předpokládali u BVS, klíče všech prvků uložených v tabulce jsou různé a prvky jsou reprezentovány objekty třídy Prvek (obr.). Rozhraní tabulky s přímým adresováním jako abstraktního datového typu 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│ve třídě Tabulka, jehož prvky budou obsahovat odkazy na prvky tabulky, resp. null nejsou-li využity (obr.). Implementace dalších operací rozhraní je na obr.
. Všechny operace jsou rychlé a jejich čas je O(1).
Uvedený přístup je ilustrován na obr.. 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 metody 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.