Hash Table Tasarımı: Çarpışma Çözme Yöntemleri ve Kod Örnekleri
Hash table'lar hızlı veri erişimi sağlar, ancak iki farklı anahtar aynı hash değerine denk gelirse çarpışma meydana gelir. Bu sorunu çözmek için iki ana strateji vardır: chaining ve open addressing.
Chaining yönteminde her hash pozisyonunda bir bağlı liste tutarız. Çarpışan öğeler aynı konumda zincir halinde saklanır. Basit ve etkilidir, fakat ekstra bellek gerektirir.
Open addressing ise çarpışma durumunda başka bir boş pozisyon arar. Linear probing, quadratic probing ve double hashing gibi teknikler kullanılır.
Aşağıda C ile chaining yöntemi ile basit bir hash table uygulaması var:
1#include <stdio.h>2#include <stdlib.h>3#include <string.h>45#define TABLE_SIZE 1067typedef struct Node {8char *key;9int value;10struct Node *next;11} Node;1213typedef struct {14Node *table[TABLE_SIZE];15} HashTable;1617int hash(char *key) {18int sum = 0;19for (int i = 0; key[i]!= '\0'; i++) {20sum += key[i];21}22return sum % TABLE_SIZE;23}2425HashTable* createHashTable() {26HashTable *ht = (HashTable*)malloc(sizeof(HashTable));27for (int i = 0; i < TABLE_SIZE; i++) {28ht->table[i] = NULL;29}30return ht;31}3233void insert(HashTable *ht, char *key, int value) {34int index = hash(key);35Node *newNode = (Node*)malloc(sizeof(Node));36newNode->key = (char*)malloc(strlen(key) + 1);37strcpy(newNode->key, key);38newNode->value = value;39newNode->next = ht->table[index];40ht->table[index] = newNode;41}4243int search(HashTable *ht, char *key) {44int index = hash(key);45Node *current = ht->table[index];46while (current!= NULL) {47if (strcmp(current->key, key) == 0) {48return current->value;49}50current = current->next;51}52return -1;53}5455int main() {56HashTable *ht = createHashTable();5758insert(ht, "ali", 100);59insert(ht, "veli", 200);60insert(ht, "ayse", 300);6162printf("ali: %d\n", search(ht, "ali"));63printf("veli: %d\n", search(ht, "veli"));64printf("ayse: %d\n", search(ht, "ayse"));65printf("osman: %d\n", search(ht, "osman"));6667return 0;68}Beklenen çıktı:
1ali: 1002veli: 2003ayse: 3004osman: -1Bu kod chaining ile çarpışmaları yönetir. Aynı hash değerine sahip anahtarlar bağlı liste içinde ard arda saklanır. `search` fonksiyonu zinciri takip ederek doğru değeri bulur.
Open addressing için linear probing kullanırsanız, çarpışmada bir sonraki boş pozisyonu kontrol edersiniz. Chaining daha basit ve dinamik veri için iyiyken, open addressing daha az bellek tüketir ama tablo dolunca performans düşer. Hangi yöntemi seçeceğiniz veri setinizin büyüklüğü ve çarpışma oranına bağlıdır.
0 yorum