Како имплементирати пример табеле хеширања у C/C++

Како имплементирати пример табеле хеширања у C/C++

Увод

Табеле хеширања су фундаменталне структуре података које се користе за брзо проналажење и приступ елементима на основу њихових кључева. Оне су веома ефикасне за обављање операција као што су убацивање, претраживање и брисање, што их чини идеалним за бројне апликације, укључујући базе података, кеширање и превођење табела.

У овом чланку ћемо истражити како да имплементирамо једноставну табелу хеширања у C/C++, користећи ланчану хеширање за решавање колизија.

Имплементација табеле хеширања

Структура хеш табеле

Табела хеширања се састоји од низа „слотова“, где сваки слот представља касу за елементе са истим хеш кодом. Хеш код је нумеричка вредност изведена из кључа елемента коришћењем хеш функције.

У нашој имплементацији, користимо двоструко повезану листу за сваки слот, што нам омогућава да ефикасно додамо, претражимо и обришемо елементе.

c++
struct HashNode {
int key;
int value;
struct HashNode* next;
struct HashNode* prev;
};

struct HashTable {
int TABLE_SIZE;
struct HashNode** table;
};

Хеш функција

Хеш функција је функција која мапира кључ на хеш код. Добро написана хеш функција ће равномерно распоредити кључеве у слотове, смањујући вероватноћу колизија. У нашој имплементацији користимо просту модуло операцију да генеришемо хеш код:

c++
int hashFunction(int key, int TABLE_SIZE) {
return key % TABLE_SIZE;
}

Убацивање елемента

За убацивање елемента у табелу хеширања, прво израчунамо хеш код кључа и добијемо слот. Затим проверавамо да ли тај слот већ има елементе у њему. Ако нема, једноставно додамо нови елемент на крају листе. Ако слот већ има елементе, додајемо нови елемент на почетак листе:

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

Претраживање елемента

За претраживање елемента у табели хеширања, израчунавамо хеш код кључа и добијамо слот. Затим траверзирамо кроз листу унутар слота и упоређујемо кључеве док не пронађемо тражени елемент:

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

Бришање елемента

За брисање елемента из табеле хеширања, прво израчунавамо хеш код кључа и добијамо слот. Затим траверзирамо кроз листу унутар слота и уклањамо елемент ако нађемо подударање кључа:

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

Закључак

Имплементација табеле хеширања у C/C++ је моћна техника за брзо проналажење и приступ елементима на основу њихових кључева. Користећи ланчану хеширање за решавање колизија, можемо ефикасно управљати чак и великим скуповима података.

Имплементирање табеле хеширања у C/C++ је важна вештина за програмере, јер омогућава ефикасно извршавање широког спектра апликација у стварном свету.

Често постављана питања (FAQs)

1. Шта је табела хеширања?
Табела хеширања је структура података која мапира кључеве на вредности. Она користи хеш функцију да генерише хеш код за сваки кључ, који се затим користи за проналажење слота у низу где се чува тај кључ.

2. Шта је хеш функција?
Хеш функција је функција која мапира улаз на хеш код, који је фиксиране величине. Добро написана хеш функција ће равномерно распоредити улазе у опсег хеш кодова, смањујући вероватноћу колизија.

3. Шта је колизија?
Колизија се јавља када два различита кључа производе исти хеш код. Током решавања колизије, елементи са истим хеш кодом се складиште у посебну структуру података, као што је ланчана листа или бинарно стабло претраге.

4. Шта значи „фактор оптерећења“?
Фактор оптерећења је број елемената у табели хеширања подељен са бројем слотова у низу. Оптимални фактор оптерећења варира у зависности од имплементације, али типично се креће између 0,5 и 0,75.

5. Како се решавају колизије?
Колизије се могу решавати на више начина, укључујући ланчано хеширање, отворено адресирање и двојно хеширање. Ланчано хеширање чува елементе са истим хеш кодом у ланчаној листи, док отворено адресирање проналази следећи слот у низу за чување елемента када дође до колизије.

6. Шта је „хостинг“ у контексту хеширања?
Хостинг је техника коју се користи када је хеш функција несавршена. Она укључује чување оригиналних кључева заједно са хеш кодовима, тако да се у случају колизије може проверити тачан кључ да би се пронашао елемент.

7. Које су прилагођене функције хеширања?
Прилагођене функције хеширања су хеш функције које су дизајниране да оптимизују перформансе за одређени скуп кључева. Оне се могу креирати коришћењем информација о дистрибуцији кључева.

8. Које су предности коришћења табеле хеширања?
Предности коришћења табеле хеширања укључују брзо проналажење и приступ, ефикасно убацивање, претраживање и брисање, и релативно