Universaali tiiviste
Universaali tiiviste on hajautusalgoritmi, jolla on tiettyjä matemaattisia ominaisuuksia. Täydellinen tiiviste on hajautusalgoritmi, jossa kaikki haut suoritetaan O(1) ajassa.[1]
Hajautusalgoritmia käytetään säilömään tiedot, jotka on kerran laskettu jotta niitä ei tarvitse laskea uudelleen.[1] Lisäksi on useita sovelluksia muun muassa kryptografiassa.[1] Hajautusalgoritmi laskee tiivisteen, jonka haittana on että tietylle joukolle S on N elementtiä, jotka viittaavat samaan.[1] Monet yksinkertaiset hajautusalgoritmit toimivat hyvin käytännössä tyypilliselle joukolle S.[1] Törmäysten välttämiseksi hajautusalgoritmissa voidaan käyttää huolella valikoitua satunnaisuutta, jolloin suorituskyvyn voidaan ennakoida olevan hyvä ja saadaan universaali tiiviste.[1][2]
Lähteet muokkaa
- ↑ a b c d e f Universal and Perfect Hashing (PDF) cs.cmu.edu. Viitattu 12.4.2022. (englanniksi)
- ↑ Universal hashing (PDF) mi.fu-berlin.de. Viitattu 12.4.2022. (englanniksi)
Aiheesta muualla muokkaa
- Lecture 14: Universal Hash Function Family (PDF) (englanniksi)
- Lecture 5 - Universal Hashing and Perfect Hashing (englanniksi)