BPC-ALD - Skripta_rev2019_2

prvky  na  nich  s hledaným  prvkem  x,  dokud  buďto  hledaný  prvek  nenalezneme  anebo  se 
nedostaneme na prázdný řádek anebo nevyčerpáme všechny možné pozice. 

Příklad. Máme vyhledat jméno Robert v tabulce z předminulého příkladu. 

   h(Robert)=(7*82+3*111+116+6) mod 11 = 6 

Na této pozici je ale jiné jméno - Bohumil. Začneme počítat a prohledávat další možné pozice 

   (6+12) mod 11 = 7  -  Pavel 

− 87 − 

   (6+22) mod 11 = 10 

Vyhledávání skončí na pozici 10, která je prázdná. Jméno Robert tedy v tabulce není. 

4.4.2  Zřetězení 

Předchozí metoda otevřeného adresování má dvě nevýhody: 
•  Počet  prvků, jež  lze  do  tabulky  uložit, je  omezen  její  velikostí.  Pokud  dopředu  neznáme, 

kolik prvků bude do tabulky ukládáno, může se stát, že ji stanovíme malou a dojde k jejímu 
přeplnění. Následné zvětšení velikosti tabulky může být časově náročně. 

•  Při  vyhledávání,  zejména  v dost  zaplněné  tabulce,  procházíme  v důsledku  otevřeného 

adresování  i  prvky,  které  mají  jinou  hodnotu  hašovací  funkce,  čímž  se  doba  vyhledávání 
zvětšuje. 

Tyto nevýhody odstraňuje metoda zřetězení, která k ukládání dalších prvků se stejnou hodnotou 
hašovací funkce využívá seznamy. Řádek v hašovací tabulce v tomto případě má kromě místa 
na uložení prvku dále místo pro ukazatel na seznam. 

Příklad. Tabulka z předchozích příkladů, ale se zřetězením. 

Nebo  druhá  možnost  je,  že  hašovací  tabulka  je  tvořena  jen  ukazateli  a  všechny  prvky  jsou  
uloženy  v seznamech.  Zejména  je  tento  způsob  výhodný  v případě,  kdy  do  hašovací  tabulky 
nejen přidáváme nové prvky, ale rovněž z ní prvky i odebíráme.