nechodím na prednáškyAlgoritmy a dátové štruktúry prednáška 18
Preber si túto prednášku so svojou AI
Skopíruj pripravený podklad a vlož ho do ChatGPT, Claude alebo inej AI — bude ťa učiť alebo skúšať len z tejto prednášky.
Zhrnutie prednášky
Prednáška predstavuje hešovanie ako efektívnejšiu alternatívu k vyvažovaným stromom pri implementácii množiny. Pomocou metafory rozhadzovania guličiek do jamiek a narodeninového paradoxu sa vysvetľuje, prečo pri hešovaní vždy vznikajú kolízie a prečo treba s nimi počítať. Prednáška odbočuje ku kryptografickému hešovaniu (MD5, SHA-256) a k rozdielu medzi požiadavkami na kryptografické a na dátovoštruktúrne hešovacie funkcie. Následne sa vysvetľuje implementácia hešovacej tabuľky pomocou zreťazenia so spájaným zoznamom na každom poličku, ako aj mechanizmus dynamického zväčšovania tabuľky (resize, load factor) pri jej zapĺňaní.
- Hešovanie ako alternatíva k vyvažovaným stromom pre množinu
- Kolízie pri rozhadzovaní prvkov do poľa (guličky a jamky)
- Narodeninový paradox a odhad pravdepodobnosti kolízie
- Kryptografické hešovacie funkcie MD5 a SHA-256
- Odolnosť kryptografických hešovacích funkcií voči kolíziám
- Implementácia hešovacej tabuľky pomocou zreťazenia
- Load factor a dynamické zväčšovanie hešovacej tabuľky
Zhrnutie pripravené s pomocou AI z prepisu videa.
