Hash Tablosu Uygulamaları

/* Bir sonraki asal sayıyı bul */
bool asalMi(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}
int sonrakiAsal(int n) {
    while (!asalMi(n)) n++;
    return n;
}

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

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

    // 2) Tüm elemanları yeniden hash'le
    for (int i = 0; i < eskiBoyut; i++) {
        Entry* curr = eskiBuckets[i];
        while (curr) {
            Entry* next = curr->next;
            // Yeni indeks hesapla (boyut değişti!)
            unsigned int yeniIdx = hash(curr->key, ht->size);
            curr->next = ht->buckets[yeniIdx];
            ht->buckets[yeniIdx] = curr;
            ht->count++;
            curr = next;
        }
    }
    free(eskiBuckets); // 3) Eski diziyi serbest bırak
    printf("Rehash: %d → %d (α: %.2f)\n",
           eskiBoyut, ht->size,
           (float)ht->count / ht->size);
}

/* Akıllı ekleme — α kontrollü */
void tabloEkleAkilli(HashTable* ht, const char* key, int val) {
    if ((float)ht->count / ht->size >= 0.75f)
        rehash(ht);
    tabloEkle(ht, key, val);
}

/* Dizi elemanlarının frekansını say */
void frekansSay(const char* kelimeler[], int n) {
    HashTable* ht = tabloOlustur(17);

    for (int i = 0; i < n; i++) {
        bool found;
        int count = tabloAra(ht, kelimeler[i], &found);

        if (found)
            tabloEkle(ht, kelimeler[i], count + 1);  // +1
        else
            tabloEkle(ht, kelimeler[i], 1);          // ilk kez
    }

    // Tabloyu yazdır
    for (int i = 0; i < ht->size; i++) {
        Entry* e = ht->buckets[i];
        while (e) {
            printf("  %-10s : %d\n", e->key, e->value);
            e = e->next;
        }
    }
}

/* Kullanım */
const char* kelimeler[] = {
    "elma", "armut", "elma",
    "kiraz", "elma", "armut"
};
frekansSay(kelimeler, 6);
// Çıktı:
//   elma       : 3
//   armut      : 2
//   kiraz      : 1

/* Karakter frekansı — basit dizi tabanlı hash */
void karakterFrekans(const char* str) {
    int freq[256] = {0};  // ASCII "hash tablosu"

    for (int i = 0; str[i]; i++)
        freq[(unsigned char)str[i]]++;

    printf("Karakter frekansları:\n");
    for (int i = 0; i < 256; i++)
        if (freq[i] > 0)
            printf("  '%c' : %d\n", i, freq[i]);
}

karakterFrekans("merhaba dünya");
// 'a' : 2, 'b' : 1, 'd' : 1, 'e' : 1, ...

/* Dizide tekrar eden ilk elemanı bul */
int ilkTekrar(int arr[], int n) {
    HashTable* set = tabloOlustur(sonrakiAsal(n * 2));

    for (int i = 0; i < n; i++) {
        char key[20];
        sprintf(key, "%d", arr[i]);

        bool found;
        tabloAra(set, key, &found);

        if (found) {
            tabloYikici(set);
            return arr[i];  // tekrar bulundu!
        }
        tabloEkle(set, key, 1);  // sete ekle
    }
    tabloYikici(set);
    return -1;  // tekrar yok
}

/* Tüm tekrar eden elemanları bul */
void tumTekrarlar(int arr[], int n) {
    HashTable* freq = tabloOlustur(sonrakiAsal(n * 2));

    // Adım 1: Frekansları say
    for (int i = 0; i < n; i++) {
        char key[20];
        sprintf(key, "%d", arr[i]);
        bool found;
        int cnt = tabloAra(freq, key, &found);
        tabloEkle(freq, key, found ? cnt + 1 : 1);
    }

    // Adım 2: Frekansı > 1 olanları yazdır
    printf("Tekrar eden elemanlar:\n");
    for (int i = 0; i < freq->size; i++) {
        Entry* e = freq->buckets[i];
        while (e) {
            if (e->value > 1)
                printf("  %s (%d kez)\n", e->key, e->value);
            e = e->next;
        }
    }
}

/* İki dizinin kesişimi — hash set ile */
int* diziKesisim(int A[], int n,
                 int B[], int m,
                 int* sonucBoyut) {
    // Küçük diziyi hash'le (bellek tasarrufu)
    int* kucuk = n <= m ? A : B;
    int  kBoy  = n <= m ? n : m;
    int* buyuk = n <= m ? B : A;
    int  bBoy  = n <= m ? m : n;

    // Adım 1: Küçük diziyi set'e ekle
    HashTable* set = tabloOlustur(sonrakiAsal(kBoy * 2));
    for (int i = 0; i < kBoy; i++) {
        char key[20];
        sprintf(key, "%d", kucuk[i]);
        tabloEkle(set, key, 1);
    }

    // Adım 2: Büyük diziyi tara
    int* sonuc = malloc(kBoy * sizeof(int));
    int idx = 0;

    for (int i = 0; i < bBoy; i++) {
        char key[20];
        sprintf(key, "%d", buyuk[i]);
        bool found;
        tabloAra(set, key, &found);

        if (found) {
            sonuc[idx++] = buyuk[i];
            tabloSil(set, key);  // tekrar eklemeyi önle
        }
    }

    *sonucBoyut = idx;
    tabloYikici(set);
    return sonuc;
}

/* Kullanım */
int A[] = {3, 7, 1, 5, 9, 4};
int B[] = {2, 5, 8, 3, 6, 4, 10};
int boyut;
int* sonuc = diziKesisim(A, 6, B, 7, &boyut);
// sonuc = [5, 3, 4], boyut = 3

/* İki elemanın toplamı = hedef → indeksleri döndür */
bool twoSum(int arr[], int n, int hedef,
            int* idx1, int* idx2) {
    HashTable* ht = tabloOlustur(sonrakiAsal(n * 2));

    for (int i = 0; i < n; i++) {
        int tamamlayici = hedef - arr[i];
        char key[20];
        sprintf(key, "%d", tamamlayici);

        bool found;
        int j = tabloAra(ht, key, &found);

        if (found) {
            *idx1 = j; *idx2 = i;
            tabloYikici(ht);
            return true;
        }

        // arr[i]'yi tabloya ekle (değer = indeks)
        sprintf(key, "%d", arr[i]);
        tabloEkle(ht, key, i);
    }
    tabloYikici(ht);
    return false;
}

bool anagramMi(const char* s1, const char* s2) {
    if (strlen(s1) != strlen(s2)) return false;

    int freq[256] = {0};  // karakter hash tablosu

    // s1'in karakterlerini say (+)
    for (int i = 0; s1[i]; i++)
        freq[(unsigned char)s1[i]]++;

    // s2'nin karakterlerini çıkar (-)
    for (int i = 0; s2[i]; i++)
        freq[(unsigned char)s2[i]]--;

    // Tüm sayaçlar 0 olmalı
    for (int i = 0; i < 256; i++)
        if (freq[i] != 0) return false;

    return true;
}

printf("%d\n", anagramMi("listen", "silent"));  // 1 (true)
printf("%d\n", anagramMi("hello",  "world"));   // 0 (false)