TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
- Tabulky s přímým přístupem
- Mapovací funkce
- Princip tabulek s rozptýlenými položkami
- TRP s explicitně zřetězenými synonymy
- TRP s implicitně zřetězenými synonymy
- TRP s lineárním vyhledáváním
- TRP s kvadratickým vyhledáváním
- TRP s dvojí rozptylovací funkcí
- Brentova varianta
- Operace DELETE v TRP
- Hodnocení vyhledávání v tabulkách s rozptýlenými pložkami
4.1. Tabulky s přímým přístupem
Je-li známa množina všech klíčů K={K1, … Kn}, které se budou vkládat do vyhledávací tabulky, a je-li možné nalézt jedno-jednoznačnou mapovací funkci f(Ki) = i (i = 1, 2, … n) pro všechny prvky množiny K, je možné vytvořit tabulku s přímým přístupem. Tuto tabulku tvoří pole, v němž položka s klíčem Ki bude uložena na indexu u daného pole.
Nechť jsou dány tyto typy:
TYPPOLOZKY = record
DATA:TYPDATA;
KLIC:TYPKLIC;
OBSAZEN:Boolean;
end;
TYPTABULKY = array [1..n] of TYPPOLOZKY;
a proměnné
TAB:TYPTABULKY; K:TYPKLIC; DATAPOLOZKY:TYPDATA;
Pak operace INITTAB ustaví složku OBSAZEN u všech položek pole na hodnotu false. Algoritmus operace INSERT bude mít jednoduchý tvar:
procedure INSERTTAB (var TAB:TYPTABULKY; K:TYPKLIC; DATAPOLOZKY:TYPDATA);
begin
TAB[f(k)].DATA := DATAPOLOZKY;
TAB[f(k)].KLIC := K; { tato operace není při jedno-jednoznačnosti funkce f() nutná }
TAB[f(k)].OBSAZEN := true;
end;
Operace SEARCHTAB ustaví svou hodnotu na základě složky OBSAZEN:
function SEARCHTAB (var TAB:TYPTABULKY; K:TYPKLIC):Boolean;
begin
SEARCHTAB := TAB[f(k)].OBSAZEN;
end;
Operace DELETETAB vyřadí prvek s klíčem K tímto příkazem:
procedure DELETETAB (var TAB:TYPTABULKA; K:TYPKLIC);
begin
TAB[f(k)].OBSAZEN := false;
end;
Obtíž s využitím jinak vysoce účinné tabulky s přímým přístupem spočívá v obtížném nalezení vhodné mapovací funkce f. V praxi se tato potíž někdy obchází používáním numerických klíčů pro identifikaci položek. Takové klíče dobře známe pod názvy „pořadové“ nebo „evidenční číslo“. V řadě případů je však tento manévr neúčinný, protože je nutné pracovat s textovým (nejčastěji sugestivním) tvarem klíče. Typickým příkladem takového případu je manipulace překladače s identifikátory, které tvoří uživatel programovacího jazyka při tvorbě svých programů.
4.2. Mapovací funkce
Jak nalézt vhodnou mapovací funkci pro danou množinu klíčů? Pro 31 různých prvků, které se mají zobrazit do 41 prvkové množiny existuje 4131 (tj. cca 1050) možných mapovacích funkcí. Přitom pouze (41!/31!) z nich dává odlišné hodnoty pro různé klíče. (tzn., že funkce je jedno-jednoznačná). To znamená, že poměr vhodných funkcí ke všem možným funkcím je asi 1:107. Jedno-jednoznačné funkce jsou tedy velmi řídkým jevem.
V dalších úvahách budeme hledat takovou mapovací funkci, která klíče z dané předpokládané množiny klíčů „rozptýlí“ v dané tabulce, aniž budeme trvat na jedno-jednoznačnosti funkce. Klíče, které mají stejnou hodnotu mapovací funkce, budeme nazývat synonyma. Dojde-li k pokusu umístit novou položku na místo, které je již obsazeno, budeme situaci nazývat kolize. Mapovací funkci používané k rozptýlení položek v tabulce budeme říkat rozptylovací funkce (angl. hash-function, říká se jí také hashovací či hašovací funkce).
Předpokládejme, že máme k dispozici celočíselnou funkci Num(K), která z libovolného typu klíče získá celé kladné číslo. Je-li klíč textovým řetězcem, může se využít jeho binárního obrazu (v Pascalu budeme pracovat např. s funkcí ord). Právě volba funkce Num nejvíce ovlivní počet synonym a množství kolizí v tabulce. Pro volbu této funkce však nelze stanovit obecně platná pravidla. Volba musí vycházet z konkrétních vlastností množiny klíčů. Bude-li funkce Num odvozovat svou hodnotu např. z prvního znaku textového klíče, pak všechny identifikátory (použité jako klíče) se stejným písmenem na začátku, budou synonyma. Protože všechna písmena nemají rovnoměrný výskyt jako první znaky identifikátorů, bude u některých znaků docházet k častějším klizím.
Na dobrou rozptylovací funkci se kladou dva základní požadavky:
- výpočet rozptylovací funkce musí být dostatečně rychlý
- rozptylovací funkce má vytvářet co nejméně kolizí
Je zřejmé, že tyto požadavky jsou většinou protichůdné.
Nechť rozptylovací funkce R(K) = h(Num(K)), kde funkce h zajistí transformaci (mapování) libovolného celého kladného čísla (získaného funkcí Num) do intervalu daného rozsahem indexu pole, kterým implementujeme tabulku. Tímto intervalem bude nejčastěji 0..MAX nebo 1..MAX.
Poměrně úspěšné rozptylovací funkce h jsou založeny na vlastnostech celočíselného dělení, a to především operace modulo. Např.
h(K) = K mod (MAX + 1)
získá hodnoty z intervalu 0..MAX a funkce
h(K) = K mod MAX + 1 z intervalu 1..MAX
Úspěšnost zvolené funkce však může záviset také na volbě velikosti tabulky (MAX). Pro funkci h(K) = K mod MAX jsou některé hodnoty MAX nevhodné. Jsou to např. hodnoty MAX = rl ± c, kde l a c jsou malá celá čísla a r je řád použitého alfanumerického kódu (např. 64, 128, 256 apod.).
4.3. Princip tabulek s rozptýlenými položkami
Princip vyhledávání v tabulkách s rozptýlenými položkami (dále jen TRP) je velmi podobný principu vyhledávání v indexsekvenčním souboru. Pomocí rozptylovací funkce se získá index pole, na něž se uloží (od něj se vyhledává) položka s daným klíčem. Obsahuje-li tabulka synonyma vzhledem k danému indexu (více různých klíčů mělo shodnou hodnotu rozptylovací), pak na daném indexu začíná lineární seznam synonym, v němž se vyhledává položka s daným klíčem. Vyhledávání v TRP bude účinné tehdy, jestliže počet seznamů synonym bude co největší a jejich délka bude co nejkratší.
Podle způsobu, jakým se realizuje lineární seznam synonym, se rozdělují nejznámější metody implementace TRP do dvou skupin:
- Tabulky s explicitně zřetězenými synonymy
- Tabulky s implicitně zřetězenými synonymy (této skupině se také říká „tabulky s otevřeným adresováním položek“)
Explicitním zřetězením se rozumí, že každý prvek seznamu obsahuje ukazatel na následníka v seznamu. Implicitním zřetězením se rozumí, že z adresy (indexu) každého prvku seznamu se může určit adresa (index) následujícího prvku.
4.4. TRP s explicitně zřetězenými synonymy
Základem TRP je pole. Na i-tém prvku pole je začátek lineárního seznamu všech položek se synonymními klíči, pro které platí R(K) = i. TRP s explicitně zřetězenými seznamy můžeme principiálně rozdělit podle způsobu, kterým se přiděluje paměťový prostor položkám seznamu.
- Pole obsahuje pouze ukazatele na jednotlivé seznamy synonym
- Pole obsahuje položky seznamu. Synonyma se ukládají do „oblasti přeplnění“. Kolidující položka v tabulce je zřetězena se seznamem synonym umístěným v oblasti přeplnění.
Oblast přeplnění může být organizována různými způsoby:
- Oblast přeplnění budou vytvářet paměťové místa získaná mechanismem dynamického přidělování paměti (new)
- Oblast přeplnění tvoří zvláštní pole (v některých případech to může být „horní“ část pole, jehož „spodní“ část je použita jako základní pole TRP)
- Oblast přeplnění se překrývá se základním polem TRP
Jako první si ukážeme implementaci typu A, v níž jsou všechny prvky tabulky obsaženy v „oblasti přeplnění“ realizované podle způsobu A. (V tom případě nemá vlastně smysl hovořit o oblasti přeplnění, protože jsou v ní uloženy všechny prvky.)
Nechť jsou dány tyto typy:
TYPUK = ^TYPPOLOZKY;
TYPPOLOZKY = record
DATA:TYPDATA;
KLIC:TYPKLIC;
DALSI:TYPUK;
end;
TYPTAB = array [1..MAX] of TYPUK;
Operace INIT nastaví všechny ukazatele tabulky TAB na hodnotu null.
procedura INIT (var TAB:TYPTAB);
var I:POSINT;
begin
for I:=1 to MAX do TAB[I[:=nil
end;
Operace SEARCH bude mít tvar Booleovské funkce:
function SEARCH (TAB:TYPTAB; K:TYPKLIC):Boolean;
var I:POSINT;
POMUK:TYPUK;
begin I := R(K);
POMUK := TAB[I];
SEARCH := false;
if POMUK <> nil then begin while (POMUK^.DALSI <> nil) and
(POMUK^.KLIC<> K) do POMUK:=POMUK^.DALSI;
SEARCH:=POMUK^.KLIC=K
end
end; { procedury SEARCH }
Operace INSERT buď vloží do tabulky novou položku (bylo-li vyhledání daného klíče neúspěšné), nebo přepíše (aktualizuje) datovou složku položky s vyhledaným klíčem. Uvedený algoritmus vkládá nový prvek na začátek seznamu synonym.
procedure INSERT (var TAB:TYPTAB; K:TYPKLIC; DATAPOLOZKY:TYPDATA);
var I:POSINT;
POMUK:TYPUK;
NASEL:Boolean;
begin
I:=R(K);
POMUK := TAB[I];
if POMUK <> nil
then { seznam synonym je neprázdný; prohledá se }
begin while (POMUK^.DALSI <> nil) and (POMUK^.KLIC <> K) do
POMUK := POMUK^.DALSI;
NASEL := POMUK^.KLIC = K;
end;
if NASEL then POMUK^.DATA := DATAPOLOZKY; { Přepis datové složky }
else begin { Nová položka se zařadí na začátek seznamu synonym }
new (POMUK);
POMUK^.DALSI := TAB[I];
TAB[I] := POMUK;
POMUK^.KLIC := K;
POMUK^.DATA := DATAPOLOZKY;
end
end; { procedury INSERT }
Operace DELETE je podobná operaci DELETE nad lineárním seznamem.
Dále je uveden algoritmus, v němž se oblast přeplnění překrývá se základním polem. Není-li při vkládání nového prvku volné místo na indexu získaném rozptylovací funkcí R, vyhledá se v poli tabulky první volný prvek (pro usnadnění vyhledávání se používá pomocný ukazatel ukazující na poslední volný prvek), naplní se daty a připojí se k seznamu synonym. Parametr ERROR oznamuje, že novou položku nelze vložit, protože je tabulka plná.
Nechť jsou dány tyto typy:
TYPPOLOZKY = record
KLIC:TYPKLIC;
DATA:TYPDATA;
VOLNY:Boolean;
DALSI:0..MAX;
end;
TYPTAB:array [1..MAX] of TYPPOLOZKY;
Operace inicializace bude ustavovat pole volných prvků a nastavovat pomocný ukazatel RR.
procedure INIT (var TAB:TYPTAB; var RR:POSINT);
var I:POSINT;
begin
fori I:=1 to MAX do TAB[I].VOLNY := true;
RR := MAX;
end; { procedury INIT }
Protože mechanismus vyhledávání je obsažen v operaci INSERT, nebudeme uvádět samostatnou operaci SEARCH. Operace INSERT podle uvedeného Knuthova algoritmu bude mít následující tvar:
procedure INSERT (var TAB:TYPTAB; K:TYPKLIC; DATAPOLOZKY:TYPDATA;
var RR:POSINT; var ERROR:Boolean);
var I:POSINT;
JESTE, NASEL:Boolean;
begin
I := R(K); { Rozptylovací funkce poskytuje hodnoty z intervalu 1..MAX }
ERROR := false; NASEL := false; { Inicializace Booleovských proměnných }
if not TAB[I].VOLNY
then begin { prvek není volný, hledej v lineárním seznamu }
JESTE := TAB[I].KLIC <> K { Inicializace řídící proměnné cyklu }
while JESTE do begin
I := TAB[I].DALSI; { Index následníka }
if I = 0 then JESTE := false { Konec seznamu }
else JESTE := TAB[I].KLIC <> K;
end;
if I = 0 then begin NASEL := true;
TAB[I].DATA := DATAPOLOZKY { Přepis při nalezení }
end;
if not NASEL then begin { Vyhledej místo pro vkládanou položku }
while (RR = 0) and (not TAB[RR].VOLNY) do RR:=RR-1;
ERROR := RR = 0;
if not ERROR then begin
TAB[I].DALSI := RR; { připojení k seznamu }
I := RR { příprava pro naplnění }
end
end;
if (not NASEL) and (not ERROR) then begin { naplnění složek vkládané položky }
TAB[I].KLIC := K;
TAB[I].DALSI := 0;
TAB[I].DATA := DATAPOLOZKY;
TAB[I].VOLNY := false;
end
end; { procedury INSERT }
4.5. TRP s implicitně zřetězenými synonymy
TRP s implicitně zřetězenými synonymy jsou implementovány jedním polem, které plní jak funkci základního pole (do něhož míří index získaný rozptylovací funkcí), tak oblasti přeplnění. Index následníka v seznamu synonym je dán součtem indexu předchůdce a přírůstku INC. Podle vlastnosti přírůstku dělíme metody s implicitně zřetězenými synonymy takto:
- Lineární vyhledávání (INC je konstantní; nejčatěji INC := 1)
- Kvadratické vyhledávání (INC lineárně vzrůstá; nejčastěji INC := INC + 1)
- Metoda dvou rozptylovacích funkcí (INC je konstantní, ale získá se druhou rozptylovací funkcí (INC := R2(K)
4.5.1. TRP s lineárním vyhledáváním
Vyhledávání v této tabulce postupuje podle pravidel:
- Rozptylovací funkce určí index prvního přístupu do pole tabulky
- Od této pozice se zahájí vyhledávání v sekvenčně umístěném seznamu v poli. Vyhledávání končí úspěšně při nalezení položky s vyhledávaným klíčem, nebo neúspěšně, dojde-li se k prvnímu neobsazenému prvku pole. S polem se pracuje jako s kruhovým seznamem.
Pro zajištění konečnosti neúspěšného vyhledávání se musí zachovat alespoň jedna zarážka ve formě neobsazeného prvku pole. Nejčastěji se to dělá pomocnou proměnnou POCET, která udává počet prvků v tabulce. Je-li POCET právě o 1 menší, než je maximální kapacita, je tabulka zaplněna. (Jinou možností konečnosti vyhledávání je test na shodu s výchozím indexem).
Nechť jsou dány typy:
TYPPOLOZKY = record
KLIC:TYPKLIC;
DATA:TYPDATA;
OBSAZENY:Boolean;
end;
TYPTAB = array [0..MAX] of TYPPOLOZKY;
Operace INIT a INSERT nad TRP s lineárním vyhledáváním budou mít tvar:
procedure INIT (var TAB:TYPTAB; var POCET:POSINT);
var I:POSINT;
begin
for I := 0 to MAX do TAB[I].OBSAZENY := false;
POCET := 0
end
procedure INSERT (var TAB:TYPTAB; K:TYPKLIC; DATAPOLOZKY:TYPDATA;
var POCET:POSINT);
var INC, I:POSINT;
begin
I := R(K); { R(K) je v intervalu 0..MAX }
INC := 1;
while TAB[I].OBSAZENY and (TAB[I].KLIC <> K) do I:=(I+INC) mod (MAX+1);
if TAB[I].KLIC = K then TAB[I].DATA:=DATAPOLOZKY { Našel, přepisuje }
else begin { Vkládá }
TAB[I].KLIC := K;
TAB[I].DATA := DATAPOLOZKY;
TAB[I].OBSAZENY := true;
POCET := POCET + 1;
end
end; { procedury INSERT }
4.5.2. TRP s kvadratickým vyhledáváním
U TRP s lineárním vyhledáváním je častý případ, který se projevuje vytvářením shluků obsazených prvků pole, vznikajících nejčastěji tehdy, je-li přírůstek INC = 1 a jsou-li indexy několika skupin synonym dosti blízké. Situaci lze zlepšit změnou hodnoty INC na hodnotu větší než 1. Hodnota INC však nesmí být dělitelem délky základního pole (aby se zajistil průchod všemi prvky pole).
Jiný významný způsob zabránění vzniku shluků spočívá v kvadratickém vyhledávání. To znamená, že hodnoty indexu po sobě jdoucích prvků vytvářejí kvadratickou funkci. Je-li I0=R(K), pak Il=(I0+l2) mod MAX. Přitom platí Il+1=Il+INCl a INCl+1=INCl+2. Je-li I0=1, pak se při průchodu postupně projde indexy 1, 2, 5, 10, 17, 26, 37 …. Je-li MAX prvočíslo, pak se při neúspěšném vyhledávání v nejhorším případě projde polovinou prvků pole a průchod končí při INC = MAX.
Další metota postupně prochází indexy
I0 = R(K)
I = (I0+0.5*l + 0.5*l2) mod MAX
přičemž platí Il+1=Il+INCl
INCl+1=INCl+1
Je-li I0=1, pak se při průchodu postupně projde indexy 1, 2, 4, 7, 11, 16, 22 …. Pro tuto metodu musí mít MAX hodnotu prvočísla ve tvaru 4n+3 (např. 991).
Nechť je dán typ:
TYPTAB = array [1..PRVOCISLO] of TYPPOLOZKYkde PRVOCISLO=4K+3 pro celé kladné K (např. 991) a TYPPOLOZKY je shodný s typem z předchozího odstavce. Pak operace INIT a INSERT budou mít tento tvar:
procedure INIT (var TAB:TYPTAB);
var I:POSINT;
begin
for I:=1 to PRVOCISLO do TAB[I].OBSAZENY := false;
end;
procedure INSERT (var TAB:TYPTAB; K:TYPKLIC; DATAPOLOZKY:TYPDATA;
var ERROR:Boolean);
var I, INC:POSINT;
KONEC, VLOZIL:Boolean;
begin
INC := 1; { * }
I:=R(K); { R(K) je z intervalu 1..PRVOCISLO }
VLOZIL := false;
repeat
KONEC := false;
if not TAB[I].OBSAZENY then begin { Našel volný prvek, vkládá a končí }
TAB[I].KLIC := K;
TAB[I].DATA := DATAPOLOZKY;
TAB[I].OBSAZENY := true;
KONEC := true; VLOZIL := true;
end
else begin { Prvek není volný }
if TAB[I].KLIC = K then begin { Našel shodu, přepisuje }
TAB[I].DATA := DATAPOLOZKY;
KONEC := true
end
else begin { Připrav index dalšího prvku }
I := I + INC; { * }
if I>PRVOCISLO then I:=I-PRVOCISLO;
INC:=INC+1;
if INC >= (PRVOCISLO div 2) { * }
then begin
KONEC:=true; ERROR := true;
end
end
end
until KONEC
end { procedury INSERT }
Skutečnost, že algoritmus prochází v nejhorším případě jen polovinu prvků tabulky, neubírá metodě na účinnosti. Přesto lze jednoduchou úpravou algoritmus zlepšit tak, aby byla pro každý klíč dostupná celá tabulka. Tato úprava se nazývá „Full Table Quadratic Searching“ – tedy kvadratické vyhledávání v plné TRP. Úprava spočívá ve třech změnách na místech v programu označených { * }.
Místo INC := 1 se uvede INC := - PRVOCISLO
místo I := I + INC se uvede I := I + abs(INC)
místo if INC>=(PRVOCISLO div 2)
se uvede if INC >= PRVOCISLO
4.5.3. TRP s dvojí rozptylovací funkcí
Odstranění shluků v TRP se může dosáhnout také s přírůstkem INC, který je sice konstantní, ale jeho hodnota se získá druhou rozptylovací funkcí z klíče K. Zatímco první rozptylovací funkce R(K) dává hodnotu z intervalu 0..MAX, druhá rozptylovací funkce Q(K) musí mít hodnotu z intervalu 1..MAX takovou, která není dělitelem čísla MAX+1. (Bude-li MAX+1 prvočíslo, pak to může být každé číslo z daného intervalu; bude-li (MAX+1)=2m, pak to může být každé liché číslo z intervalu 1..(2m-1) ).
Nechť je dán typ:
TYPTAB = array [0..MAX] of TYPPOLOZKY; { MAX+1 je prvočíslo }
Operace INIT a INSERT pak budou mít následující tvar:
procedure INIT (var TAB:TYPTAB; var POCET:POSINT);
var I:POSINT;
begin
for I:=) to MAX do TAB[I].OBSAZENY := false;
POCET := 0;
end;
procedure INSERT (var TAB:TYPTAB; K:TYPKLIC; DATAPOLOZKY:TYPDATA;
var POCET:POSINT; var ERROR:Boolean);
var I, INC:POSINT;
NASEL, KONEC:Boolean;
begin
ERROR := false;
NASEL := false;
I := R(K); { Funkce dává hodnotu z intervalu 0..MAX }
if TAB[I].OBSAZENY then { Prvek není volný }
if TAB[I].KLIC = K
then NASEL := true { Našel shodu }
else begin { Hledej v seznamu }
INC := Q(K); { Funkce dává hodnotu z intervalu 1..MAX }
repeat
KONEC := false;
I := I + INC;
if I > MAX then I := I – MAX – 1;
if not TAB[I].OBSAZEN
then KONEC := true { Našel volný, končí }
else if TAB[I].KLIC = K then begin { Našel shodu, končí }
KONEC := true; NASEL := true;
end
until KONEC;
end;
if NASEL then TAB[I].DATA := DATAPOLOZKY { Přepisuje nalezenou položku }
else if POCET = MAX then ERROR := true
else begin { Vkládá novou položku }
POCET := POCET + 1;
TAB[I].DATA := DATAPOLOZKY;
TAB[I].KLIC := K;
TAB[I].OBSAZENY := true
end
end; { procedury INSERT }
4.5.4. Brentova varianta
Brentova varianta vychází z metody dvou rozptylovacích funkcí a předpokládá, že úspěšné vyhledávání je častější než neúspěšné vyhledání a následným vkládáním nového prvku. Algoritmus vkládání je složitější, ale má za důsledek zkrácení úspěšného vyhledávání. Metoda používá dvou rozptylovacích funkci R a Q stejných jako v předcházející metodě.
Popis Brenotvy varianty najdete v literatuře.
4.6. Operace DELETE v TRP
U jednotlivých metod TRP byly uvedeny většinou pouze operace INIT a INSERT. Z operace INSERT kze snadno odvodit algoritmus operací SEARCH a READ. Poněkud složitější je to s operací DELETE. V metodách s explicitním zřetězením lze vyřazovaný prvek vyloučit na principu operace DELETE v jednosměrném zřetězeném seznamu (u Knuthovy varianty by se měl aktualizovat pomocný ukazatel RR).
U TRP s implicitním zřetězením je jedinou praktickou možností „zaslepení“ vylučované položky. Nastavením složky OBSAZENY na hodnotu false by se totiž porušilo implicitní zřetězení mezi přechůdcem a následníkem vyřazovaného prvku. Zaslepení však vyžaduje indikaci zaslepeného prvku. Místo složky OBSAZENY lze definovat např. složku STAV:(VOLNY, OBSAZENY, SLEPY). Operaci INSERT lze pak upravit tak, že si při vyhledávání pamatuje index první slepé položky v procházeném seznamu a na tento index pak vloží novou položku v případě neúspěšného vyhledání.
4.7. Hodnocení vyhledávání v tabulkách s rozptýlenými pložkami
U tabulek, které jsou celé implementované polem, hraje nejdůležitější roli pro hodnocení délky vyhledávání koeficient zaplnění tabulky a=POCET/MAX (poměr počtu prvků v tabulce k maximálnímu možnému počtu).
Analýza jednotlivých metod není jednoduchá a analytické vyjádření průměrné doby úspěšného a neúspěšného vyhledávání mají podobu vztahů jen zřídka použitelných v praxi.
Metoda lineárního vyhledávání potřebuje větší počet porovnání než ostatní metody, ale její výhodou je jednoduchost. Uvážíme-li, že při 90% zaplnění potřebuje pro úspěšné vyhledání v průměru méně než 5,5 porovnání, lze říci, že metoda je užitečná. Pro vložení nové položky po neúspěšném vyhledání však potřebuje při tomto zaplnění v průměru 50,5 porovnání.
Metody s explicitním zřetězením jsou ekonomické s ohledem na počet porovnání, ale jejich nevýhodou je to, že pro řetězící ukazatele potřebují více paměti. Jsou-li položky paměti krátké, může se ukázat, že je výhodnější větší tabulka s implicitním zřetězením než menší tabulka s explicitním zřetězením.
Z uvedených metod se jeví nejúčinnější Brentova varianta, která umožňuje úspěšné vyhledání v zaplněné tabulce s průměrem 2,5 porovnání. Neúspěšné vyhledávání s vložením nové položky je však pomalé a vyžaduje cca 0,5*N porovnání.
Ze srovnání s jinými vyhledávacími metodami vyplývá, že tabulky s rozptýlenými položkami jsou rychlejší než binární vyhledávání, zejména pro větší N. Binární vyhledávání je přitom vhodné jen pro statické tabulky. Tabulky s rozptýlenými položkami jsou rychlejší než vyhledávání ve stromech, je-li počet prvků řádově vyšší než 100.
Literatura
[1] skriptum PROGRAMOVACÍ TECHNIKY – Doc. Ing. Jan Honzík a kolektiv
