13-Vyhledavani

31. Volbou prvočísel dosáhneme nejlepší rovnoměrné zobrazení do 

množiny celých čísel.  
 

Hašovací funkce pro řetězce 

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

31. 

• Volbou prvočísel dosáhneme nejlepší rovnoměrné zobrazení do 

množiny celých čísel. 

• Druhá část hašovací funkce převádí celé číslo na číslo řádku v hašovací 

tabulce. Je to jednoduchý zbytek po dělení 𝑚 (modulo 𝑚). 

• Výsledná hašovací funkce má tvar: 

ℎ 𝑥 = 𝑐 𝑥  𝑚𝑜𝑑 𝑚 

Hašovací funkce pro datum 

•

𝑐 𝑑𝑒𝑛, 𝑚, 𝑚𝑒𝑠𝑖𝑐 𝑟𝑜𝑘 = 𝑝 ∙ 𝑑𝑒𝑛 + 𝑞 ∙ 𝑚𝑒𝑠𝑖𝑐 + 𝑟𝑜𝑘, 
kde 𝑝 a 𝑞 jsou konstanty, nejlépe prvočísla. 

c(den, mesic, rok)

Hašovací funkce – druhá část 

• Druhá část hašovací funkce převádí celé číslo na číslo řádku v hašovací 

tabulce.  

• Je to jednoduchý zbytek po dělení 𝑚 (modulo 𝑚). 
• Výsledná hašovací funkce má tvar: 

ℎ 𝑥 = 𝑐 𝑥  𝑚𝑜𝑑 𝑚 

 
kde 𝑐 𝑥  je první část hašovací funkce. 
 

Hašovací funkce příklad 

• Do tabulky velikost 11 budeme ukládat řetězce. Hašovací funkci 

zvolíme:  

ℎ 𝑧1𝑧2 … 𝑧𝑘 = 𝑐 𝑧1𝑧2 … 𝑧𝑘  𝑚𝑜𝑑 11 

𝑐1 𝑧1𝑧2 … 𝑧𝑘 = 7 ∙ 𝑎𝑠𝑐 𝑧1 + 3 ∙ 𝑎𝑠𝑐 𝑧2 + 𝑎𝑠𝑐 𝑧𝑘 + 𝑘 

• Do tabulky vložíme řetězce: "Eva", "Irena", "Pavel", "Marta", 

"Ivan", "Nina". 
 

Hašovací funkce - kolize 

• Hašovací funkce může více různým prvků přiřadit stejné číslo řádků. 
• Tyto kolize lze řešit pomocí: 

• Otevřeného adresování 
• Zřetězování 

Otevřené adresování 

• V případě, že číslo řádku v tabulce vypočtené hašovací funkcí je