BPC-ALD - Skripta_rev2019_2

V hašování 
používáme k 
uložení prvků 
tabulku. 

− 82 − 

1.  Při  implementaci  hašování  se  tabulka  snadno  realizuje  pomocí  pole.  Datový  typ  se  zvolí 
takový, aby se do něho daly uložit údaje, které ukládáme do řádků tabulky. Tím každý prvek 
pole  reprezentuje  jeden  řádek  tabulky  a  indexování  pole  odpovídá  adresování  jednotlivých 
řádků v tabulce. 

Základem hašování je hašovací funkce. Je to zobrazení, které hodnotě prvku (nebo klíči prvku, 
pokud prvek je strukturovaný typ) přiřadí číslo některého z řádků v tabulce, tedy číslo v rozmezí 
0 až m-1. Hašovací funkce se typicky sestaví ze dvou funkcí. Ta první hodnotu prvku zobrazí na 
celé číslo. Druhá celé číslo zobrazí na číslo řádku v tabulce, tedy na celé číslo z intervalu <0,m-
1>. Je zřejmé, že první funkce závisí na datovém typu prvku a sestavujeme si ji sami, druhá už 
je víceméně standardní a jen ji použijeme. 

Účelem  hašovací  funkce  je  rovnoměrné  rozmístění  prvků  v tabulce.  Z toho  plyne,  že  první 
funkce, která převádí hodnotu prvku na celé nezáporné číslo, by měla mít vlastnosti: 

•  Zobrazovat hodnoty prvků na co největší počet různých 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 hašovací tabulky uložit). 

Vezměme  například  řetězec.  Řetězec  můžeme  chápat  jako  posloupnost  znaků.  Jsou  různé 
možnosti,  jak  tuto  posloupnost  zobrazit  na  celá  čísla.  Nejčastěji  se  při  tom  vychází  z  ASCII 
tabulky, která poskytuje zobrazení znaků na čísla z intervalu <0,255>. Řetězec si označme