Cum să implementați o tabelă hash eșantion în C/C++

O tabelă hash reprezintă o structură de date esențială, care asociază chei unice cu valori specifice. Aceste chei sunt folosite pentru a facilita căutarea rapidă a valorilor în cadrul tabelei, optimizând astfel accesul la date. În acest articol, vom detalia procesul de implementare a unei tabele hash simple folosind limbajele de programare C și C++.

Ce Reprezintă o Tabelă Hash?

O tabelă hash este, în esență, un tablou de compartimente (numite și „cupe”). Fiecare compartiment poate conține o listă de perechi cheie-valoare. Atunci când adăugăm o nouă pereche, se calculează un index pentru compartiment folosind o funcție hash. Apoi, perechea este inserată în lista specifică acelui compartiment.

În timpul căutării unei valori, procesul este similar: se calculează indexul compartimentului folosind cheia, iar apoi se caută perechea cheie-valoare în lista compartimentului respectiv. Dacă se găsește, valoarea asociată este returnată.

De Ce să Utilizăm Tabele Hash?

Tabelele hash sunt preferate pentru avantajele pe care le oferă în gestionarea datelor. Iată câteva dintre cele mai importante:

• Căutare Rapidă: În medie, tabelele hash oferă o complexitate de timp O(1) pentru operațiunea de căutare, ceea ce înseamnă că timpul de căutare este aproape constant, indiferent de numărul de elemente stocate.
• Inserare Rapidă: Similar cu căutarea, inserarea unei noi perechi cheie-valoare durează, de asemenea, în medie, O(1) timp.
• Acces Eficient: Tabelele hash permit accesul direct și rapid la valorile asociate cheilor, îmbunătățind performanța generală a aplicațiilor.

Cum Implementăm o Tabelă Hash în C/C++?

Structura unui Compartiment

Pentru a stoca perechile cheie-valoare, vom folosi o structură simplă numită Compartiment. Această structură conține un pointer către o pereche cheie-valoare și un alt pointer către următorul compartiment din listă.

C++
struct Compartiment {
PerecheCheieValoare *perecheCheieValoare;
Compartiment *urmatorulCompartiment;
};


Rolul Funcției Hash

Funcția hash este crucială pentru determinarea indexului compartimentului corespunzător unei anumite chei. Aceasta transformă cheia într-un număr întreg, care este apoi folosit ca index. Alegerea funcției hash potrivite depinde de particularitățile aplicației.

Funcția de Căutare

Funcția de căutare identifică o valoare asociată unei chei specifice. Pașii implicați sunt:

1. Calcularea indexului compartimentului folosind funcția hash.
2. Parcurgerea listei din compartiment și căutarea perechii cheie-valoare potrivite.
3. Returnarea valorii asociate dacă perechea este găsită.
4. Returnarea NULL dacă perechea nu este găsită.

Funcția de Inserare

Funcția de inserare adaugă o nouă pereche cheie-valoare în tabelă. Pașii sunt:

1. Calcularea indexului compartimentului utilizând funcția hash.
2. Alocarea memoriei pentru o nouă pereche cheie-valoare și inițializarea acesteia cu cheia și valoarea primite.
3. Adăugarea noii perechi la începutul listei din compartiment.

Exemplu de Implementare

Iată un exemplu de implementare a tabelei hash în C/C++:

C++
#include <stdlib.h>
#include <string.h>

// Structura unui compartiment
struct Compartiment {
PerecheCheieValoare *perecheCheieValoare;
Compartiment *urmatorulCompartiment;
};

// Structura tabelei hash
struct TabelăHash {
int dimensiune;
Compartiment **compartimente;
};

// Crearea unei tabele hash
TabelăHash *creeazăTabelăHash(int dimensiune) {
TabelăHash *tabelăHash = (TabelăHash *)malloc(sizeof(TabelăHash));
tabelăHash->dimensiune = dimensiune;
tabelăHash->compartimente = (Compartiment **)malloc(dimensiune * sizeof(Compartiment *));

for (int i = 0; i < dimensiune; i++) {
tabelăHash->compartimente[i] = NULL;
}

return tabelăHash;
}

// Funcția hash
int funcțieHash(char *cheie) {
int index = 0;

for (int i = 0; cheie[i] != '\0'; i++) {
index += (int)cheie[i];
}

return index % dimensiune;
}

// Căutarea unei valori într-o tabelă hash
void *caută(TabelăHash *tabelăHash, char *cheie) {
int index = funcțieHash(cheie);
Compartiment *compartiment = tabelăHash->compartimente[index];

while (compartiment) {
if (strcmp(compartiment->perecheCheieValoare->cheie, cheie) == 0) {
return compartiment->perecheCheieValoare->valoare;
}

compartiment = compartiment->urmatorulCompartiment;
}

return NULL;
}

// Inserarea unei perechi cheie-valoare într-o tabelă hash
void inserează(TabelăHash *tabelăHash, char *cheie, void *valoare) {
int index = funcțieHash(cheie);
Compartiment *compartiment = (Compartiment *)malloc(sizeof(Compartiment));
compartiment->perecheCheieValoare = (PerecheCheieValoare *)malloc(sizeof(PerecheCheieValoare));
compartiment->perecheCheieValoare->cheie = (char *)malloc(strlen(cheie) + 1);
strcpy(compartiment->perecheCheieValoare->cheie, cheie);
compartiment->perecheCheieValoare->valoare = valoare;
compartiment->urmatorulCompartiment = tabelăHash->compartimente[index];
tabelăHash->compartimente[index] = compartiment;
}

// Ștergerea unei perechi cheie-valoare dintr-o tabelă hash
void șterge(TabelăHash *tabelăHash, char *cheie) {
int index = funcțieHash(cheie);
Compartiment *compartiment = tabelăHash->compartimente[index];
Compartiment *compartimentAnterior = NULL;

while (compartiment) {
if (strcmp(compartiment->perecheCheieValoare->cheie, cheie) == 0) {
if (compartimentAnterior) {
compartimentAnterior->urmatorulCompartiment = compartiment->urmatorulCompartiment;
} else {
tabelăHash->compartimente[index] = compartiment->urmatorulCompartiment;
}

free(compartiment->perecheCheieValoare->cheie);
free(compartiment->perecheCheieValoare);
free(compartiment);
return;
}

compartimentAnterior = compartiment;
compartiment = compartiment->urmatorulCompartiment;
}
}

// Eliberarea memoriei ocupate de o tabelă hash
void eliberează(TabelăHash *tabelăHash) {
for (int i = 0; i < tabelăHash->dimensiune; i++) {
Compartiment *compartiment = tabelăHash->compartimente[i];

while (compartiment) {
Compartiment *urmatorulCompartiment = compartiment->urmatorulCompartiment;
free(compartiment->perecheCheieValoare->cheie);
free(compartiment->perecheCheieValoare);
free(compartiment);
compartiment = urmatorulCompartiment;
}
}

free(tabelăHash->compartimente);
free(tabelăHash);
}


Concluzii

Tabelele hash sunt instrumente extrem de eficiente și versatile pentru gestionarea datelor în diverse aplicații. Implementarea unei tabele hash în C/C++ este accesibilă, oferind acces rapid și performant la date. Acest articol a oferit o prezentare detaliată a conceptelor și a modului de implementare a tabelelor hash, permițându-vă să le utilizați cu încredere în proiectele voastre.