BPC-ALD - Skripta_rev2019_2

Příklad.  Tabulka  z předchozího  příkladu  se  zřetězením.  Všechny  prvky  jsou  nyní  uloženy 
v seznamech. 

Složitost hašování 

Další možnost 
řešení konfliktů 
je metoda 
zřetězení, která 
využívá 
seznamy.

− 88 − 

Při  vyhledávání  je  složitost  dána  složitostí  výpočtu  hašovací  funkce  a  složitostí  vlastního 
vyhledávání.  Složitost  hašovací  funkce  závisí  na  tom,  jak  se  počítá.  Nicméně  ji  můžeme 
považovat za konstantní. Například u řetězců pracujeme buďto s řetězci, které mají omezenou 
délku,  anebo  případně  můžeme  pro  výpočet  hašovací  funkce  brát  jen  omezený  počet  znaků 
z řetězce, například uvažujeme jen jeho 20 znaků. 

Nejlepší  situace  v hašování  je,  když  při  ukládání  prvků  (vytváření  hašovací  tabulky)  nedojde 
k žádné  kolizi,  pak  složitost  vyhledávání  je  viditelně 

Θ(1),  což  neposkytuje  žádná  dosud 

popsaná  vyhledávací  metoda.  Běžně  ale  kolize  nastávají.  Složitost  přirozeně  roste  s počtem 
kolizí v tabulce. Budeme-li uvažovat metodu zřetězení pro řešení konfliktů, pak pro vyhledání 
prvku potřebujeme počet srovnání, který se pohybuje od 1 (když prvek je okamžitě nalezen) až 
po maximum z délek seznamů (když prohledáváme seznam s dalšími prvky se stejnou hodnotou 
hašovací funkce). Věcně vzato, jestliže zvolíme dostatečně velkou hašovací tabulku vzhledem 
k očekávanému  množství  ukládaných  prvků  (tj.  o  něco  větší)  a  zvolíme  dostatečně  kvalitní 
hašovací funkci, která rovnoměrně zobrazuje prvky do hašovací tabulky, lze očekávat že počet 
srovnání potřebný pro vyhledání prvku bude typicky velmi nízký, tedy jen několik srovnání.