Hash Tabloları Hash Temelleri

/* 1) Bölme metodu (Division) — en basit */
unsigned int hashBolme(const char* key, int tablo_boyutu) {
    unsigned int hash = 0;
    for (int i = 0; key[i]; i++)
        hash += key[i];
    return hash % tablo_boyutu;
}

/* 2) DJB2 — yaygın, basit, iyi dağılım */
unsigned int hashDJB2(const char* key, int tablo_boyutu) {
    unsigned long hash = 5381;
    int c;
    while ((c = *key++))
        hash = hash * 33 + c;  // hash × 33 + karakter
    return hash % tablo_boyutu;
}

/* 3) Tam sayı anahtarlar için — Knuth çarpma */
unsigned int hashKnuth(int key, int tablo_boyutu) {
    return (key * 2654435761u) >> 16 % tablo_boyutu;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define TABLO_BOYUTU  11  // asal sayı!

/* Anahtar-değer çifti */
typedef struct Entry {
    char*  key;            // anahtar (string)
    int    value;           // değer
    struct Entry* next;     // çarpışma zinciri (chaining)
} Entry;

/* Hash tablosu */
typedef struct {
    Entry** buckets;       // kova dizisi
    int     size;           // tablo boyutu
    int     count;          // eleman sayısı
} HashTable;

/* Hash fonksiyonu — DJB2 */
unsigned int hash(const char* key, int size) {
    unsigned long h = 5381;
    int c;
    while ((c = *key++))
        h = h * 33 + c;
    return h % size;
}

/* Tablo oluştur */
HashTable* tabloOlustur(int size) {
    HashTable* ht = malloc(sizeof(HashTable));
    ht->size    = size;
    ht->count   = 0;
    ht->buckets = calloc(size, sizeof(Entry*));
    return ht;
}

void tabloEkle(HashTable* ht, const char* key, int value) {
    unsigned int idx = hash(key, ht->size);

    // Aynı anahtar varsa güncelle
    Entry* curr = ht->buckets[idx];
    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            curr->value = value;  // güncelle
            return;
        }
        curr = curr->next;
    }

    // Yeni entry oluştur — başa ekle (O(1))
    Entry* entry = malloc(sizeof(Entry));
    entry->key   = strdup(key);
    entry->value = value;
    entry->next  = ht->buckets[idx];  // eski baş → next
    ht->buckets[idx] = entry;          // yeni baş
    ht->count++;
}

int tabloAra(HashTable* ht, const char* key, bool* found) {
    unsigned int idx = hash(key, ht->size);
    Entry* curr = ht->buckets[idx];

    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            *found = true;
            return curr->value;  // bulundu!
        }
        curr = curr->next;
    }
    *found = false;
    return -1;  // bulunamadı
}

bool tabloSil(HashTable* ht, const char* key) {
    unsigned int idx = hash(key, ht->size);
    Entry* curr = ht->buckets[idx];
    Entry* prev = NULL;

    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            // Bağlı listeden çıkar
            if (prev)
                prev->next = curr->next;
            else
                ht->buckets[idx] = curr->next;

            free(curr->key);
            free(curr);
            ht->count--;
            return true;   // silindi
        }
        prev = curr;
        curr = curr->next;
    }
    return false;  // bulunamadı
}

void rehash(HashTable* ht) {
    int eskiBoyut = ht->size;
    Entry** eskiBuckets = ht->buckets;

    // Yeni boyut: ~2× en yakın asal
    ht->size = sonrakiAsal(eskiBoyut * 2);
    ht->buckets = calloc(ht->size, sizeof(Entry*));
    ht->count = 0;

    // Tüm elemanları yeniden hash'le
    for (int i = 0; i < eskiBoyut; i++) {
        Entry* curr = eskiBuckets[i];
        while (curr) {
            Entry* next = curr->next;
            tabloEkle(ht, curr->key, curr->value);
            free(curr->key);
            free(curr);
            curr = next;
        }
    }
    free(eskiBuckets);
}

/* tabloEkle içinde rehash tetikleme */
void tabloEkleAkilli(HashTable* ht, const char* key, int val) {
    if ((float)ht->count / ht->size >= 0.75f)
        rehash(ht);   // α ≥ 0.75 → genişlet
    tabloEkle(ht, key, val);
}

int main() {
    HashTable* ht = tabloOlustur(11);

    // ── Ekleme ──
    printf("=== Hash Table Demo ===\n\n");
    tabloEkle(ht, "Ali",   85);
    tabloEkle(ht, "Ayşe",  92);
    tabloEkle(ht, "Can",   78);
    tabloEkle(ht, "Deniz", 95);
    tabloEkle(ht, "Elif",  88);
    printf("5 eleman eklendi. count=%d, size=%d\n",
           ht->count, ht->size);

    // ── Arama ──
    printf("\n--- Arama ---\n");
    bool found;
    int val;
    const char* aramalar[] = {"Ali","Can","Zeynep","Elif"};
    for (int i = 0; i < 4; i++) {
        val = tabloAra(ht, aramalar[i], &found);
        if (found)
            printf("  %s → %d ✓\n", aramalar[i], val);
        else
            printf("  %s → bulunamadı ✗\n", aramalar[i]);
    }

    // ── Güncelleme ──
    printf("\n--- Güncelleme ---\n");
    tabloEkle(ht, "Ali", 90);  // 85 → 90
    val = tabloAra(ht, "Ali", &found);
    printf("  Ali güncellendi: %d\n", val);

    // ── Silme ──
    printf("\n--- Silme ---\n");
    printf("  delete(\"Elif\"): %s\n",
           tabloSil(ht,"Elif") ? "silindi ✓" : "yok");
    printf("  delete(\"Zeynep\"): %s\n",
           tabloSil(ht,"Zeynep") ? "silindi" : "bulunamadı ✗");
    printf("  search(\"Elif\"): %s\n",
           tabloAra(ht,"Elif",&found)?"var":"yok ✗");
    printf("  Kalan eleman: %d\n", ht->count);

    return 0;
}

=== Hash Table Demo ===

5 eleman eklendi. count=5, size=11

--- Arama ---
  Ali → 85 ✓
  Can → 78 ✓
  Zeynep → bulunamadı ✗             ← tabloda yok
  Elif → 88 ✓                       ← çarpışma zincirinde bulundu

--- Güncelleme ---
  Ali güncellendi: 90                ← aynı key ile tekrar ekle → değer güncellendi

--- Silme ---
  delete("Elif"): silindi ✓         ← zincirden çıkarıldı
  delete("Zeynep"): bulunamadı ✗    ← tabloda yok
  search("Elif"): yok ✗             ← artık bulunamaz
  Kalan eleman: 4