Ero sivun ”Hajautusalgoritmi” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p Botti muokkasi: de:Hashfunktion |
Ei muokkausyhteenvetoa |
||
Rivi 1:
{{tämä artikkeli|käsittelee [[hajautustaulu]]un liittyvää hajautusalgoritmia. Katso myös yleisempi käsite [[Tiiviste (tietotekniikka)|tiiviste]], joka käsittelee myös [[salaus]]ta ja [[todennus]]ta vastaavalla tekniikalla.}}
{{YhdistettäväArtikkeliin|hajautustaulu}}
'''Hajautusfunktio''' ({{k-en|hash function}}) on [[algoritmi]], jota käytetään ''hajautustaulu''[[tietorakenne|tietorakenteen]] toteuttamisessa. Se ottaa syötteeksi merkkijonon (tai helposti merkkijonoksi muutettavan muun tyypin) ja laskee sille ns. ''tiivisteen''. Tätä tiivistettä puolestaan käytetään indeksinä taulukkoon, jota kutsutaan ''hajautustauluksi''. Tyypillisesti hajautustauluja käytetään, kun halutaan indeksoida tietorakennetta käyttäen avaimina merkkijonoja numeeristen arvojen sijaan.
Yksinkertainen ja nopea hajautusalgoritmi perustuu johonkin suurehkoon vakioon ja jakojäännökseen, joka lasketaan vakion ja merkkijonosta muodostetun lukuarvon perusteella. Esimerkiksi hajautustauluun voidaan varata tilaa 1000:lle alkiolle jolloin sisäinen toteutus indeksoi aina taulukon alkioita 0..999. ''Törmäyksistä'' johtuvat päällekkäisyydet voidaan ratkaista usealla tavalla, esimerkiksi käyttämällä ketjutusta. Ohessa esimerkki pelkistetystä (ja moneen tarkoitukseen huonosta) hajautusfunktiosta pseudokoodina:
| |||