13-Vyhledavani

chceme vyhledávat.  

• Hašovací funkce 

• Zobrazení, které prvku (nebo klíče prvku v případě strukturovaných prvků) 

přiřadí číslo řádku v tabulce (tj. index  prvku v poli). 

klíči

Hašovací funkce 

• Typicky se skládá ze dvou částí (funkcí): 

• První funkce zobrazí hodnotu prvku resp. klíče (např. řetězce) na celé číslo. 

• Funkce závislá na datovém typu prvku, vytváříme si ji sami. 

• Druhá funkce zobrazí toto celé číslo na číslo řádku v tabulce, tedy na celé číslo 

z intervalu  0, 𝑚 − 1 , kde 𝑚 je počet řádků tabulky. 

• Standardní funkce nezávislá na datovém typu prvku. 

Hašovací funkce 

• Hašovací funkce by měla rovnoměrně rozmisťovat prvky v tabulce. 

Proto by první funkce, která převádí hodnotu prvku na celé číslo, měla 
mít následující vlastnosti: 

• Zobrazovat hodnoty prvků na co největší počet celých čísel. 
• Zobrazení na celá čísla by mělo být rovnoměrné. 

• Na jednotlivá čísla by se měl zobrazovat přibližně stejný počet prvků, které chceme do 

tabulky ukládat. 

• Výpočet hodnoty hašovací funkce by neměl být časově náročný. 

Hašovací funkce pro řetězce 

• Řetězec se skládá ze znaků, které jsou kódovány (ASCII, UTF-4, …) 

• Např. ASCII tabulka přiřazuje znakům čísla  0, 127 . 

• Uvažujme řetězec 𝑧1𝑧2 … 𝑧𝑘, kde 𝑧𝑖 jsou jednotlivé znaky a 𝑘 je počet 

znaků. 

• Pro zobrazení řetězce na celé číslo můžeme použít např. následující 

jednoduchou funkci: 

𝑐1 𝑧1𝑧2 … 𝑧𝑘 = 𝑝 ∙ 𝑎𝑠𝑐 𝑧1 + 𝑞 ∙ 𝑎𝑠𝑐 𝑧2 + 𝑎𝑠𝑐 𝑧𝑘 + 𝑘, 

kde 𝑝 a 𝑞 jsou zvolené konstanty. 

• Konstanty 𝑝 a 𝑞 je nejlépe volit jako prvočísla, např. 𝑝 = 127,  𝑞 =