Wikipedia

Ero sivun ”Hajautusalgoritmi” versioiden välillä

Selaa historiaa interaktiivisesti
[arvioimaton versio][arvioimaton versio]
← Vanhempi muutosUudempi muutos →
Poistettu sisältö Lisätty sisältö
VisuaalinenWikiteksti
Anurmi (keskustelu | muokkaukset)
223 muokkausta
täsmennys- ja yhdistyshuomautukset
Jonkinlainen yritys saada termistöä kuntoon, + sekalaisia korjauksia.
Rivi 1:
{{tämä artikkeli|käsittelee [[hajautustaulu]]un liittyvää hajautusalgoritmia. Katso myös yleisempi käsite [[tiiviste]], joka käsittelee myös [[salaus]]ta ja [[todennus]]ta vastaavalla tekniikalla.}}
{{YhdistettäväArtikkeliin|hajautustaulu}}
'''Hajautusfunktio''' 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.
'''Hajautusfunktio''' on [[algoritmi]], jota
käytetään [[tietorakenne|tietorakenteen]] ''hajautustaulun'', eli ''tiivisteen'', toteuttamisessa. 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, esim. käyttämällä ketjutusta. Ohessa yksinkertainen esimerkki pelkistetystä (ja moneen tarkoitukseen huonosta) hajautusfunktiosta pseudokoodina:
 
<pre>
function compute_hashlaske_tiiviste(stringmerkkijono):
slot_sizetaulukon_koko = 1000
numsumma = 0
for charmerkki in stringmerkkijono:
numsumma = numsumma + ascii_orginalascii(charmerkki)
quotientjakojaannos = mod(numsumma, slot_sizetaulukon_koko) # 0 <= quotientjakojaannos < slot_sizetaulukon_koko
return quotientjakojaannos
</pre>
 
Hajautustauluna käytetään nyt 1000-alkioista taulukkoa, ja kun jokin arvo halutaan tallentaa taulukkoon käyttäen haluttua merkkijonoa avaimena, arvo tallennetaan taulukon siihen indeksiin, jonka <code>compute_hash(merkkijono)</code> palauttaa.
taulukkoon käyttäen haluttua merkkijonoa avaimena, arvo tallennetaan taulukon siihen indeksiin, minkä <code>compute_hash(merkkijono)</code> palauttaa.
 
== Törmäykset ==
 
Eri merkkijonoista syntyvät samat hajautusarvot johtavat ''törmäyksiin''. KetjuttaessaHajautustarkoituksiin tämähyvä ratkaistaantiiviste sitenon sellainen, ettäjoka samaanminimoi hajautusindeksiin osuneet avaimet muodostavat ketjuntörmäykset, jotaeli käydäänjonka lävitsetuottamat lineaarisesti.tiivisteet Lineaarisuussyötemerkkijonoille eijakautuvat kuitenkaanhajautustauluun tee hajautustaulusta tehotonta, koska hyvä hajautusfunktio tuottaamahdollisimman tasaisesti jakautuneita avaimia.
 
Hajautustauluja käytettäessä on kuitenkin käytännössä aina varauduttava törmäyksiin. Ketjutettaessa tämä ratkaistaan siten, että samaan hajautusindeksiin osuneet avaimet muodostavat ketjun, jota käydään lävitse lineaarisesti. Lineaarisuus ei kuitenkaan tee hajautustaulusta tehotonta, koska hyvä hajautusfunktio tuottaa tasaisesti jakautuneita avaimia. Tällöin täynnä olevaan hajautustauluun tehtävien hakujen [[asymptoottinen kompleksisuus]] on edelleen sama kuin lineaarisessa haussa, O(n), mutta käytännössä hakunopeus on karkeasti ottaen kääntäen verrannollinen hajautustaulun kokoon.
Muita ratkaisuja törmäysten hoitamiseksi antavat kaksoishajautus sekä lineaarimenettely. Lineaarimenettelyssä kokeillaan yksitellen törmäyksen aiheuttaneelle alkiolle seuraavia vapaita lokeroja. Tätä jatketaan niin kauan kunnes vapaa lokero löytyy.▼
 
Muita ratkaisuja törmäysten hoitamiseksi antavat kaksoishajautus sekä lineaarimenettely. Näitä käytettäessä hajautustauluun ei voida tallentaa mielivaltaista määrää arvoja, joten taulun täyttyminen pitää ottaa huomioon.
 
▲Muita ratkaisuja törmäysten hoitamiseksi antavat kaksoishajautus sekä lineaarimenettely. Lineaarimenettelyssä kokeillaan yksitellen törmäyksen aiheuttaneelle alkiolle seuraavia vapaita lokeroja. Tätä jatketaan niin kauan kunnes vapaa lokero löytyy.
<pre>
h(k,i) = (h'(k) + i) mod m | missä h' on jokin hajautusfunktio ja m lokeroiden lukumäärä.
Rivi 66 ⟶ 68:
== Toteutukset ==
 
Nykyään hajautustauluja tarvitsee tai kannattaa toteuttaa harvoin itse. [[C++]]:n [[STL]] sisältää tietorakenteen <code>map</code> ja monet korkean tason ohjelmointikielet tarjoavat valmiit toteutukset (usein nimellä map, hash tai dictionary). Monesti hajautusfunktio on sisäisesti korvattu [[puu (graafiteoria)|tasapainotetulla puurakenteella]], jolloin haku pysyy edelleen nopeana (asymptoottinen kompleksisuus O(log n)), mutta tietorakennetta voidaan dynaamisesti kasvattaa ilmankäymättä kaikkia siihen talletettuja suurempiaarvoja kustannuksialäpi.
 
== Katso myös ==
Rivi 72 ⟶ 74:
* [[SHA]]
* [[kryptografia]]
* [[tiiviste (tietotekniikka)|hajatustauluttiiviste]]
 
[[Luokka:Algoritmit]]
Noudettu kohteesta ”https://fi.wikipedia.org/wiki/Hajautusalgoritmi”