Uvod u heš tabele
Heš tabele su temeljne strukture podataka koje omogućavaju izuzetno brzo pronalaženje i pristup podacima na osnovu njihovih ključeva. Zbog svoje efikasnosti pri operacijama kao što su umetanje, pretraga i brisanje, heš tabele su nezamenljive u raznim aplikacijama, uključujući sisteme baza podataka, keš memorije i tabele prevođenja.
U ovom članku ćemo detaljno razmotriti kako implementirati jednostavnu heš tabelu u C/C++, koristeći lančano heširanje kao metodu za rešavanje kolizija.
Struktura i implementacija heš tabele
Osnovna struktura heš tabele
Heš tabela se sastoji od niza „slotova“, gde svaki slot služi kao prostor za smeštanje elemenata koji dele isti heš kod. Heš kod je numerička vrednost izvedena iz ključa elementa pomoću heš funkcije.
U našoj implementaciji, svaki slot koristi dvostruko povezanu listu, što omogućava efikasno dodavanje, pretraživanje i brisanje elemenata.
struct HashNode {
int key;
int value;
struct HashNode* next;
struct HashNode* prev;
};
struct HashTable {
int TABLE_SIZE;
struct HashNode** table;
};
Heš funkcija
Heš funkcija je ključni deo svake heš tabele. Ona preslikava ulazni ključ na heš kod. Dobro dizajnirana heš funkcija ravnomerno raspoređuje ključeve po slotovima, što smanjuje mogućnost kolizija. U našem primeru koristimo jednostavnu modulo operaciju:
int hashFunction(int key, int TABLE_SIZE) {
return key % TABLE_SIZE;
}
Umetanje elementa u tabelu
Da bismo ubacili element u heš tabelu, prvo izračunavamo heš kod ključa i pronalazimo odgovarajući slot. Zatim proveravamo da li je slot prazan. Ako jeste, novi element se dodaje na kraj liste. Ako slot već sadrži elemente, novi element se dodaje na početak liste:
void insert(struct HashTable* ht, int key, int value) {
int index = hashFunction(key, ht->TABLE_SIZE);
struct HashNode* temp = new HashNode;
temp->key = key;
temp->value = value;
temp->next = ht->table[index];
if (ht->table[index] != NULL) {
ht->table[index]->prev = temp;
}
ht->table[index] = temp;
}
Pretraga elementa u tabeli
Za pretragu elementa, prvo se izračunava heš kod ključa i dobija odgovarajući slot. Zatim se prolazi kroz povezanu listu u okviru tog slota, upoređujući ključeve dok se ne pronađe traženi element:
int search(struct HashTable* ht, int key) {
int index = hashFunction(key, ht->TABLE_SIZE);
struct HashNode* temp = ht->table[index];
while (temp != NULL) {
if (temp->key == key) {
return temp->value;
}
temp = temp->next;
}
return -1;
}
Brisanje elementa iz tabele
Za brisanje elementa iz heš tabele, ponovo se izračunava heš kod ključa i pronalazi odgovarajući slot. Zatim se prolazi kroz listu unutar slota i briše se element ukoliko se pronađe podudaranje ključa:
void remove(struct HashTable* ht, int key) {
int index = hashFunction(key, ht->TABLE_SIZE);
struct HashNode* temp = ht->table[index];
while (temp != NULL) {
if (temp->key == key) {
if (temp == ht->table[index]) {
ht->table[index] = temp->next;
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
if (temp->prev != NULL) {
temp->prev->next = temp->next;
}
free(temp);
return;
}
temp = temp->next;
}
}
Zaključak
Implementacija heš tabele u C/C++ je moćan pristup za brzo pronalaženje i pristup podacima na osnovu njihovih ključeva. Korišćenjem lančanog heširanja za rešavanje kolizija, možemo efikasno upravljati i velikim skupovima podataka.
Ovladavanje implementacijom heš tabele u C/C++ je ključna veština za svakog programera, omogućavajući efikasno izvršavanje širokog spektra realnih aplikacija.
Često postavljana pitanja (FAQ)
1. Šta je heš tabela?
Heš tabela je struktura podataka koja mapira ključeve na vrednosti. Ona koristi heš funkciju da izračuna heš kod za svaki ključ, koji se zatim koristi za pronalaženje slota u nizu gde se čuva taj ključ.
2. Šta je heš funkcija?
Heš funkcija je funkcija koja mapira ulaz na heš kod, koji je fiksne veličine. Dobro napisana heš funkcija će ravnomerno rasporediti ulaze unutar opsega heš kodova, smanjujući mogućnost kolizija.
3. Šta je kolizija?
Kolizija se javlja kada dva različita ključa generišu isti heš kod. Prilikom rešavanja kolizije, elementi sa istim heš kodom se skladište u posebnu strukturu podataka, kao što je povezana lista ili binarno stablo pretrage.
4. Šta znači „faktor opterećenja“?
Faktor opterećenja je odnos broja elemenata u heš tabeli i broja slotova u nizu. Optimalni faktor opterećenja varira u zavisnosti od implementacije, ali se najčešće kreće između 0.5 i 0.75.
5. Kako se rešavaju kolizije?
Kolizije se mogu rešavati na različite načine, uključujući lančano heširanje, otvoreno adresiranje i dvostruko heširanje. Lančano heširanje skladišti elemente sa istim heš kodom u povezanu listu, dok otvoreno adresiranje pronalazi sledeći dostupan slot u nizu za smeštanje elementa kada dođe do kolizije.
6. Šta je „hosting“ u kontekstu heširanja?
„Hosting“ je tehnika koja se koristi kada heš funkcija nije savršena. Ona uključuje čuvanje originalnih ključeva zajedno sa heš kodovima, tako da se u slučaju kolizije može proveriti tačan ključ da bi se pronašao traženi element.
7. Šta su prilagođene heš funkcije?
Prilagođene heš funkcije su heš funkcije koje su dizajnirane da optimizuju performanse za određeni skup ključeva. One se mogu kreirati na osnovu informacija o distribuciji ključeva.
8. Koje su prednosti korišćenja heš tabele?
Prednosti korišćenja heš tabele uključuju brzo pronalaženje i pristup podacima, efikasno umetanje, pretragu i brisanje, kao i relativno