Hash Tablosu

Veri Yapıları O(1) average O(n)

Anahtarları bir hash fonksiyonuyla kovalara eşler; çakışmalar her kovanın içinde bağlı liste olarak zincirlenir.

∅

Kodu adım adım izlemek için bir işlem seçin.

DeğişmezHer anahtar hash(anahtar) kovasında durur, bu yüzden arama tüm tabloyu değil tek zinciri tarar.

hash-table.c

#define BUCKETS 8
 
typedef struct Entry {
    int key;
    struct Entry *next;
} Entry;
 
Entry *table[BUCKETS];
 
int hash(int key) {
    return ((key % BUCKETS) + BUCKETS) % BUCKETS;
}
 
void insert(int key) {
    int b = hash(key);
    Entry *e = malloc(sizeof(Entry));
    e->key = key;
    e->next = table[b];   /* chain on collision */
    table[b] = e;
}
 
int contains(int key) {
    for (Entry *e = table[hash(key)]; e; e = e->next)
        if (e->key == key) return 1;
    return 0;
}

Hash Tablosu nasıl çalışır?

Hash fonksiyonu her anahtarı bir kovaya eşler. Arama doğru kovaya doğrudan atlar ve yalnızca o kovanın (kısa) çakışma zincirini yürür.

En iyi durum

Düzgün dağılım — ~1 uzunluklu zincirler: işlem başına O(1).

En kötü durum

Tüm anahtarlar tek kovada çakışır: O(n) zincir yürüyüşü.

Ne zaman kullanılır?

Varsayılan sözlük/küme: sıra önemli değilken sabit zamanlı erişim.