Hash-tabel forklaret: Hvad det er, og hvordan man implementerer det

En hash-tabel, også kendt som et hash-kort, er en datastruktur, der kortlægger nøgler til værdier. Det er en del af en teknik kaldet hashing, hvoraf den anden er en hash-funktion. En hash-funktion er en algoritme, der producerer et indeks over, hvor en værdi kan findes eller gemmes i hash-tabellen.

Nogle vigtige noter om hash-tabeller:

1. Værdier gemmes ikke i en sorteret rækkefølge.
2. Du skal redegøre for potentielle kollisioner. Dette gøres normalt med en teknik kaldet chaining. Kædning betyder at oprette en sammenkædet liste over værdier, hvis nøgler knyttes til et bestemt indeks.

Implementering af en hash-tabel

Den grundlæggende idé bag hashing er at distribuere nøgle / værdipar på tværs af en række pladsholdere eller "spande" i hash-tabellen.

En hash-tabel er typisk en række sammenkædede lister. Når du vil indsætte et nøgle / værdipar, skal du først bruge hash-funktionen til at kortlægge nøglen til et indeks i hash-tabellen. Med en nøgle kan hash-funktionen foreslå et indeks, hvor værdien kan findes eller gemmes:

index = f(key, array_size)

Dette gøres ofte i to trin:

hash = hashfunc(key) index = hash % array_size

Brug af denne metode hasher uafhængig af størrelsen på hash-tabellen. hashreduceres til et indeks - et tal mellem 0, starten af ​​arrayet og array_size - 1slutningen af ​​arrayet - ved hjælp af operatoren modulo (%).

Overvej følgende streng S:

string S = “ababcd”

Du skal tælle hyppigheden af ​​alle tegnene i S. Den nemmeste måde at gøre dette på er at gentage alle de mulige tegn og tælle hyppigheden af ​​hver, en efter en.

Dette fungerer, men det er langsomt - tidskompleksiteten af ​​en sådan tilgang er O (26 * N), Nidet den er strengens størrelse Sganget med 26 mulige tegn fra AZ.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Produktion:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Lad os se på en løsning, der bruger hashing.

Tag et array og brug hash-funktionen til at hash de 26 mulige tegn med indeks i arrayet. Derefter gentages Sog øges værdien af ​​den aktuelle karakter af strengen med det tilsvarende indeks for hvert tegn.

Kompleksiteten af ​​denne hashing-tilgang er O (N), hvor N er størrelsen på strengen.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Produktion

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Hash-kollisioner

Da dit hash-kort sandsynligvis vil være betydeligt mindre end mængden af ​​data, du behandler, er hash-kollisioner uundgåelige. Der er to hovedmetoder til håndtering af kollisioner: kæde og åben adressering .

Lænkning

Som tidligere nævnt betyder sammenkædning, at hvert nøgle / værdipar i hash-tabellen, værdien er en sammenkædet liste over data snarere end en enkelt celle.

Forestil dig f.eks., At nøglen 152 indeholder værdien "John Smith". Hvis værdien "Sandra Dee" føjes til den samme nøgle, tilføjes "Sandra Dee" som et andet element til tast 152 lige efter "John Smith".

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

Den største ulempe ved kæde er stigningen i tidskompleksitet. I stedet for 0 (1) som med en almindelig hash-tabel, tager hver opslag mere tid, da vi er nødt til at krydse hver sammenkædede liste for at finde den korrekte værdi.

Åben adressering

Åben adressering betyder, at når en værdi er kortlagt til en nøgle, der allerede er optaget, bevæger du dig langs tasterne på hash-tabellen, indtil du finder en, der er tom. For eksempel, hvis "John Smith" blev kortlagt til 152, vil "Sandra Dee" blive kortlagt til det næste åbne indeks:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

Den største ulempe ved åben adressering er, at når du ser på værdier, er de muligvis ikke på det nøglekort, du forventer dem på. I stedet skal du krydse forskellige dele af hash-tabellen for at finde den værdi, du leder efter.