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:
- Værdier gemmes ikke i en sorteret rækkefølge.
- 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 hash
er uafhængig af størrelsen på hash-tabellen. hash
reduceres til et indeks - et tal mellem 0, starten af arrayet og array_size - 1
slutningen 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), N
idet den er strengens størrelse S
ganget 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 S
og ø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.