Phenquestions
Anta at du er eier av en stor proviantbutikk 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 forsyningsbutikk i området; du har noen få konkurrenter. Og så kommer det til deg at du skal registrere telefonnummerene til kundene dine i en øvelsesbok. Selvfølgelig er treningsboken liten, og du kan ikke registrere alle telefonnumrene til alle kundene dine.
Så du bestemmer deg for å registrere bare telefonnumrene til dine vanlige kunder. Og så har du en tabell med to kolonner. Kolonnen til venstre har navnene på kundene, og kolonnen til høyre har de tilsvarende telefonnumrene. På denne måten skjer det en kartlegging mellom kundenavn og telefonnummer. Høyre kolonne i tabellen kan betraktes som kjerneshash-tabellen. Kundenavn kalles nå nøkler, og telefonnumrene kalles verdier. Vær oppmerksom på at når en kunde går på overføring, må du avbryte raden hans, slik at raden er tom eller erstattes med en ny vanlig kundes. Merk også at med tiden kan antall faste kunder øke eller redusere, og slik kan bordet vokse eller krympe.
Anta at det er en klubb med bønder i et fylke som et annet eksempel på kartlegging. Selvfølgelig vil ikke alle bøndene være medlemmer i klubben. Noen medlemmer av klubben vil ikke være vanlige medlemmer (til stede og bidrag). Bar-mannen kan bestemme seg for å registrere navnene på medlemmene og deres valg av drikke. Han utvikler en tabell med to kolonner. I venstre kolonne skriver han navnene på klubbmedlemmene. I høyre kolonne skriver han det tilsvarende valget av drikke.
Det er et problem her: det er duplikater i høyre kolonne. Det vil si at det samme navnet på en drink finnes 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 drikk. Bar-mannen bestemmer seg for å løse dette problemet ved å sette inn en smal kolonne mellom de to kolonnene. I denne midtre kolonnen, som begynner fra toppen, nummererer han radene som begynner fra null (i.e. 0, 1, 2, 3, 4 osv.), går ned, en indeks per rad. Med dette blir problemet hans løst, ettersom et medlemsnavn nå tilordnes til en indeks, og ikke til navnet på en drink. Så når en drink identifiseres av en indeks, tilordnes et kundenavn til den tilsvarende indeksen.
Verdikolonnen (drikke) alene danner den grunnleggende hash-tabellen. I den modifiserte tabellen danner kolonnen med indekser og tilhørende verdier (med eller uten duplikater) en normal hash-tabell - full definisjon av en hash-tabell er gitt nedenfor. Tastene (første kolonne) utgjør ikke nødvendigvis en del av hash-tabellen.
Som et annet eksempel igjen, kan du vurdere en nettverksserver der en bruker fra klientdatamaskinen kan legge til litt informasjon, slette noe informasjon eller endre noe informasjon. Det er mange brukere for serveren. Hvert brukernavn tilsvarer et passord som er lagret på serveren. De som vedlikeholder serveren, kan se brukernavn og tilhørende passord, og slik kunne ødelegge brukernes arbeid.
Så eieren av serveren bestemmer seg for å produsere en funksjon som krypterer et passord før det lagres. En bruker logger seg på serveren, med sitt normale passord. Imidlertid er nå hvert passord lagret i en kryptert form. Hvis noen ser et kryptert passord og prøver å logge inn med det, vil det ikke fungere, fordi innlogging, mottar et forstått passord av serveren, og ikke et kryptert passord.
I dette tilfellet er det forståte 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 hash-tabell. Hvis den kolonnen er foran en annen kolonne med indekser som begynner fra null, slik at hvert krypterte passord er assosiert med en indeks, så danner både kolonnen med indekser og den krypterte passordkolonnen en normal hash-tabell. Tastene er ikke nødvendigvis en del av hasjbordet.
Merk 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 tilordnet en indeks, som er knyttet til en verdi som er en kryptert nøkkel.
Definisjonen av en hash-funksjon, den fullstendige definisjonen av en hash-tabell, betydningen av en matrise og andre detaljer er gitt nedenfor. Du må ha kunnskap i pekere (referanser) og lenkede lister, for å sette pris på resten av denne opplæringen.
Betydningen av Hash-funksjon og Hash-tabell
Array
En matrise er et sett med påfølgende minneplasseringer. Alle stedene er av samme størrelse. Verdien på den første plasseringen er tilgjengelig med indeksen, 0; verdien til det andre stedet er tilgjengelig med indeksen, 1; den tredje verdien er tilgjengelig med 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å en ny matrise opprettes, og tilsvarende verdier kopieres til den nye matrisen. Verdiene til en matrise er alltid av samme type.
Hash-funksjon
I programvare er en hash-funksjon en funksjon som tar en nøkkel og produserer en tilsvarende indeks for en matrixcelle. Matrisen har en 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 hash-funksjonen kalles en hash-verdi eller en sammendrag eller en hash-kode eller bare en hash.
Hash-bord
En hash-tabell er en matrise med verdier, til hvis indekser nøklene er kartlagt. Tastene er indirekte tilordnet verdiene. Faktisk sies det at tastene er kartlagt til verdiene, siden hver indeks er assosiert med en verdi (med eller uten duplikater). Imidlertid funksjonen som gjør kartlegging (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 hashtabell for navnene på personer og telefonnumre. Matrixcellene (spor) kalles bøtter.
Legg merke til at noen bøtter er tomme. En hash-tabell må ikke nødvendigvis ha verdier i alle bøttene. Verdiene i skuffene må ikke nødvendigvis være i stigende rekkefølge. Imidlertid er indeksene som de er knyttet til i stigende rekkefølge. Pilene indikerer kartleggingen. Legg merke til at tastene ikke er i en matrise. De trenger ikke være i noen struktur. En hash-funksjon tar en hvilken som helst tast, og hasher ut en indeks for en matrise. Hvis det ikke er noen verdi i bøtta knyttet til indekshashet, kan det settes en ny verdi i bøtta. Det logiske forholdet er mellom nøkkelen og indeksen, og ikke mellom nøkkelen og verdien som er knyttet til indeksen.
Verdiene til en matrise, som verdiene i denne hash-tabellen, er alltid av samme datatype. En hash-tabell (bøtter) kan koble nøkler til verdiene til forskjellige datatyper. I dette tilfellet er verdiene til matrisen alle pekere, og peker på forskjellige verdityper.
En hash-tabell er en matrise med en hash-funksjon. Funksjonen tar en nøkkel og hashes en tilsvarende indeks, og kobler så nøkler til verdier, i matrisen. Tastene trenger ikke å være en del av hasjbordet.
Hvorfor Array og ikke koblet liste for Hash-tabell
Matrisen for en hash-tabell 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 iteres 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 hashes den tilsvarende indeksen, for å lese den tilknyttede 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 den hashede indeksen allerede ha en tilknyttet verdi, og det er en kollisjon; den nye verdien kan ikke plasseres der det allerede er en verdi. Det er måter å løse kollisjon på - se nedenfor.
Hvorfor kollisjon forekommer
I eksemplet på forsyningsbutikken ovenfor er kundenavnene 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 drikke fra vanlige kunder lagres i matrisen. Kollisjonen vil oppstå når en ikke-vanlig kunde blir vanlig. Kunder for butikken danner et stort sett, mens antall bøtter for kunder i matrisen er begrenset.
Med hashtabeller er det verdiene for tastene som er veldig sannsynlige som blir registrert. Når en nøkkel som ikke var sannsynlig, blir sannsynlig, vil det sannsynligvis være en kollisjon. Faktisk oppstår kollisjon alltid med hasjetabeller.
Grunnleggende om kollisjonsoppløsning
To tilnærminger til kollisjonsoppløsning kalles separat lenking og åpen adressering. I teorien skal nøklene ikke være i datastrukturen eller ikke være en del av hash-tabellen. Begge tilnærmingene krever imidlertid at nøkkelkolonnen går foran hash-tabellen og blir en del av den overordnede strukturen. I stedet for at nøklene er i nøkkelkolonnen, kan pekere til nøklene være i nøkkelkolonnen.
En praktisk hash-tabell inkluderer en nøkkelkolonne, men denne nøkkelkolonnen er ikke offisielt en del av hash-tabellen.
Enten tilnærming for oppløsning kan ha tomme bøtter, ikke nødvendigvis på slutten av matrisen.
Separat lenking
I en egen kjetting, når en kollisjon inntreffer, legges den nye verdien til høyre (ikke over eller under) for den kolliderte verdien. Så to eller tre verdier ender 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 liste datastruktur, som inneholder en, to eller tre kolliderte verdier. Følgende diagram er et eksempel på en hashtabell for separat kjetting av kunder og deres telefonnumre:
De tomme skuffene er merket med bokstaven x. Resten av sporene har pekere til koblede lister. Hvert element i den koblede listen har to datafelter: ett for kundenavnet og det andre for telefonnummeret. Det oppstår konflikt for nøklene: Peter Jones og Suzan Lee. De tilsvarende verdiene består av to elementer på en koblet liste.
For motstridende nøkler er kriteriet for å sette inn verdi det samme kriteriet som brukes til å lokalisere (og lese) verdien.
Åpne adressering
Med åpen adressering lagres alle verdiene i bøtteoppstillingen. Når konflikt oppstår, settes den nye verdien inn i en tom bøtte, den nye verdien for konflikten, etter noen kriterier. Kriteriet som brukes for å sette inn en verdi i 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 hasher indeksen, 152, og lagrer telefonnummeret sitt ved den tilhørende bøtta. Etter en stund hash-funksjonen hasher 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 hashes indeksen, 153 for nøkkelen, Robin Hood, men denne indeksen har allerede blitt brukt til å løse konflikten for en tidligere nøkkel. Verdien for Robin Hood plasseres altså i neste tomme bøtte, som er den for indeks 154.
Metoder for å løse konflikter for separat lenking 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 kjettingkonflikter
Metodene for separate kjetting hash-tabeller er kort forklart nå:
Separat lenking med sammenkoblede lister
Denne metoden er som forklart ovenfor. Imidlertid må hvert element i den koblede listen ikke nødvendigvis ha nøkkelfeltet (e.g. kundenavnfelt ovenfor).
Separat lenking med listehodeceller
I denne metoden lagres det første elementet i den koblede listen i en bøtte i matrisen. Dette er mulig, hvis datatypen for matrisen er elementet i den koblede listen.
Separat lenking 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 åpne adresseringskonflikter
En metode for å løse konflikter i åpen adressering kalles sondesekvens. Tre kjente sondesekvenser er kort forklart nå:
Lineær sondering
Med lineær sondering, når det oppstår en konflikt, blir det sett etter nærmeste tomme bøtte under bøtta ved konflikt. Også, med lineær sondering, lagres både nøkkelen og verdien i samme bøtte.
Kvadratisk sondering
Anta at konflikt oppstår ved indeks H. Neste tomme spor (bøtte) ved indeks H + 12 benyttes; hvis det allerede er opptatt, så er den neste tomme på H + 22 brukes, hvis den allerede er opptatt, så den neste tomme på H + 32 brukes, og så videre. Det er varianter av dette.
Dobbel hasj
Med dobbel hashing er det to hashfunksjoner. Den første beregner (hasher) indeksen. Hvis det oppstår en konflikt, bruker den andre den samme nøkkelen til å bestemme hvor langt ned verdien skal settes inn. Det er mer til dette - se senere.
Perfekt Hash-funksjon
En perfekt hash-funksjon er en hash-funksjon som ikke kan føre til kollisjon. Dette kan skje når settet med nøkler er relativt lite, og hver nøkkel tilordnes til et bestemt heltall i hash-tabellen.
I ASCII-tegnsett kan store bokstaver tilordnes til tilsvarende små bokstaver ved hjelp av en hash-funksjon. Bokstaver er representert i dataminnet 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, legg til 32 til 65; for å kartlegge fra B til b, legg til 32 til 66; for å kartlegge fra C til c, legg til 32 til 67; og så videre. Her er store bokstaver nøklene, og små bokstaver er verdiene. Hashtabellen for dette kan være en matrise hvis verdier er de tilknyttede indeksene. Husk at bøtter i matrisen kan være tomme. Så bøtter i matrisen fra 64 til 0 kan være tomme. Hashfunksjonen legger ganske enkelt 32 til store bokstaver for å få indeksen, og derav små bokstaver. En slik funksjon er en perfekt hash-funksjon.
Hashing fra heltall til heltallindekser
Det er forskjellige metoder for å haske heltall. En av dem kalles Modulo Division Method (Function).
Modulo-divisjonens hasjfunksjon
En funksjon i dataprogramvare er ikke en matematisk funksjon. I databehandling (programvare) består en funksjon av et sett med utsagn foran argumenter. For Modulo-divisjonsfunksjonen er tastene heltall og blir kartlagt til indekser i spekteret. Tastesettet er stort, så bare nøkler som sannsynligvis vil forekomme 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 deleren, og 3 resten 2 er kvotienten. Resten 2 kalles også modulo. Merk: det er mulig å ha en modulo på 0.
For denne hashingen er bordstørrelsen vanligvis en styrke på 2, f.eks.g. 64 = 26 eller 256 = 28, etc. Deleren for denne hashing-funksjonen er et primtall nær matrisestørrelsen. Denne funksjonen deler nøkkelen med deleren og returnerer modulo. Modulen er indeksen til matrisen med skuffer. Den tilhørende verdien i bøtta er en verdi du velger (verdi for nøkkelen).
Hashing variabel lengde nøkler
Her er tastene til nøkkelsettet tekster av ulik lengde. Ulike heltall kan lagres i minnet ved hjelp av samme antall byte (størrelsen på et engelsk tegn er en byte). Når forskjellige taster har forskjellige bytestørrelser, sies det at de har variabel lengde. En av metodene for hasking av variable lengder kalles Radix Conversion Hashing.
Radix Conversion Hashing
I en streng er hvert tegn på datamaskinen et tall. I denne metoden,
Hash-kode (indeks) = x0enk − 1+x1enk − 2+… + Xk − 2en1+xk − 1en0
Hvor (x0, x1,…, xk − 1) er tegnene i inngangsstrengen og a er en radix, 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 en 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 annen tekst eller nummer eller post.
Associative Array
En liste er en datastruktur, der listeelementene er relatert, og det er et sett med operasjoner som fungerer på listen. Hvert listeelement kan bestå av et par elementer. Den generelle hashtabellen med nøklene kan betraktes som en datastruktur, men det er mer et system enn en datastruktur. Tastene og tilhørende verdier er ikke veldig avhengige av hverandre. De er ikke veldig beslektet med hverandre.
På den annen side er en assosiativ matrise en lignende ting, men nøkler og deres verdier er veldig avhengige av hverandre; de er veldig i slekt med hverandre. For eksempel kan du ha et assosiativt utvalg av frukt og deres farger. Hver frukt har naturlig sin farge. Fruktens navn er nøkkelen; fargen er verdien. Under innsetting settes hver nøkkel inn med verdien. Når du sletter, slettes hver nøkkel med verdien.
En assosiativ matrise er en hash-tabell datastruktur sammensatt av nøkkel / verdipar, der det ikke er noe duplikat for nøklene. Verdiene kan ha duplikater. I denne situasjonen er nøklene en del av strukturen. Det vil si at tastene må lagres, mens tastene ikke må lagres med den generelle tabellen. Problemet med de dupliserte verdiene løses naturlig ved indeksene til spekteret. Ikke forveksle mellom dupliserte verdier og kollisjon i en indeks.
Siden en assosiativ matrise er en datastruktur, har den minst følgende operasjoner:
Associative Array Operations
sett inn eller legg til
Dette setter inn et nytt nøkkel / verdipar i samlingen, og tilordner nøkkelen til verdien.
omfordele
Denne operasjonen erstatter verdien av en bestemt nøkkel til en ny verdi.
slette eller fjerne
Dette fjerner en nøkkel pluss dens tilsvarende verdi.
se opp
Denne operasjonen søker etter verdien på en bestemt nøkkel og returnerer verdien (uten å fjerne den).
Konklusjon
En datastruktur for hash-tabellen består av en matrise og en funksjon. Funksjonen kalles en hash-funksjon. Funksjonen tilordner nøkler til verdier i matrisen gjennom indeksene til matrisen. Nøklene må ikke nødvendigvis være en del av datastrukturen. Nøkkelsettet er vanligvis større enn de lagrede verdiene. Når det oppstår en kollisjon, løses den enten ved den separate kjedemetoden eller den åpne adresseringsmetoden. En assosiativ matrise er et spesielt tilfelle av datastrukturen for hash-tabellen.
