ADŠ prednáška 23: Hešovanie 2 - porovnávanie veľkých súborov, univerzálne hešovanie.

Zhrnutie prednášky

Prednáška nadväzuje na tému hashovania a rozoberá teoretické aj praktické aspekty rozhadzovania prvkov do hashovacej tabuľky. Vysvetľuje sa pravdepodobnostný výsledok o maximálnej obsadenosti priehradky pri náhodnom hádzaní N guličiek do N priehradiek, ktorá rastie ako log N / log log N. Keďže hashovacia funkcia musí byť deterministická, v praxi sa používajú fixné funkcie (napríklad modulo prvočíslo veľkosti poľa), ktoré sa pri rozumných dátach správajú takmer ako náhodné rozhadzovanie. Prednáška analogicky pripomína randomizovaný quicksort, kde náhoda nezaručuje korektnosť odpovede, ale ovplyvňuje rýchlosť behu, a s vysokou pravdepodobnosťou dáva dobrú časovú zložitosť. Na záver sa uvádza motivačný príklad, ktorý demonštruje využitie náhody na jedinú kontrolu ako prípravu na univerzálne hashovanie.

• - Cieľom hashovania je dosiahnuť takmer konštantnú časovú zložitosť operácií nad množinou/asociatívnym poľom.
• - Pri náhodnom rozhadzovaní N prvkov do N priehradiek rastie maximálna obsadenosť priehradky asymptoticky ako log N / log log N.
• - Hashovacia funkcia musí byť deterministická, aby vždy vrátila rovnaký index pre rovnaký prvok.
• - V praxi sa používajú fixné hashovacie funkcie (napr. modulo prvočíslo) fungujúce dobre pre 'rozumné' dáta bez záškodníka.
• - Voľba veľkosti poľa ako prvočísla zabezpečuje, že každý bit vstupu ovplyvňuje výslednú hashovaciu hodnotu.
• - Analógia s randomizovaným quicksortom: náhoda nezaručuje korektnosť, ale ovplyvňuje rýchlosť behu algoritmu, pričom s vysokou pravdepodobnosťou dosahuje dobrú zložitosť.
• - Predstavuje sa prechod k pokročilejšej téme – využitiu náhody na zlepšenie hashovania (smerom k univerzálnemu hashovaniu).

Zhrnutie pripravené s pomocou AI z prepisu videa.