ADŠ prednáška 22: Hešovanie 1 - princípy, narodeninový paradox, riešenie kolízií zreťazením.

Zhrnutie prednášky

Prednáška úvodným príkladom s toaletnými kabínkami ilustruje princíp náhodného rozmiestňovania prvkov, na ktorý nadväzuje hlavná téma hašovania ako alternatívy k vyvažovaným stromom pri implementácii množiny a asociatívneho poľa. Vysvetľuje sa koncept ideálnej „magickej škatuľky“ (hašovacej funkcie), ktorá by každému prvku jednoznačne a konzistentne priradila voľné políčko v poli, čím by sa dosiahol konštantný čas pre vloženie, vyhľadanie aj vymazanie prvku. Pomocou Dirichletovho princípu sa ukazuje, že žiadna deterministická funkcia nemôže zaručiť bezkolízne rozmiestnenie, keďže univerzum možných vstupov (napr. používateľských mien) je oveľa väčšie než veľkosť tabuľky. Spomína sa aj špeciálny prípad, keď je univerzum prvkov dostatočne malé (napr. čísla prilieb zamestnancov), a preto stačí jednoduché pole bez potreby hašovania.

• - Motivačný príklad s výberom toaletnej kabínky ilustruje princíp náhodného rozmiestňovania.
• - Hašovanie je alternatíva k vyvažovaným stromom pre implementáciu množiny a asociatívneho poľa bez nutnosti usporiadania prvkov.
• - Ideálna hašovacia funkcia (magická škatuľka) by konzistentne priraďovala každému prvku unikátne políčko v poli.
• - Konzistentnosť znamená, že rovnaký prvok musí vždy dostať rovnaký index.
• - Ideálne fungovanie by umožnilo vloženie, vyhľadanie aj vymazanie v konštantnom čase.
• - Dirichletov princíp dokazuje, že deterministická funkcia nutne spôsobuje kolízie, keď je univerzum vstupov väčšie než tabuľka.
• - Ak je množina možných prvkov dostatočne malá (napr. očíslované prilby), stačí jednoduché pole bez potreby hašovacej funkcie.

Zhrnutie pripravené s pomocou AI z prepisu videa.