Hashovanie. Riešenie kolízií.

Zhrnutie prednášky

Prednáška uvádza hešovanie ako spôsob implementácie asociatívnych polí, v ktorých index záznamu vyplýva priamo z jeho obsahu (kľúča). Priame indexovanie podľa reťazcov by viedlo k veľmi riedkej a pamäťovo zbytočne veľkej tabuľke, preto sa používa rýchla hešovacia funkcia, ktorá zobrazuje veľkú množinu kľúčov do malej množiny indexov. Keďže ide o zobrazenie do menšej množiny, vznikajú kolízie, teda rôzne kľúče s rovnakým hešom, a ich riešenie sa preberie neskôr. Veľkosť tabuľky je vhodné voliť ako veľké prvočíslo, napríklad Mersennovo. Praktická časť začína hešovaním čísel s pohyblivou desatinnou čiarkou: hodnota z intervalu sa lineárne zobrazí do intervalu 0 až 1 a vynásobí sa veľkosťou tabuľky zníženou o 1, aby index nepresiahol hranicu tabuľky.

• - Hešovanie umožňuje asociatívne polia, kde index vychádza z obsahu záznamu.
• - Hešovacia funkcia musí byť rýchla a rovnomerne rozdeľovať kľúče, aby bolo kolízií minimum.
• - Heš nie je vratný: z indexu nemožno zistiť pôvodný kľúč, hľadá sa opätovným výpočtom hešu.
• - Kolízia nastáva, keď majú rôzne kľúče rovnaký heš, pretože ide o zobrazenie do menšej množiny.
• - Veľkosť tabuľky sa odporúča voliť ako veľké prvočíslo, napr. Mersennovo (2^n − 1).
• - Heš pre float: (x − min)/(max − min) zobrazí hodnotu do intervalu 0 až 1, násobenie (m − 1) a zaokrúhlenie dá index.
• - Potrebné sú bitové operácie v C a delenie modulo; postupne sa prejde od int a float k reťazcom.

Zhrnutie pripravené s pomocou AI z prepisu videa.