Hva er Hashing? Hvordan Hash-koder fungerer - med eksempler

Introduksjon til hashing

Hashing er designet for å løse problemet med å trenge å effektivt finne eller lagre et element i en samling.

For eksempel, hvis vi har en liste med 10 000 ord på engelsk og vi vil sjekke om et gitt ord er i listen, ville det være ineffektivt å sammenlikne ordet suksessivt med alle 10 000 elementene til vi finner en kamp. Selv om ordlisten er sortert leksikografisk, som i en ordbok, trenger du fortsatt litt tid på å finne ordet du leter etter.

Hashing er en teknikk for å gjøre ting mer effektive ved effektivt å begrense søket i begynnelsen.

Hva er hashing?

Hashing betyr å bruke en eller annen funksjon eller algoritme for å kartlegge objektdata til en representativ heltallverdi.

Denne såkalte hash-koden (eller bare hash) kan da brukes som en måte å begrense søket når vi leter etter varen på kartet.

Vanligvis brukes disse hashkodene til å generere en indeks der verdien lagres.

Hvordan hashing fungerer

I hashtabeller lagrer du data i former for nøkkel- og verdipar. Nøkkelen, som brukes til å identifisere dataene, blir gitt som en inngang til hashing-funksjonen. Hashkoden, som er et heltall, blir deretter kartlagt til den faste størrelsen vi har.

Hash-tabeller må støtte 3 funksjoner.

  • sett inn (nøkkel, verdi)
  • få (nøkkel)
  • slett (nøkkel)

Rent som et eksempel for å hjelpe oss med å forstå konseptet, la oss anta at vi vil kartlegge en liste med strengnøkler til strengverdier (for eksempel kartlegge en liste over land til hovedstaden).

Så la oss si at vi vil lagre dataene i Tabell på kartet.

Og la oss anta at vår hash-funksjon er å bare ta lengden på strengen.

For enkelhets skyld vil vi ha to matriser: en for nøklene og en for verdiene.

Så for å plassere et element i hash-tabellen, beregner vi hash-koden (i dette tilfellet teller du bare antall tegn), og legger deretter nøkkelen og verdien i matriser ved tilsvarende indeks.

For eksempel har Cuba en hash-kode (lengde) på 4. Så vi lagrer Cuba i 4. posisjon i nøkkeloppstillingen, og Havana i den fjerde indeksen av verdiordningen osv. Og vi ender med følgende:

Nå, i dette spesifikke eksemplet, fungerer ting ganske bra. Utvalget vårt må være stort nok til å imøtekomme den lengste strengen, men i dette tilfellet er det bare 11 spor.

Vi kaster bort litt plass fordi det for eksempel ikke er 1-bokstavsnøkler i dataene våre, og heller ikke nøkler mellom 8 og 10 bokstaver.

Men i dette tilfellet er heller ikke den bortkastede plassen så ille. Å ta lengden på en streng er fin og rask, og det er også prosessen med å finne verdien som er knyttet til en gitt nøkkel (absolutt raskere enn å gjøre opptil fem strengesammenligninger).

Men hva gjør vi hvis datasettet vårt har en streng som inneholder mer enn 11 tegn?

Hva om vi har hverandre ord med fem tegn, “India”, og prøver å tilordne det til en indeks ved hjelp av hash-funksjonen vår. Siden indeks 5 allerede er opptatt, må vi ringe hva vi skal gjøre med den. Dette kalles en kollisjon.

Hvis datasettet vårt hadde en streng med tusen tegn, og du lager en rekke tusen indekser for å lagre dataene, ville det føre til sløsing med plass. Hvis nøklene våre var tilfeldige ord fra engelsk, der det er så mange ord med samme lengde, ville bruk av lengde som en hashing-funksjon være ganske ubrukelig.

Kollisjonshåndtering

To grunnleggende metoder brukes til å håndtere kollisjoner.

  1. Separat lenking
  2. Åpne adressering

Separat lenking

Håndtering av hasjkollisjon ved separat kjetting, bruker en ekstra datastruktur, helst koblet liste for dynamisk tildeling, i bøtter. I vårt eksempel, når vi legger til India i datasettet, legges det til den koblede listen som er lagret i indeks 5, så vil tabellen vår se slik ut.

For å finne et element går vi først til bøtta og sammenligner deretter nøklene. Dette er en populær metode, og hvis du bruker en liste over lenker, fylles hasjen aldri opp. Kostnaden for get(k)er i gjennomsnitt O(n)hvor n er antall nøkler i bøtta, totalt antall nøkler er N.

Problemet med separat kjetting er at datastrukturen kan vokse uten grenser.

Åpne adressering

Åpen adressering introduserer ingen ny datastruktur. Hvis det oppstår en kollisjon, ser vi etter tilgjengelighet på neste sted generert av en algoritme. Åpen adressering brukes vanligvis der lagringsplass er begrenset, dvs. innebygde prosessorer. Åpen adressering ikke nødvendigvis raskere enn separat kjetting.

Metoder for åpen adressering

  • [Lineær sondering
  • Kvadratisk sondering
  • Dobbel hasj

Hvordan bruke hashing i koden din.

Python

 # Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
:rakett:

Kjør kode

Java

 // Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();
:rakett:

Kjør kode

Mer info om hashing

  • Den kodeløse guiden til hasj- og hasjbord
  • Hvordan implementere en enkel hash-tabell i JavaScript
  • Hash-tabeller forklart