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

O tabelă hash este o structură de date care mapează chei unice la valori asociate. Cheile sunt folosite pentru a căuta rapid valorile în tabela hash, oferind acces eficient la date. În acest articol, vom explora cum să implementăm o tabelă hash eșantion în limbajele de programare C/C++.

Ce este o tabelă hash?

O tabelă hash este un array de cupe. Fiecare cupă conține o listă de perechi cheie-valoare. Când adăugăm o nouă pereche cheie-valoare la tabela hash, calculăm indexul cupei folosind o funcție hash. Apoi, adăugăm perechea cheie-valoare la lista din cupă.

Când căutăm o valoare folosind o cheie, calculăm din nou indexul cupei și căutăm perechea cheie-valoare în lista din cupă. Dacă perechea cheie-valoare este găsită, returnăm valoarea asociată.

De ce să folosim o tabelă hash?

Tabelele hash sunt folosite pentru a îmbunătăți timpul de căutare și inserare în structurile de date. Iată câteva avantaje ale utilizării tabelelor hash:

* Căutare rapidă: Tabelele hash oferă un timp de căutare constant, O(1), în medie.
* Inserare rapidă: Inserarea unei noi perechi cheie-valoare într-o tabelă hash durează, de asemenea, O(1) timp în medie.
* Acces eficient: Tabelele hash permit accesul eficient la valori asociate cu chei specifice.

Implementarea unei tabele hash în C/C++

Structura cupei

Vom folosi o structură de date simplă numită cupă pentru a stoca perechile cheie-valoare. O structură de cupă conține un pointer către o pereche cheie-valoare și un pointer către următoarea cupă.

c++
struct Cupă {
PerecheCheieValoare *perecheCheieValoare;
Cupă *următoareaCupă;
};


Funcția hash

Funcția hash joacă un rol crucial în determinarea indexului cupei pentru o anumită cheie. În general, funcțiile hash convertesc o cheie într-un întreg, care este apoi folosit ca index al cupei. Există diferite funcții hash disponibile, iar alegerea celei mai bune funcții hash depinde de aplicația specifică.

Funcția de căutare

Funcția de căutare caută o valoare asociată cu o cheie dată într-o tabelă hash. Iată pașii implicați în căutarea unei valori:

1. Calculăm indexul cupei folosind funcția hash.
2. Iterăm prin lista din cupă și căutăm perechea cheie-valoare cu cheia dată.
3. Dacă perechea cheie-valoare este găsită, returnăm valoarea asociată.
4. Dacă perechea cheie-valoare nu este găsită, returnăm NULL.

Funcția de inserare

Funcția de inserare adaugă o nouă pereche cheie-valoare într-o tabelă hash. Iată pașii implicați în inserarea unei perechi cheie-valoare:

1. Calculăm indexul cupei folosind funcția hash.
2. Alocăm o nouă pereche cheie-valoare și o inițializăm cu cheia și valoarea date.
3. Adăugăm noua pereche cheie-valoare la începutul listei din cupă.

Un exemplu de implementare a tabelei hash

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

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

// Structura cupei
struct Cupă {
PerecheCheieValoare *perecheCheieValoare;
Cupă *următoareaCupă;
};

// Structura tabelei hash
struct TabelăHash {
int dimensiune;
Cupă **cupe;
};

// Crearea unei tabele hash
TabelăHash *creaTabelăHash(int dimensiune) {
TabelăHash tabelăHash = (TabelăHash )malloc(sizeof(TabelăHash));
tabelăHash->dimensiune = dimensiune;
tabelăHash->cupe = (Cupă *)malloc(dimensiune * sizeof(Cupă ));

for (int i = 0; i < dimensiune; i++) {
tabelăHash->cupe[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);
Cupă *cupă = tabelăHash->cupe[index];

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

cupă = cupă->următoareaCupă;
}

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);
Cupă cupă = (Cupă )malloc(sizeof(Cupă));
cupă->perecheCheieValoare = (PerecheCheieValoare *)malloc(sizeof(PerecheCheieValoare));
cupă->perecheCheieValoare->cheie = (char *)malloc(strlen(cheie) + 1);
strcpy(cupă->perecheCheieValoare->cheie, cheie);
cupă->perecheCheieValoare->valoare = valoare;
cupă->următoareaCupă = tabelăHash->cupe[index];
tabelăHash->cupe[index] = cupă;
}

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

while (cupă) {
if (strcmp(cupă->perecheCheieValoare->cheie, cheie) == 0) {
if (cupăPrecedentă) {
cupăPrecedentă->următoareaCupă = cupă->următoareaCupă;
} else {
tabelăHash->cupe[index] = cupă->următoareaCupă;
}

free(cupă->perecheCheieValoare->cheie);
free(cupă->perecheCheieValoare);
free(cupă);

return;
}

cupăPrecedentă = cupă;
cupă = cupă->următoareaCupă;
}
}

// Eliberarea unei tabele hash
void eliberează(TabelăHash *tabelăHash) {
for (int i = 0; i < tabelăHash->dimensiune; i++) {
Cupă *cupă = tabelăHash->cupe[i];

while (cupă) {
Cupă *următoareaCupă = cupă->următoareaCupă;
free(cupă->perecheCheieValoare->cheie);
free(cupă->perecheCheieValoare);
free(cupă);
cupă = următoareaCupă;
}
}

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


Concluzie

Tabelele hash sunt structuri de date versatile și eficiente care pot fi utilizate într-o gamă largă de aplicații. Implementarea unei tabele hash în C/C++ este relativ simplă și oferă acces rapid și eficient la date. În acest articol, am explorat conceptele și implementarea tabelelor hash în C/C++. Înțelegerea acestor concepte vă va permite să utilizați