Hashing er navnet på en metode for å avbilde et stort verdiområde ned på et mindre verdiområde, \(a=hashfunksjon(verdi)\). \(hashfunksjon\) velges slik at alle mulige verdier av \(verdi\) gir et resultat innenfor ønsket intervall, som oftest \(0\) til \(n-1\). Hensikten med hashing  er ofte en grovsortering når en skal finne objekter med like eller ulike egenskaper. Hashing brukes i databaser, søkemotorer, og algoritmer hvor en søker likhet eller ulikhet. 

På en skole med ca. 200 elever skal en gruppere elever som har samme fødselsdag. Alle er samlet i gymsalen. Der setter en opp 20 bord med god plass rundt, og merker bordene tydelig med tallene 0 til 19. Så ber en alle elever legge sammen dag og måned i fødselsdato. Trekk så 20 fra summen inntil tallet blir mindre enn 20. Dette blir da nummeret på bordet eleven skal gå til. Når alle har funnet sitt bord vil det gjennomsnittlig være ti elever per bord. Antallet ved hvert bord vil variere, kanskje mellom 5 og 15. Ved hvert bord sier alle etter tur sin fødselsdag, evtuelle andre med samme dag sier fra og går ut av gruppen.  Resten fortsetter til alle har sagt sin fødselsdag. 

Algoritmen kan også brukes til å finne dagen(e) hvor flest elever har fødselsdag. Til slutt må en da sammeligne resultatene i hver gruppe.

Algoritmen er korrekt fordi hvis to elever har samme fødselsdag så vil de garantert komme i samme gruppe.

Hashfunksjonen som er brukt er: \(a = \mod((dag+mnd),20)\), en deler summen av dag og måned med 20 og bruker divisjonsresten som adresse, det vil si bordnummer. Ved å bruke divisjonsrest som siste ledd i en hashformel vil en alltid få et resultat i intervallet \(0\) til \(n-1\) når en har \(n\) adresser til rådighet. En god hashformel skal fordele adressene - verdiene på \(a\), så jevnt som mulig i adresserommet. Spesielt er det uheldig om en får en opphopning av verdier på én eller et fåtall adresser. 

Store deler av algoritmen har parallell utførelse. Hver enkelt elev beregner og går selv til riktig bord. Når alle elever har funnet sitt bord kan en starte spørringen i hver gruppe. Det er en lineær prosess lokalt, men gruppene gjør oppgaven samtidig. Hvor stor parallellitet en vil ha i siste deloppgave bestemmes av gruppestørrelsen. 

Denne algoritmen egner seg derfor godt for utførelse på en parallellmaskin, og som setter oss i stand til å håndere svært store datamengder på kort tid. 

Hashing er ikke egnet for å gruppere verdier som er nesten like. Den vil kun gruppere på absolutt likhet, det vil si absolutt likhet basert på de deler av hashnøkkelen (verdi) som brukes av hashformelen. 

Foreslå endringer i tekst

Foreslå bilder til artikkelen

Kommentarer

Har du spørsmål om eller kommentarer til artikkelen?

Kommentaren din vil bli publisert under artikkelen, og fagansvarlig eller redaktør vil svare når de har mulighet.

Du må være logget inn for å kommentere.