Un tabel hash, cunoscut și sub numele de hartă hash, este o structură de date care mapează cheile la valori. Este o parte a unei tehnici numite hash, cealaltă dintre care este o funcție hash. O funcție hash este un algoritm care produce un indice de unde o valoare poate fi găsită sau stocată în tabelul hash.

Câteva note importante despre tabelele hash:

  1. Valorile nu sunt stocate într-o ordine sortată.
  2. Ai nevoie de potențiale coliziuni. Acest lucru se face de obicei cu o tehnică numită înlănțuire. Înlănțuirea înseamnă a crea o listă legată de valori, ale căror taste se mapează la un anumit index.

Conţinut

Implementarea unui tabel hash

Ideea de bază din spatele hashului este distribuirea perechilor cheie / valoare într-o serie de substituenți sau „găleți” în tabelul hash.

Un tabel hash este de obicei o serie de liste legate. Când doriți să inserați o pereche cheie / valoare, trebuie mai întâi să utilizați funcția hash pentru a mapa cheia la un index din tabelul hash. Având în vedere o cheie, funcția hash poate sugera un index unde valoarea poate fi găsită sau stocată:

index = f(key, array_size)

Acest lucru se face adesea în doi pași:

ad-banner
hash = hashfunc(key)
index = hash % array_size

Folosind această metodă, hash este independent de dimensiunea tabelului hash. hash este redus la un index – un număr între 0, începutul matricei și array_size - 1, sfârșitul matricei – folosind operatorul modulo (%).

Luați în considerare următorul șir, S:

string S = “ababcd”

Trebuie să numărați frecvența tuturor caracterelor din S. Cel mai simplu mod de a face acest lucru este să iterați prin toate caracterele posibile și să numărați frecvența fiecăruia, unul câte unul.

Acest lucru funcționează, dar este lent – complexitatea timpului unei astfel de abordări este O (26 * N), cu N fiind de mărimea șirului S înmulțit cu 26 de caractere posibile din 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;
        }
    }

Ieșire:

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

Să aruncăm o privire la o soluție care utilizează hashing.

Luați o matrice și utilizați funcția hash pentru a hashiza cele 26 de caractere posibile cu indicii matricei. Apoi iterați S și creșteți valoarea caracterului curent al șirului cu indicele corespunzător pentru fiecare caracter.

Complexitatea acestei abordări hash este O (N), unde N este dimensiunea șirului.

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;
    }

Ieșire

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

Hash Collisions

Deoarece harta dvs. hash va fi probabil mult mai mică decât cantitatea de date pe care o prelucrați, coliziunile hash sunt inevitabile. Există două abordări principale pentru gestionarea coliziunilor: înlănțuire și adresare deschisă.

Înlănțuirea

După cum sa menționat mai devreme, înlănțuirea înseamnă că fiecare pereche cheie / valoare din tabelul hash, valoarea este o listă legată de date mai degrabă decât o singură celulă.

De exemplu, imaginați-vă că cheia 152 deține valoarea „John Smith”. Dacă valoarea „Sandra Dee” este adăugată la aceeași cheie, „Sandra Dee” se adaugă ca un alt element la cheia 152, imediat după „John Smith”.

152: [["John Smith", "p01"]]

...

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

Principalul dezavantaj al înlănțuirii este creșterea complexității timpului. În loc de 0 (1) ca în cazul unui tabel hash obișnuit, fiecare căutare va dura mai mult timp, deoarece trebuie să parcurgem fiecare listă legată pentru a găsi valoarea corectă.

Adresare deschisă

Adresarea deschisă înseamnă că, odată ce o valoare este mapată la o cheie deja ocupată, vă deplasați de-a lungul tastelor tabelului hash până când găsiți una goală. De exemplu, dacă „John Smith” a fost mapat la 152, „Sandra Dee” va fi mapat la următorul index deschis:

152: ["John Smith", "p01"] 

...

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

Principalul dezavantaj al adresării deschise este că, atunci când căutați valori, este posibil să nu fie la harta cheie la care vă așteptați. În schimb, trebuie să parcurgeți diferite părți ale tabelului hash pentru a găsi valoarea pe care o căutați.