Hashing er innen informasjonsteknologi en metode for å avbilde et stort verdiområde ned på et mindre verdiområde ved hjelp av en hashfunksjon. 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.
Hashfunksjonen velges slik at alle mulige verdier gir et resultat innenfor ønsket intervall, som oftest 0 til n–1.
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 sammenligne 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åndtere 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.
Kommentarer
Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.
Du må være logget inn for å kommentere.