Çarpışma Çözümleme Collision Handling

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

#define INIT_SIZE  11
#define MAX_LOAD   0.75

typedef struct Entry {
    char* key;
    int   value;
    struct Entry* next;
} Entry;

typedef struct {
    Entry** buckets;
    int     size;      // kova sayısı
    int     count;     // eleman sayısı
} ChainTable;

unsigned int hashDJB2(const char* k, int sz) {
    unsigned long h = 5381;
    while (*k) h = h * 33 + *k++;
    return h % sz;
}

ChainTable* chainOlustur(int sz) {
    ChainTable* t = malloc(sizeof(ChainTable));
    t->size = sz; t->count = 0;
    t->buckets = calloc(sz, sizeof(Entry*));
    return t;
}

/* ── Ekleme ── */
void chainEkle(ChainTable* t, const char* key, int val) {
    unsigned int idx = hashDJB2(key, t->size);
    // Var mı? Güncelle
    for (Entry* e = t->buckets[idx]; e; e = e->next)
        if (strcmp(e->key, key) == 0) { e->value = val; return; }
    // Yeni — başa ekle
    Entry* e = malloc(sizeof(Entry));
    e->key = strdup(key); e->value = val;
    e->next = t->buckets[idx];
    t->buckets[idx] = e;
    t->count++;
}

/* ── Arama ── */
int chainAra(ChainTable* t, const char* key, bool* ok) {
    unsigned int idx = hashDJB2(key, t->size);
    for (Entry* e = t->buckets[idx]; e; e = e->next)
        if (strcmp(e->key, key) == 0) { *ok=true; return e->value; }
    *ok = false; return -1;
}

/* ── Silme ── */
bool chainSil(ChainTable* t, const char* key) {
    unsigned int idx = hashDJB2(key, t->size);
    Entry* curr = t->buckets[idx], *prev = NULL;
    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            if (prev) prev->next = curr->next;
            else      t->buckets[idx] = curr->next;
            free(curr->key); free(curr);
            t->count--;
            return true;
        }
        prev = curr; curr = curr->next;
    }
    return false;
}

#define TABLE_SIZE  11
#define EMPTY      -1
#define DELETED    -2   // tombstone

typedef struct {
    char* key;
    int   value;
    int   state;    // EMPTY, DELETED, veya 0 (dolu)
} Slot;

typedef struct {
    Slot* slots;
    int   size;
    int   count;
} LinearTable;

/* ── Ekleme ── */
void linearEkle(LinearTable* t, const char* key, int val) {
    unsigned int idx = hashDJB2(key, t->size);

    for (int i = 0; i < t->size; i++) {
        int pos = (idx + i) % t->size;   // linear probe

        if (t->slots[pos].state == EMPTY ||
            t->slots[pos].state == DELETED) {
            // Boş veya silinmiş → yerleştir
            t->slots[pos].key   = strdup(key);
            t->slots[pos].value = val;
            t->slots[pos].state = 0;
            t->count++;
            return;
        }
        if (strcmp(t->slots[pos].key, key) == 0) {
            t->slots[pos].value = val;  // güncelle
            return;
        }
    }
}

/* ── Arama ── */
int linearAra(LinearTable* t, const char* key, bool* ok) {
    unsigned int idx = hashDJB2(key, t->size);

    for (int i = 0; i < t->size; i++) {
        int pos = (idx + i) % t->size;

        if (t->slots[pos].state == EMPTY) {
            *ok = false;  return -1;  // boş → yok
        }
        if (t->slots[pos].state != DELETED &&
            strcmp(t->slots[pos].key, key) == 0) {
            *ok = true;  return t->slots[pos].value;
        }
        // DELETED → atla, aramaya devam
    }
    *ok = false;  return -1;
}

/* ── Silme (Tombstone) ── */
bool linearSil(LinearTable* t, const char* key) {
    unsigned int idx = hashDJB2(key, t->size);

    for (int i = 0; i < t->size; i++) {
        int pos = (idx + i) % t->size;
        if (t->slots[pos].state == EMPTY) return false;
        if (t->slots[pos].state != DELETED &&
            strcmp(t->slots[pos].key, key) == 0) {
            free(t->slots[pos].key);
            t->slots[pos].state = DELETED;  // ★ tombstone!
            t->count--;
            return true;
        }
    }
    return false;
}

void quadEkle(LinearTable* t, const char* key, int val) {
    unsigned int h = hashDJB2(key, t->size);

    for (int i = 0; i < t->size; i++) {
        int pos = (h + i * i) % t->size;  // ★ i² adım

        if (t->slots[pos].state == EMPTY ||
            t->slots[pos].state == DELETED) {
            t->slots[pos].key   = strdup(key);
            t->slots[pos].value = val;
            t->slots[pos].state = 0;
            t->count++;
            return;
        }
        if (strcmp(t->slots[pos].key, key) == 0) {
            t->slots[pos].value = val;
            return;
        }
    }
}

#define PRIME2  7  // m'den küçük asal

unsigned int hash2(int key) {
    return PRIME2 - (key % PRIME2);  // asla 0 olmaz ✓
}

void doubleEkle(LinearTable* t, int key, int val) {
    unsigned int h1 = key % t->size;
    unsigned int h2 = hash2(key);

    for (int i = 0; i < t->size; i++) {
        int pos = (h1 + i * h2) % t->size; // ★ double hash

        if (t->slots[pos].state == EMPTY ||
            t->slots[pos].state == DELETED) {
            t->slots[pos].value = val;
            t->slots[pos].state = 0;
            t->count++;
            return;
        }
    }
}

int doubleAra(LinearTable* t, int key, bool* ok) {
    unsigned int h1 = key % t->size;
    unsigned int h2 = hash2(key);

    for (int i = 0; i < t->size; i++) {
        int pos = (h1 + i * h2) % t->size;
        if (t->slots[pos].state == EMPTY)
            { *ok = false; return -1; }
        if (t->slots[pos].state != DELETED &&
            t->slots[pos].value == key) // int key örneği
            { *ok = true; return t->slots[pos].value; }
    }
    *ok = false; return -1;
}

Eklenecek anahtarlar: 22, 1, 13, 11, 24, 33
Tablo boyutu: 11

══════ Chaining (Zincirleme) ══════
  insert(22): idx=0, zincir uzunluğu 1      ← 0 çarpışma
  insert(1):  idx=1, zincir uzunluğu 1
  insert(13): idx=2, zincir uzunluğu 1
  insert(11): idx=0, zincir uzunluğu 2      ← çarpışma! 22 ile aynı kova
  insert(24): idx=2, zincir uzunluğu 2      ← çarpışma! 13 ile aynı kova
  insert(33): idx=0, zincir uzunluğu 3      ← çarpışma! 22,11 ile aynı kova

  Tablo durumu:
    [0]: 33 → 11 → 22 → ∅   (zincir: 3)
    [1]: 1 → ∅               (zincir: 1)
    [2]: 24 → 13 → ∅         (zincir: 2)
    [3-10]: ∅
  Toplam probe: 6 (her ekleme 1)

══════ Linear Probing ══════
  insert(22): pos=0                          ← 1 probe
  insert(1):  pos=1                          ← 1 probe
  insert(13): pos=2                          ← 1 probe
  insert(11): 0(dolu)→1(dolu)→2(dolu)→pos=3 ← 4 probe! küme
  insert(24): 2(dolu)→3(dolu)→pos=4          ← 3 probe
  insert(33): 0,1,2,3,4(dolu)→pos=5          ← 6 probe! küme büyüdü

  Tablo: [22][1][13][11][24][33][ ][ ][ ][ ][ ]
         ← ──────── küme ──────── →
  Toplam probe: 16                           ← kümeleme etkisi belirgin

══════ Double Hashing (h₂ = 7 - key%7) ══════
  insert(22): pos=0                          ← 1 probe
  insert(1):  pos=1                          ← 1 probe
  insert(13): pos=2                          ← 1 probe
  insert(11): h₁=0,h₂=3 → 0(dolu)→pos=3    ← 2 probe
  insert(24): h₁=2,h₂=4 → 2(dolu)→pos=6    ← 2 probe
  insert(33): h₁=0,h₂=2 → 0(dolu)→pos=2    ← 2(dolu)→pos=4
              0,2(dolu)→pos=4                ← 3 probe

  Tablo: [22][1][13][11][33][ ][24][ ][ ][ ][ ]
          ↑     ↑   ↑   ↑      ↑   ← dağınık, küme yok!
  Toplam probe: 10                           ← linear'dan %38 daha az

══════ Sonuç ══════
  Chaining :  6 probe  (her ekleme O(1), ama zincir uzar)
  Linear   : 16 probe  (kümeleme → feci)
  Double   : 10 probe  (dengeli dağılım ✓)