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