BPC-ALD - Skripta_rev2019_2

U tabulek založených na otevřeném adresování se odebrání prvku řeší tím způsobem, že řádek 
se  po  odebrání  prvku  označí  specifickou  hodnotou.  Toto  označení  ho  odlišuje  od  prázdných 
řádků,  což  jsou  řádky,  do  kterých  nebyl  ještě  uložen  žádný  prvek.  Řádek  takto  označený  je 
v operaci  přidávání  použit  stejným  způsobem  pro  uložení  nového  prvku  jako  prázdný  řádek. 
V operaci vyhledávání se ale tento řádek jen přeskočí a vyhledávání se na něm nezastaví jako u 
prázdného řádku. 

Algoritmy hašování jsou velmi používané. Třeba překladač (kompilátor) je využívá 

pro uložení informací o překládaném programu. Využívají se rovněž v dabázových 
systémech atd.  

Kontrolní otázky  

1.  Jaké sestavíme hašovací funkci? 

U hašování se 
dá dosáhnout 
vynikající 
časová složitost 
vyhledávání. 

− 89 − 

2.  Čím při hašování vznikají kolize a jak je řešíme? 
3.  Jaká je časová složitost hašování? 

Cvičení  

1.  Sestavte hašovací tabulku, do které budou ukládány řetězce. Abychom zjednodušili 

výpočet hašovací funkce, budeme předpokládat, že řetězce budou začínat jen velkými 
písmeny. Pro převod písmen na čísla použijeme velmi jednoduchou funkci, kterou 
nazveme w a která písmena zobrazí na celá čísla podle předpisu 

 w(A)=1, w(B)=2, w(C)=3,… w(Y)=25, w(Z)=26  . 

Pokud písmeno má diakritiku, tak ji zanedbáme. 
Rozsah tabulky bude 7 řádků a hašovací funkce bude velmi jednoduchá 

7

mod

)

)

(

(

)

...

(

1

2

1

k

z

w

z

z

z

h

k

+

=

Uložte do tabulky jména Marta, Petr, Irena. 

2.  Budeme pokračovat v předchozím cvičení a pro řešení konfliktů zvolíme otevřené 

adresování a použijeme dvojí hašování. Další (druhou) hašovací funkce sestavte podle 
první funkce (uvedené v předchozím cvičení). Pak do tabulky uložte jméno Jiří.