Hash -tabelldatastrukturopplæring

I informatikk betyr ordet "kart" å koble et element i ett sett til et annet element i et annet sett. Se for deg at det på en side er ord i en sirkel til venstre, og på høyre side av samme side er det en annen sirkel som det er andre ord. Anta at i hver sirkel er ordene skrevet tilfeldig, spredt i sirkelen. Anta også at ordene i venstre sirkel kalles nøkler, og ordene i høyre sirkel kalles verdier. Hvis en pil trekkes fra hvert ord til venstre til hvert ord til høyre, vil det bli sagt at tastene er blitt kartlagt til verdiene.

Anta at du er eier av en stor bestemmelsesbutikk i fylket der du bor. Anta at du bor i et stort område, som ikke er et kommersielt område. Du er ikke den eneste med en bestemmelsesbutikk i området; Du har noen få konkurrenter. Og så forekommer det deg at du bør registrere telefonnumrene til kundene dine i en treningsbok. Selvfølgelig er treningsboken liten, og du kan ikke registrere alle telefonnumrene for alle kundene dine.

Så du bestemmer deg for å registrere bare telefonnumrene til dine vanlige kunder. Og så har du et bord med to kolonner. Kolonnen til venstre har navnene på kunder, og kolonnen til høyre har de tilsvarende telefonnumrene. På denne måten er det en kartlegging mellom kundenavn og telefonnumre. Den høyre kolonnen i tabellen kan betraktes som kjernen Hash -tabellen. Kundenavn kalles nå nøkler, og telefonnumrene kalles verdier. Merk at når en kunde går på overføring, må du avbryte raden hans, slik at raden er tom eller erstattes med den til en ny vanlig kunde. Legg også merke til at med tiden kan antallet vanlige kunder øke eller redusere, og at tabellen kan vokse eller krympe.

Som et annet eksempel på kartlegging, antar du at det er en klubb av bønder i et fylke. Selvfølgelig vil ikke alle bøndene være medlemmer av klubben. Noen medlemmer av klubben vil ikke være vanlige medlemmer (til stede og bidrag). Barmannen kan bestemme seg for å registrere navnene på medlemmene og deres valg av drikke. Han utvikler et bord med to kolonner. I venstre kolonne skriver han navnene på klubbmedlemmene. I høyre kolonne skriver han det tilsvarende drikkevalget.

Det er et problem her: det er duplikater i høyre kolonne. Det vil si at samme navn på en drink blir funnet mer enn en gang. Med andre ord, forskjellige medlemmer drikker den samme søte drikken eller den samme alkoholholdige drikken, mens andre medlemmer drikker en annen søt eller alkoholholdig drikke. Barmannen bestemmer seg for å løse dette problemet ved å sette inn en smal kolonne mellom de to kolonnene. I denne midterste kolonnen, fra toppen, nummererer han radene som begynner fra null (i.e. 0, 1, 2, 3, 4, etc.), gå ned, en indeks per rad. Med dette blir problemet hans løst, som et medlemsnavn nå kartlegger en indeks, og ikke til navnet på en drink. Så som en drink blir identifisert av en indeks, blir et kundenavn kartlagt til den tilsvarende indeksen.

Verdisøylen (drinker) alene danner den grunnleggende hasjbordet. I den modifiserte tabellen danner kolonnen med indekser og tilhørende verdier (med eller uten duplikater) en normal hasjtabell - full definisjon av en hasjtabell er gitt nedenfor. Tastene (første kolonnen) utgjør ikke nødvendigvis en del av hasjbordet.

Som et annet eksempel igjen, bør du vurdere en nettverksserver der en bruker fra klientdatamaskinen hans kan legge til litt informasjon, slette litt informasjon eller endre litt informasjon. Det er mange brukere for serveren. Hvert brukernavn tilsvarer et passord som er lagret på serveren. De som vedlikeholder serveren kan se brukernavnene og tilsvarende passord, og slik kan ødelegge brukerens arbeid.

Så eieren av serveren bestemmer seg for å produsere en funksjon som krypterer et passord før den er lagret. En bruker logger seg på serveren, med sitt normale forstått passord. Imidlertid lagres hvert passord i en kryptert form. Hvis noen ser et kryptert passord og prøver å logge inn ved å bruke det, vil det ikke fungere, fordi det å logge inn, mottar et forstått passord av serveren, og ikke et kryptert passord.

I dette tilfellet er det forståelige passordet nøkkelen, og det krypterte passordet er verdien. Hvis det krypterte passordet er i en kolonne med krypterte passord, er den kolonnen en grunnleggende hasjtabell. Hvis den kolonnen er gitt en annen kolonne med indekser som begynner fra null, slik at hvert kryptert passord er tilknyttet en indeks, danner både kolonnen med indekser og den krypterte passordkolonnen en normal hasjtabell. Tastene er ikke nødvendigvis en del av hasjbordet.

Legg merke til i dette tilfellet at hver tast, som er et forstått passord, tilsvarer et brukernavn. Så det er et brukernavn som tilsvarer en nøkkel som er kartlagt til en indeks, som er assosiert med en verdi som er en kryptert nøkkel.

Definisjonen av en hasjfunksjon, den fulle definisjonen av en hasjtabell, betydningen av en matrise og andre detaljer er gitt nedenfor. Du må ha kunnskap på pekere (referanser) og koblede lister, for å sette pris på resten av denne opplæringen.

Betydning av hasjfunksjon og hasjbord

Array

En matrise er et sett med påfølgende minneplasser. Alle stedene har samme størrelse. Verdien på det første stedet er tilgjengelig med indeksen, 0; Verdien på det andre stedet er tilgjengelig med indeksen, 1; Den tredje verdien får tilgang til indeksen, 2; fjerde med indeks, 3; og så videre. En matrise kan normalt ikke øke eller krympe. For å endre størrelsen (lengden) på en matrise, må det opprettes en ny matrise, og tilsvarende verdier kopieres til den nye matrisen. Verdiene til en matrise er alltid av samme type.

Hash -funksjon

I programvare er en hasjfunksjon en funksjon som tar en nøkkel og produserer en tilsvarende indeks for en matrisecelle. Matrisen er av fast størrelse (fast lengde). Antall nøkler er av vilkårlig størrelse, vanligvis større enn størrelsen på matrisen. Indeksen som følge av hasjfunksjonen kalles en hasjverdi eller en fordøyelse eller en hasjkode eller bare en hasj.

Hashbord

En hash -tabell er en matrise med verdier, hvis indekser, nøkler blir kartlagt. Tastene er indirekte kartlagt til verdiene. Faktisk sies nøklene å være kartlagt til verdiene, siden hver indeks er assosiert med en verdi (med eller uten duplikater). Imidlertid funksjonen som kartlegger (i.e. hashing) relaterer nøkler til matriseindeksene og egentlig ikke til verdiene, da det kan være duplikater i verdiene. Følgende diagram illustrerer en hasjtabell for navnene på mennesker og deres telefonnumre. Arraycellene (spor) kalles bøtter.

Legg merke til at noen bøtter er tomme. En hasjbord må ikke nødvendigvis ha verdier i alle bøttene. Verdiene i bøttene må ikke nødvendigvis være i stigende rekkefølge. Imidlertid er indeksene de er tilknyttet i stigende rekkefølge. Pilene indikerer kartleggingen. Legg merke til at nøklene ikke er i en matrise. De trenger ikke å være i noen struktur. En hasjfunksjon tar en hvilken som helst nøkkel, og hashes ut en indeks for en matrise. Hvis det ikke er noen verdi i bøtta tilknyttet indeksen, kan det settes en ny verdi i den bøtta. Det logiske forholdet er mellom nøkkelen og indeksen, og ikke mellom nøkkelen og verdien forbundet med indeksen.

Verdiene til en matrise, som de i denne hasjbordet, er alltid av samme datatype. En hasjbord (bøtter) kan koble nøkler til verdiene til forskjellige datatyper. I dette tilfellet er verdiene til matrisen alle pekere, og peker på forskjellige verdistyper.

En hasjbord er en matrise med en hasjfunksjon. Funksjonen tar en nøkkel og hashes en tilsvarende indeks, og kobler slik nøkler til verdier, i matrisen. Tastene trenger ikke å være en del av hasjbordet.

Hvorfor matrise og ikke koblet liste for hasjbord

Maten for en hasjtabell kan erstattes av en koblet listedatastruktur, men det ville være et problem. Det første elementet i en koblet liste er naturlig ved indeks, 0; Det andre elementet er naturlig ved indeks, 1; Den tredje er naturlig ved indeks, 2; og så videre. Problemet med den koblede listen er at for å hente en verdi, må listen itereres gjennom, og dette tar tid. Å få tilgang til en verdi i en matrise er ved tilfeldig tilgang. Når indeksen er kjent, oppnås verdien uten iterasjon; Denne tilgangen er raskere.

Kollisjon

Hashfunksjonen tar en nøkkel og hash den tilsvarende indeksen, for å lese den tilhørende verdien, eller for å sette inn en ny verdi. Hvis formålet er å lese en verdi, er det ikke noe problem (ikke noe problem), så langt. Imidlertid, hvis formålet er å sette inn en verdi, kan hash -indeksen allerede ha en tilhørende verdi, og det er en kollisjon; Den nye verdien kan ikke settes der det allerede er en verdi. Det er måter å løse kollisjon på - se nedenfor.

Hvorfor kollisjon oppstår

I eksemplet på bestemmelsen om ovenfor er kundenavn nøklene, og navnene på drinkene er verdiene. Legg merke til at kundene er for mange, mens matrisen har en begrenset størrelse, og ikke kan ta alle kundene. Så bare drinkene til vanlige kunder er lagret i matrisen. Kollisjonen ville oppstå når en ikke-regelmessig kunde blir regelmessig. Kunder for butikken danner et stort sett, mens antall bøtter for kunder i matrisen er begrenset.

Med hash -tabeller er det verdiene for nøklene som er veldig sannsynlig, som er spilt inn. Når en nøkkel som ikke var sannsynlig, blir sannsynlig, ville det sannsynligvis være en kollisjon. Faktisk forekommer kollisjon alltid med hasjbord.

Grunnleggende om kollisjonsoppløsning

To tilnærminger til kollisjonsoppløsning kalles separat kjetting og åpen adressering. I teorien skal nøklene ikke være i datastrukturen eller skal ikke være en del av hasjbordet. Imidlertid krever begge tilnærminger at nøkkelkolonnen går foran hasjtabellen og blir en del av den generelle strukturen. I stedet for at nøkler er i tastenes kolonne, kan pekere til nøklene være i tastenes kolonne.

En praktisk hash -tabell inkluderer en nøkkelkolonne, men denne nøkkelkolonnen er ikke offisielt en del av hasjbordet.

Enten tilnærming for oppløsning kan ha tomme bøtter, ikke nødvendigvis på slutten av matrisen.

Separat kjetting

I separat kjetting, når en kollisjon oppstår, legges den nye verdien til høyre (ikke over eller under) av den kolliderte verdien. Så to eller tre verdier ender opp med å ha samme indeks. Sjelden mer enn tre skal ha samme indeks.

Kan mer enn en verdi virkelig ha samme indeks i en matrise? - Nei. Så i mange tilfeller er den første verdien for indeksen en peker til en koblet listedatastruktur, som inneholder One, Two eller Three Collided Values. Følgende diagram er et eksempel på en hasjtabell for separat kjetting av kunder og deres telefonnumre:

De tomme bøttene er merket med bokstaven x. Resten av sporene har pekere på koblede lister. Hvert element i den koblede listen har to datafelt: det ene for kundenavnet og det andre for telefonnummeret. Konflikt oppstår for nøklene: Peter Jones og Suzan Lee. De tilsvarende verdiene består av to elementer i en koblet liste.

For motstridende nøkler er kriteriet for å sette inn verdi det samme kriteriet som brukes til å lokalisere (og lese) verdien.

Åpen adressering

Med åpen adressering lagres alle verdier i bøtte -matrisen. Når det oppstår konflikt, settes den nye verdien inn i en tom bøtte ny den tilsvarende verdien for konflikten, etter noe kriterium. Kriteriet som brukes til å sette inn en verdi ved konflikt er det samme kriteriet som brukes til å lokalisere (søke og lese) verdien.

Følgende diagram illustrerer konfliktløsning med åpen adressering:

Hashfunksjonen tar nøkkelen, Peter Jones og hashes indeksen, 152, og lagrer telefonnummeret sitt på den tilhørende bøtta. Etter en tid hash Hash -funksjonen den samme indeksen, 152 fra nøkkelen, Suzan Lee, kolliderer med indeksen for Peter Jones. For å løse dette lagres verdien for Suzan Lee i bøtta til neste indeks, 153, som var tom. Hashfunksjonen henger indeksen, 153 for nøkkelen, Robin Hood, men denne indeksen har allerede blitt brukt til å løse konflikten for en tidligere nøkkel. Så verdien for Robin Hood er plassert i neste tomme bøtte, som er indeksen 154.

Metoder for å løse konflikter for separat kjetting og åpen adressering

Separat kjetting har sine metoder for å løse konflikter, og åpen adressering har også sine egne metoder for å løse konflikter.

Metoder for å løse separate kjettingskonflikter

Metodene for separate kjetting hash -tabeller blir kort forklart nå:

Separat kjetting med koblede lister

Denne metoden er som forklart ovenfor. Imidlertid må hvert element i den koblede listen ikke nødvendigvis ha nøkkelfeltet (e.g. Kundenavn felt over).

Separat kjetting med listehodeceller

I denne metoden lagres det første elementet i den koblede listen i en bøtte med matrisen. Dette er mulig, hvis datatypen for matrisen er elementet i den koblede listen.

Separat kjetting med andre strukturer

Enhver annen datastruktur, for eksempel det selvbalanserende binære søketreet som støtter de nødvendige operasjonene, kan brukes i stedet for den koblede listen - se senere.

Metoder for å løse åpen adressering av konflikter

En metode for å løse konflikt i åpen adressering kalles sondesekvens. Tre kjente sondesekvenser blir kort forklart nå:

Lineær sondering

Med lineær sondering, når det oppstår en konflikt, blir den nærmeste tomme bøtta under bøtta ved konflikt, sett etter. Også med lineær sondering lagres både nøkkelen og verdien i samme bøtte.

Kvadratisk sondering

Anta at konflikt skjer ved indeks h. Neste tomme spor (bøtte) ved indeks h + 1² benyttes; Hvis det allerede er okkupert, er den neste tomme en på H + 2² brukes, hvis det allerede er okkupert, så den neste tomme ved H + 3² brukes, og så videre. Det er varianter av dette.

Dobbel hashing

Med dobbel hashing er det to hasjfunksjoner. Den første beregner (hasj) indeksen. Hvis det oppstår en konflikt, bruker den andre den samme nøkkelen for å bestemme hvor langt nedover verdien skal settes inn. Det er mer med dette - se senere.

Perfekt hashfunksjon

En perfekt hasjfunksjon er en hasjfunksjon som ikke kan resultere i noen kollisjon. Dette kan skje når settet med nøkler er relativt lite, og hver nøkkel kartlegger et bestemt heltall i hasjbordet.

I ASCII -tegnsett kan store bokstaver kartlegges til deres tilsvarende små bokstaver ved hjelp av en hasjfunksjon. Brev er representert i datamaskinminnet som tall. I ASCII -tegnsett er A 65, B er 66, C er 67 osv. og A er 97, B er 98, C er 99 osv. For å kartlegge fra A til A, tilsett 32 til 65; For å kartlegge fra B til B, tilsett 32 til 66; For å kartlegge fra C til C, tilsett 32 til 67; og så videre. Her er store bokstaver nøklene, og små bokstaver er verdiene. Hash -tabellen for dette kan være en matrise hvis verdier er de tilknyttede indeksene. Husk at bøtter av matrisen kan være tomme. Så bøtter i matrisen fra 64 til 0 kan være tomme. Hash -funksjonen legger ganske enkelt 32 til det store bokstavenummeret for å få indeksen, og derav små bokstaver. En slik funksjon er en perfekt hasjfunksjon.

Hashing fra heltall til heltallindekser

Det er forskjellige metoder for hashing heltall. En av dem kalles Modulo Division -metoden (funksjon).

Modulo Division Hashing -funksjonen

En funksjon i dataprogramvare er ikke en matematisk funksjon. I databehandling (programvare) består en funksjon av et sett med utsagn foran med argumenter. For Modulo Division -funksjonen er nøklene heltall og er kartlagt til indekser for utvalget av bøtter. Settet med nøkler er stort, så bare nøkler som sannsynligvis vil oppstå i aktiviteten, vil bli kartlagt. Så kollisjoner oppstår når usannsynlige nøkler må kartlegges.

I uttalelsen,

20/6 = 3r2

20 er utbyttet, 6 er divisoren, og 3 resten 2 er kvotienten. Resten 2 kalles også moduloen. Merk: Det er mulig å ha en modul på 0.

For denne hashing er bordstørrelsen vanligvis en kraft på 2, e.g. 64 = 2⁶ eller 256 = 2⁸, etc. Divisoren for denne hashingfunksjonen er et primtall nær matrisens størrelse. Denne funksjonen deler nøkkelen med divisoren og returnerer moduloen. Moduloen er indeksen for utvalget av bøtter. Den tilhørende verdien i bøtta er en verdi av ditt valg (verdi for nøkkelen).

Hashing variabel lengde nøkler

Her er tastene til nøkkelsettet tekster i forskjellige lengder. Ulike heltall kan lagres i minnet ved å bruke samme antall byte (størrelsen på en engelsk karakter er en byte). Når forskjellige nøkler er av forskjellige bytestørrelser, sies de å være av variabel lengde. En av metodene for hashing av variable lengder kalles radix konverteringshashing.

Radix konverteringshashing

I en streng er hvert tegn på datamaskinen et tall. I denne metoden,

Hash -kode (indeks) = x₀en^{K - 1}+x₁en^{K - 2}+… +X_{K - 2}en¹+x_{K - 1}en⁰

Hvor (x0, x1, ..., xk - 1) er tegnene til inngangsstrengen og a er en radiks, e.g. 29 (se senere). k er antall tegn i strengen. Det er mer med dette - se senere.

Nøkler og verdier

I et nøkkel/verdipar kan det hende at en verdi ikke nødvendigvis er et tall eller tekst. Det kan også være en plate. En post er en liste skrevet horisontalt. I et nøkkel/verdipar kan hver tast faktisk referere til en annen tekst eller nummer eller post.

Assosiativ matrise

En liste er en datastruktur, der listeelementene er relatert, og det er et sett med operasjoner som fungerer på listen. Hver listeelement kan bestå av et par varer. General Hash -tabellen med nøklene kan betraktes som en datastruktur, men det er mer et system enn en datastruktur. Tastene og deres tilsvarende verdier er ikke veldig avhengige av hverandre. De er ikke veldig relatert til hverandre.

På den annen side er et assosiativt utvalg en lignende ting, men nøkler og verdiene deres er veldig avhengige av hverandre; De er veldig relatert til hverandre. For eksempel kan du ha et assosiativt utvalg av frukt og fargene deres. Hver frukt har naturlig sin farge. Navnet på frukten er nøkkelen; Fargen er verdien. Under innsetting settes hver nøkkel inn med verdien. Når du sletter, blir hver tast slettet med verdien.

Et assosiativt utvalg er en hash -tabelldatastruktur sammensatt av nøkkel/verdipar, der det ikke er noen duplikat for tastene. Verdiene kan ha duplikater. I denne situasjonen er nøklene en del av strukturen. Det vil si at nøklene må lagres, mens tastene med den generelle Hast -tastene ikke trenger å lagres. Problemet med de dupliserte verdiene løses naturlig av indeksene for utvalget av bøtter. Ikke forveksle mellom dupliserte verdier og kollisjon i en indeks.

Siden en assosiativ matrise er en datastruktur, har i det minste følgende operasjoner:

Assosiative array -operasjoner

Sett inn eller legg til

Dette setter inn et nytt nøkkel/verdipar i samlingen, og kartlegger nøkkelen til verdien.

tilordne

Denne operasjonen erstatter verdien av en bestemt nøkkel til en ny verdi.

slett eller fjern

Dette fjerner en nøkkel pluss den tilsvarende verdien.

se opp

Denne operasjonen søker etter verdien av en bestemt nøkkel og returnerer verdien (uten å fjerne den).

Konklusjon

En hash -tabelldatastruktur består av en matrise og en funksjon. Funksjonen kalles en hasjfunksjon. Funksjonen kartlegger tastene til verdier i matrisen gjennom indeksene i matrisen. Tastene må ikke nødvendigvis være en del av datastrukturen. Nøkkelsettet er vanligvis større enn de lagrede verdiene. Når en kollisjon oppstår, løses den enten ved den separate kjettingstilnærmingen eller den åpne adresseringsmetoden. Et assosiativt utvalg er et spesielt tilfelle av hash -tabelldatastrukturen.