streamalism.org

1. Introduksjon

I denne opplæringen vurderer vi hashingteknikker som brukes i forskjellige datastrukturer som gir konstant tidstilgang til elementene deres.

Vi diskuterer nærmere den såkalte bretteteknikk og gi en kort introduksjon til mid-square og binning teknikker.

2. Oversikt

Når vi velger datastrukturer for lagring av objekter, er en av betraktningene om vi trenger å få tilgang til dem raskt.

Java-verktøypakken gir oss ganske mange datastrukturer for lagring av objektene våre. For mer informasjon om datastrukturer, se vår samleside for Java-samlinger som inneholder guider om flere av dem.

Som vi vet, noen av disse datastrukturene lar oss hente elementene deres i konstant tid, uavhengig av antall elementer de inneholder.

Sannsynligvis er den enkleste matrisen. Faktisk får vi tilgang til elementer i matrisen med indeksen. Tilgangstiden avhenger naturligvis ikke av størrelsen på matrisen. Faktisk, bak scenen, bruker mange datastrukturer tungt matriser.

Problemet er at matriseindeksene må være numeriske, mens vi ofte foretrekker å manipulere disse datastrukturene med objekter.

For å løse dette problemet prøver mange datastrukturer å tilordne en numerisk verdi som kan tjene som en matriseindeks til objekter. Vi kaller denne verdien a hash-verdi eller bare en hasj.

3. Hashing

Hashing er en transformasjon av et objekt til en numerisk verdi. Funksjoner som utfører disse transformasjonene kalles hash-funksjoner.

For enkelhets skyld, la oss vurdere hashfunksjoner som forvandler strenger til matriseindekser, det vil si til heltall fra området [0, N] med en endelig N.

Naturlig, en hash-funksjon brukes på et bredt utvalg av strenger. Derfor blir dets “globale” egenskaper viktige.

Dessverre er det ikke mulig at en hash-funksjon alltid forvandler forskjellige strenger til forskjellige tall.

Vi kan overbevise oss selv ganske enkelt om at antall strenger er mye større enn antall heltall i noe område [0, N]. Derfor er det uunngåelig at det er et par ikke-like strenger som en hash-funksjon produserer like verdier for. Dette fenomenet kalles kollisjon.

Vi kommer ikke til å dykke ned i ingeniørdetaljene bak hashfunksjoner, men det er klart at en god hashfunksjon bør prøve å kartlegge jevnlig strengene den er definert i tall.

Et annet åpenbart krav er at en god hashfunksjon skal være rask. Hvis det tar for lang tid å beregne en hash-verdi, kan vi ikke få tilgang til elementer raskt.

I denne opplæringen vurderer vi en av teknikker som prøver å gjøre kartleggingen ensartet samtidig som den opprettholdes raskt.

4. Brettteknikk

Målet vårt er å finne en funksjon som forvandler strenger til matriseindekser. Bare for å illustrere ideen, anta at vi vil at denne matrisen skal ha kapasitet for 105 elementer, og la oss bruke streng Java-språk som et eksempel.

4.1. Beskrivelse

La oss starte med å konvertere strengens tegn til tall. ASCII er en god kandidat for denne operasjonen:

Nå ordner vi tallene vi nettopp har fått i grupper av noen størrelse. Generelt velger vi gruppestørrelsesverdien basert på størrelsen på matrisen vår som er 105. Siden tallene, der vi transformerte tegnene til, inneholder fra to til tre sifre, uten tap av generalitet, kan vi sette gruppestørrelsen til to:

Neste trinn er å sammenkoble tallene i hver gruppe som om de var strenger og finne summen:

Nå må vi ta det siste trinnet. La oss sjekke om tallet 348933 kan tjene som en indeks for vårt utvalg av størrelse 105. Det overgår naturligvis den maksimalt tillatte verdien 99999. Vi kan lett løse dette problemet ved å bruke modulo-operatøren for å finne det endelige resultatet:

348933 % 10000 = 48933

4.2. Avsluttende bemerkninger

Vi ser at algoritmen ikke inkluderer noen tidkrevende operasjoner, og derfor er den ganske rask. Hvert tegn i inngangsstrengen bidrar til det endelige resultatet. Dette faktum hjelper definitivt til å redusere kollisjoner, men ikke for å unngå dem helt.

For eksempel hvis vi ønsket å hoppe over brettingen og brukte modulo-operatøren direkte på den ASCII-transformerte inngangsstrengen (ignorerer overflytproblemet)

749711897321089711010311797103101 % 100000 = 3101

da vil en slik hash-funksjon produsere den samme verdien for alle strenger som har de samme to siste tegnene som inngangsstrengen vår: age, salder, large, og så videre.

Fra beskrivelsen av algoritmen kan vi enkelt se at den ikke er fri for kollisjonene. For eksempel produserer algoritmen den samme hashverdien for Java-språk og vaJa språk strenger.

5. Andre teknikker

Folding Technique er ganske vanlig, men ikke den eneste. Noen ganger kan binning eller midt på torget teknikker kan også være nyttige.

Vi illustrerer ideen deres ved ikke å bruke strenger, men tall (anta at vi allerede på en eller annen måte har forvandlet strengene til tall). Vi vil ikke diskutere fordelene og svakhetene deres, men du kan danne deg en mening etter å ha sett algoritmene.

5.1. Binning-teknikk

Anta at vi har 100 heltall, og vi vil at hasjfunksjonen vår skal kartlegge dem i en matrise på 10 elementer. Da kan vi bare ordne de 100 heltallene i ti grupper på en slik måte at de ti første heltallene havner i den første bin, de andre ti heltallene havner i den andre bin osv.:

5.2. Midt-kvadrat teknikk

Denne algoritmen ble foreslått av John von Neumann, og den tillater oss å generere pseudo-tilfeldige tall fra et gitt tall.

La oss illustrere det på et konkret eksempel. Anta at vi har et firesifret nummer 1111. I følge algoritmen kvadrerer vi den, og oppnår dermed 1234321‬. Nå trekker vi ut fire sifre fra midten, for eksempel 2343. Algoritmen lar oss gjenta denne prosessen til vi er fornøyde med resultatet.

6. Konklusjon

I denne opplæringen vurderte vi flere hashingteknikker. Vi beskrev i detalj foldeteknikken og ga en blitsbeskrivelse av hvordan binning og midterkant kan oppnås.

Som alltid kan vi finne de tilsvarende kodebitene på GitHub-depotet vårt.