Tabulka s přímým adresováním

Máme skupinu záznamů, které jsou jednoznačně identifikovány klíčem a mají přiřazenou hodnotu (například slova ve slovníku, nebo seznam studentů podle osobního čísla). Takováto struktura se nazývá ADT Tabulka.

Složitost operací lze podle způsobu implementace rozdělit následovně:

[editovat] Tabulka obsahuje mnoho hodnot vzhledem k počtu klíčů

(např. seznam otázek k SZZ z předmětu PPA2). Zde je vhodné použít pole, otázky jsou číslovány, a tyto čísla použít jako index do pole otázek. Každá otázka pak má Předmět, zadání, .... Hledání v takové tabulce je pak O(1). Do této skupiny by mohly patřit i problémy, kdy je možné prvky v lineárním čase indexovat tak, že je tento index získán v konstantním čase (například den v roce pro adresování stránky v deníku)

[editovat] Tabulka obsahuje mnoho klíčů a méně hodnot

(Například počty výskytů slov této otázky. Čěština má cca 300 000 slov, ale v textu jich unikátních bude hrstka). Pro takové problémy se implementace pomocí pole nehodí, protože plýtváme pamětí (vetšina pole bude hodnota 0). Pro adresování tedy použijeme například spojový seznam. Vložení klíče je O(1), ale hledání klíče je O(n), protože musíme projít všechny položky a pro každou se podívat, jaký klíč obsahuje. Toto lze zrychlit použitím například BVS, potom bude hledání O(log n) a zásid také O(log n), kde n je počet klíčů stromu. Pokud bychom měli příklad se slovy v článku, bylo by rychlejší použít například strukturu Trie, která má vyhledávání a zápis závislý na délce slova (za předpokladu, že Trie použije v každém uzlu tabulku s přímým adresováním podle znaku. Použijeme trochu více paměti, ale pořád méně než při ad 1)

[editovat] Tabulka obsahuje mnoho hodnot pro menší množství klíčů

Tato možnost se přímým adresováním řešit nedá, klíče nejsou unikátní. Je nutné použít rozptylové tabulky