Universaali tiiviste

Wikipediasta
Siirry navigaatioon Siirry hakuun

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]

  1. a b c d e f Universal and Perfect Hashing (PDF) cs.cmu.edu. Viitattu 12.4.2022. (englanniksi)
  2. Universal hashing (PDF) mi.fu-berlin.de. Viitattu 12.4.2022. (englanniksi)

Aiheesta muualla

[muokkaa | muokkaa wikitekstiä]
Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.