Hvad er Hashing? Sådan fungerer Hash-koder - med eksempler

Introduktion til hashing

Hashing er designet til at løse problemet med behovet for effektivt at finde eller gemme en genstand i en samling.

For eksempel, hvis vi har en liste på 10.000 ord på engelsk, og vi vil kontrollere, om et givet ord er på listen, ville det være ineffektivt at successivt sammenligne ordet med alle 10.000 emner, indtil vi finder et match. Selvom ordlisten er ordbestemt sorteret, som i en ordbog, har du stadig brug for lidt tid til at finde det ord, du leder efter.

Hashing er en teknik til at gøre tingene mere effektive ved effektivt at indsnævre søgningen fra starten.

Hvad er hashing?

Hashing betyder at bruge en eller anden funktion eller algoritme til at kortlægge objektdata til en eller anden repræsentativ helhedsværdi.

Denne såkaldte hash-kode (eller simpelthen hash) kan derefter bruges som en måde at indsnævre vores søgning på, når vi leder efter varen på kortet.

Generelt bruges disse hashkoder til at generere et indeks, hvor værdien er gemt.

Hvordan hashing fungerer

I hash-tabeller gemmer du data i form af nøgle- og værdipar. Nøglen, som bruges til at identificere dataene, gives som input til hashing-funktionen. Hashkoden, som er et heltal, kortlægges derefter til den faste størrelse, vi har.

Hash-tabeller skal understøtte 3 funktioner.

  • indsæt (nøgle, værdi)
  • få (nøgle)
  • slet (nøgle)

Rent som et eksempel for at hjælpe os med at forstå konceptet, lad os antage, at vi vil kortlægge en liste med strengnøgler til strengværdier (for eksempel kortlægge en liste over lande til deres hovedstæder).

Så lad os sige, at vi vil gemme dataene i tabel på kortet.

Og lad os antage, at vores hash-funktion er simpelthen at tage længden på strengen.

For enkelheds skyld har vi to arrays: en til vores nøgler og en til værdierne.

Så for at placere et element i hash-tabellen beregner vi dets hash-kode (i dette tilfælde tæller du blot antallet af tegn) og sætter derefter nøglen og værdien i arrays ved det tilsvarende indeks.

For eksempel har Cuba en hash-kode (længde) på 4. Så vi gemmer Cuba i 4. position i nøgler array, og Havana i 4. indeks for værdier array osv. Og vi ender med følgende:

I dette specifikke eksempel fungerer tingene ganske godt. Vores array skal være stort nok til at rumme den længste streng, men i dette tilfælde er det kun 11 slots.

Vi spilder lidt plads, fordi der for eksempel ikke er nøgler på 1 bogstav i vores data eller nøgler mellem 8 og 10 bogstaver.

Men i dette tilfælde er den spildte plads heller ikke så dårlig. At tage længden af ​​en streng er pæn og hurtig, og det er også processen med at finde den værdi, der er knyttet til en given nøgle (bestemt hurtigere end at lave op til fem strengesammenligninger).

Men hvad gør vi, hvis vores datasæt har en streng, der indeholder mere end 11 tegn?

Hvad hvis vi har hinanden ord med 5 tegn, "Indien", og prøver at tildele det til et indeks ved hjælp af vores hash-funktion. Da indeks 5 allerede er optaget, skal vi ringe til, hvad vi skal gøre med det. Dette kaldes en kollision.

Hvis vores datasæt havde en streng med tusind tegn, og du laver en række tusind indeks for at gemme dataene, ville det resultere i spild af plads. Hvis vores nøgler var tilfældige ord fra engelsk, hvor der er så mange ord med samme længde, ville det være temmelig ubrugeligt at bruge længde som en hashing-funktion.

Kollisionshåndtering

To grundlæggende metoder bruges til at håndtere kollisioner.

  1. Separat lænkning
  2. Åbn adressering

Separat lænkning

Håndtering af hash-kollision ved separat kæde, bruger en ekstra datastruktur, fortrinsvis linket liste til dynamisk tildeling, i spande. I vores eksempel, når vi tilføjer Indien til datasættet, føjes det til den linkede liste, der er gemt i indeks 5, så ser vores tabel sådan ud.

For at finde et element går vi først til skovlen og sammenligner derefter nøglerne. Dette er en populær metode, og hvis der bruges en liste over links, fyldes hash aldrig op. Prisen for get(k)er i gennemsnit O(n)hvor n er antallet af nøgler i skovlen, det samlede antal nøgler er N.

Problemet med separat kæde er, at datastrukturen kan vokse uden grænser.

Åbn adressering

Åben adressering indfører ikke nogen ny datastruktur. Hvis der opstår en kollision, ser vi efter tilgængelighed på det næste sted genereret af en algoritme. Åben adressering bruges generelt, hvor lagerplads er begrænset, dvs. indlejrede processorer. Åben adressering ikke nødvendigvis hurtigere end separat kæde.

Metoder til åben adressering

  • [Lineær sondering
  • Kvadratisk sondering
  • Dobbelt hash

Sådan bruges hashing i din kode.

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()
:raket:

Kø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();
:raket:

Kør kode

Mere info om hashing

  • Den kodeløse guide til hashing og hash-tabeller
  • Sådan implementeres en simpel hash-tabel i JavaScript
  • Hash-tabeller forklaret