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]