BPC-ALD - Skripta_rev2019_2

Volba hašovací tabulky je zejména podstatná u metody otevřeného adresování. Volíme ji aspoň 
o  10

%  větší,  než  je  očekávaný  počet  prvků.  Empirické  testy  ukazují,  že  při  90%  zaplnění 

tabulky  je  i  při  nejjednodušší  metodě  řešení  kolizí,  kterou  je  lineární  hledání,  v průměru 
zapotřebí 5,5 srovnání pro nalezení libovolného prvku. U promyšlenějších metod (kvadratické 
hledání, dvojí hašování) je průměrný počet pokusů ještě menší. 

Problémem tabulek s otevřeným adresováním je případ, kdy nelze předvídat počet prvků, které 
do ní budou uloženy, a nelze tedy vyloučit situaci, že tabulka se zaplní do takové míry, že už se 
nenajdou volné pozice pro uložení dalších prvků. Pokud by toto mohlo nastat, je možnost tento 
problém  řešit  tak,  že  vytvoříme  novou,  přiměřeně  větší  hašovací  tabulku,  prvky  z dosavadní 
tabulky  do  ní  přesuneme  a  předchozí  tabulku  zrušíme  (uvolníme  paměť,  která  pro  ni  byla 
vyhrazena).  

Pokud shrneme, co jsme o hašovacích tabulkách doposud uvedli, je zřejmé, že hašování je velmi 
účinná  a  efektivní  metoda  vyhledávání  a  proto  jsou  hašovací  tabulky  velmi  často  používané. 
Navíc  vlastní  algoritmus  a  tím  i  implementace  hašování  je  poměrně  jednoduchý,  mnohem 
jednodušší než třeba vyhledávací stromy. 

Odebírání prvků z hašovací tabulky 

Zatím  jsme  se  zabývali  jen  operací  přidání  prvku.  V řadě  použití  hašovacích  tabulek  to 
postačuje.  Pokud  bychom  potřebovali  i  odebírat  prvky,  pak  je  to  snadné  v tabulkách,  které  
používají  metodu  zřetězení a jsou přitom  tvořeny jen ukazateli a mají všechny prvky uloženy 
v seznamech. Jde o tabulky popsané na konci části, v níž byla popsána  metoda zřetězení. Zde 
odebírání prvku je realizováno odebíráním prvku ze seznamu.