Hash Table

Hash table adalah struktur data yang memberi operasi lookup, insert, dan delete rata-rata O(1)—jauh lebih cepat dari binary search O(log n). Kunci-kunci dipetakan ke indeks array lewat fungsi hash. Bila dua kunci menghasilkan indeks yang sama (collision), kita perlu strategi penanganan: chaining (linked list di setiap bucket) atau open addressing (cari slot kosong lain). Pada chapter ini kita akan mengimplementasikan kedua strategi pada hash table sederhana, lalu membandingkan tradeoff-nya.

Konsep Hash Table #

Hash table memetakan kunci ke nilai lewat langkah:

Hash function: kunci K dipetakan ke indeks hash(K) % ukuran_tabel.
Storage: array of bucket. Setiap bucket menyimpan satu atau lebih pasangan kunci-nilai.
Collision handling: bila dua kunci menghasilkan indeks yang sama, strategi diperlukan.

Kualitas hash function menentukan distribusi. Fungsi hash yang buruk mengelompokkan kunci di beberapa bucket, menyebabkan chain panjang dan menurunkan performa ke O(n) worst case. Fungsi hash yang baik mendistribusikan kunci merata ke seluruh bucket.

Implementasi dengan Chaining #

Strategi chaining: setiap bucket adalah linked list. Insert menambah node ke depan list di bucket yang sesuai. Search traversal list di bucket.

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

#define UKURAN_TABEL 16

typedef struct entry {
    char *kunci;
    int nilai;
    struct entry *next;
} entry;

typedef struct {
    entry *bucket[UKURAN_TABEL];
    size_t ukuran;
} hash_table;

static char *dup_str(const char *s) {
    size_t n = strlen(s) + 1;
    char *p = malloc(n);
    if (p != NULL) memcpy(p, s, n);
    return p;
}

/* Fungsi hash string sederhana (djb2) */
static unsigned long hash_str(const char *str) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*str++) != 0) {
        h = ((h << 5) + h) + (unsigned long)c;
    }
    return h;
}

void ht_init(hash_table *ht) {
    for (int i = 0; i < UKURAN_TABEL; i++) ht->bucket[i] = NULL;
    ht->ukuran = 0;
}

int ht_set(hash_table *ht, const char *kunci, int nilai) {
    unsigned long h = hash_str(kunci) % UKURAN_TABEL;
    entry *cur = ht->bucket[h];

    /* Update bila kunci sudah ada */
    while (cur != NULL) {
        if (strcmp(cur->kunci, kunci) == 0) {
            cur->nilai = nilai;
            return 0;
        }
        cur = cur->next;
    }

    /* Buat entry baru */
    entry *n = malloc(sizeof(entry));
    if (n == NULL) return -1;
    n->kunci = dup_str(kunci);
    if (n->kunci == NULL) { free(n); return -1; }
    n->nilai = nilai;
    n->next = ht->bucket[h];
    ht->bucket[h] = n;
    ht->ukuran++;
    return 0;
}

int ht_get(hash_table *ht, const char *kunci, int *out) {
    unsigned long h = hash_str(kunci) % UKURAN_TABEL;
    entry *cur = ht->bucket[h];
    while (cur != NULL) {
        if (strcmp(cur->kunci, kunci) == 0) {
            *out = cur->nilai;
            return 0;
        }
        cur = cur->next;
    }
    return -1;
}

void ht_hapus_semua(hash_table *ht) {
    for (int i = 0; i < UKURAN_TABEL; i++) {
        entry *cur = ht->bucket[i];
        while (cur != NULL) {
            entry *tmp = cur->next;
            free(cur->kunci);
            free(cur);
            cur = tmp;
        }
        ht->bucket[i] = NULL;
    }
    ht->ukuran = 0;
}

void ht_statistik(hash_table *ht) {
    int max_chain = 0;
    int bucket_terpakai = 0;
    for (int i = 0; i < UKURAN_TABEL; i++) {
        int chain = 0;
        for (entry *cur = ht->bucket[i]; cur != NULL; cur = cur->next) chain++;
        if (chain > 0) bucket_terpakai++;
        if (chain > max_chain) max_chain = chain;
    }
    printf("Total entry: %zu, bucket terpakai: %d/%d, chain terpanjang: %d\n",
           ht->ukuran, bucket_terpakai, UKURAN_TABEL, max_chain);
}

int main(void) {
    hash_table ht;
    ht_init(&ht);

    ht_set(&ht, "apel", 10);
    ht_set(&ht, "mangga", 20);
    ht_set(&ht, "jeruk", 30);
    ht_set(&ht, "pisang", 40);
    ht_set(&ht, "anggur", 50);
    ht_set(&ht, "durian", 60);
    ht_set(&ht, "apel", 99);  /* update */

    const char *cari[] = {"apel", "jeruk", "durian", "nanas"};
    for (int i = 0; i < 4; i++) {
        int val;
        if (ht_get(&ht, cari[i], &val) == 0)
            printf("%s -> %d\n", cari[i], val);
        else
            printf("%s -> tidak ada\n", cari[i]);
    }

    ht_statistik(&ht);
    ht_hapus_semua(&ht);
    return 0;
}

Output yang Dihasilkan:

text
apel -> 99
jeruk -> 30
durian -> 60
nanas -> tidak ada
Total entry: 6, bucket terpakai: 5/16, chain terpanjang: 2

Implementasi ini memakai hash function djb2 untuk string. Fungsi ht_set mencari dulu apakah kunci sudah ada—bila ya, update nilai; bila tidak, buat entry baru di depan list bucket. Update “apel” dari 10 ke 99 sukses tanpa duplikat entry.

Mari kita telaah baris-baris kode di atas:

Baris 9-14 (struct entry): node linked list dengan field kunci (string heap-allocated), nilai, dan next. Setiap bucket adalah pointer ke entry pertama atau NULL.
Baris 26-31 (hash_str djb2): algoritma hash string klasik. Mulai dengan 5381, lalu untuk setiap karakter: h = h * 33 + c. Modulo % UKURAN_TABEL dilakukan di pemanggil, bukan di sini—agar fungsi hash bisa dipakai untuk tabel berukuran berbeda.
Baris 38-56 (ht_set): hitung indeks, traversal untuk cari kunci yang sama. Bila ketemu, update nilai. Bila tidak, alokasi entry baru, salin kunci dengan dup_str, sisip di depan list bucket.
Baris 58-71 (ht_get): traversal list di bucket yang sesuai. Bila strcmp cocok, kembalikan nilai. Bila tidak ketemu, return -1.
Baris 73-87 (ht_hapus_semua): iterasi semua bucket, bebaskan setiap entry dan string kuncinya. Penting: free(cur->kunci) dulu sebelum free(cur) agar tidak leak string.
Baris 89-103 (ht_statistik): hitung berapa bucket terpakai dan chain terpanjang. Berguna untuk evaluasi kualitas hash function—chain panjang menandakan distribusi buruk.

Implementasi dengan Linear Probing #

Strategi open addressing: tidak ada linked list. Bila slot pertama penuh, coba slot berikutnya, lalu berikutnya, hingga ketemu slot kosong. Linear probing adalah varian paling sederhana: coba idx, idx+1, idx+2, ... (modulo).

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

#define UKURAN_TABEL 16
#define KOSONG -1

typedef struct {
    int kunci;
    int nilai;
} slot;

typedef struct {
    slot tab[UKURAN_TABEL];
    size_t ukuran;
} hash_open;

static unsigned hash_int(int kunci) {
    return (unsigned)(kunci * 2654435761u) % UKURAN_TABEL;
}

void ho_init(hash_open *ht) {
    for (int i = 0; i < UKURAN_TABEL; i++) ht->tab[i].kunci = KOSONG;
    ht->ukuran = 0;
}

int ho_set(hash_open *ht, int kunci, int nilai) {
    if (ht->ukuran >= UKURAN_TABEL) return -1;

    unsigned idx = hash_int(kunci);
    for (size_t i = 0; i < UKURAN_TABEL; i++) {
        unsigned probe = (idx + i) % UKURAN_TABEL;
        if (ht->tab[probe].kunci == KOSONG) {
            ht->tab[probe].kunci = kunci;
            ht->tab[probe].nilai = nilai;
            ht->ukuran++;
            return 0;
        }
        if (ht->tab[probe].kunci == kunci) {
            ht->tab[probe].nilai = nilai;
            return 0;
        }
    }
    return -1;
}

int ho_get(hash_open *ht, int kunci, int *out) {
    unsigned idx = hash_int(kunci);
    for (size_t i = 0; i < UKURAN_TABEL; i++) {
        unsigned probe = (idx + i) % UKURAN_TABEL;
        if (ht->tab[probe].kunci == KOSONG) return -1;
        if (ht->tab[probe].kunci == kunci) {
            *out = ht->tab[probe].nilai;
            return 0;
        }
    }
    return -1;
}

void ho_cetak(hash_open *ht) {
    printf("Tabel hash (ukuran=%zu):\n", ht->ukuran);
    for (int i = 0; i < UKURAN_TABEL; i++) {
        if (ht->tab[i].kunci != KOSONG) {
            printf("  [%2d] kunci=%d nilai=%d\n", i, ht->tab[i].kunci, ht->tab[i].nilai);
        }
    }
}

int main(void) {
    hash_open ht;
    ho_init(&ht);

    int kunci[] = {10, 20, 30, 26, 42, 15, 8};
    int nilai[] = {100, 200, 300, 260, 420, 150, 80};
    int n = sizeof(kunci) / sizeof(kunci[0]);

    for (int i = 0; i < n; i++) {
        ho_set(&ht, kunci[i], nilai[i]);
    }

    ho_cetak(&ht);

    int cari[] = {10, 26, 42, 99};
    for (int i = 0; i < 4; i++) {
        int val;
        if (ho_get(&ht, cari[i], &val) == 0)
            printf("get(%d) = %d\n", cari[i], val);
        else
            printf("get(%d) = tidak ada\n", cari[i]);
    }

    return 0;
}

Output yang Dihasilkan:

text
Tabel hash (ukuran=7):
  [ 4] kunci=20 nilai=200
  [ 8] kunci=8 nilai=80
  [10] kunci=10 nilai=100
  [11] kunci=26 nilai=260
  [12] kunci=42 nilai=420
  [14] kunci=30 nilai=300
  [15] kunci=15 nilai=150
get(10) = 100
get(26) = 260
get(42) = 420
get(99) = tidak ada

Pada output, kunci 26 dan 42 tidak berada di indeks hasil hash-nya (hash_int(26) = 6, hash_int(42) = 10), tetapi pada slot berikutnya karena terjadi collision. Linear probing mencari slot kosong berurutan ke kanan.

Perbandingan Strategi #

Aspek	Chaining	Open Addressing (Linear Probing)
Memori tambahan	1 pointer per entry	0 (semua di dalam array)
Collision handling	Linked list di bucket	Probe slot berikutnya
Kapasitas	Tak terbatas (terbatas memori)	Terbatas ukuran tabel
Performa worst case	`O(n)` (semua kunci di satu bucket)	`O(n)` (semua slot penuh)
Performa rata-rata	`O(1 + n/ukuran_tabel)`	`O(1 / (1 - load_factor))`
Load factor ideal	< 1.0 (chain pendek OK)	< 0.7 (mencegah clustering)
Iterasi	Traversal linked list	Traversal array + skip KOSONG
Delete	Mudah (hapus node)	Sulit (perlu tombstone marker)