Bagian 4: Hash Table

Hash table adalah struktur data key-value yang menawarkan pencarian rata-rata O(1). Berbeda dari linked list (O(n) untuk pencarian), hash table memakai fungsi hash untuk menentukan di mana nilai disimpan. Pada bagian ini kita membangun hash_table.h dan hash_table.c dengan chaining (linked list di setiap bucket) sebagai strategi collision resolution. Tujuan bagian ini adalah memahami bagaimana hash table bekerja dan kapan memakainya sebagai pengganti linked list.

Konsep #

Hash table bekerja dengan tiga komponen: (1) array dari bucket (ukuran tetap), (2) fungsi hash yang memetakan key ke indeks bucket, dan (3) strategi penanganan collision (dua key yang hash ke indeks sama). Kita memakai strategi chaining — setiap bucket berisi linked list node yang kunci-nya hash ke bucket tersebut.

Mekanisme ht_put: hitung idx = hash(key) % HT_SIZE, traverse linked list di bucket idx untuk cari node dengan key sama. Bila ditemukan, update value (tidak ada duplikat). Bila tidak ditemukan, alokasikan node baru, isi key dan value, sisipkan di awal linked list bucket (next = bucket[idx]; bucket[idx] = n). Mekanisme ht_get: hitung idx, traverse linked list bucket, kembalikan value bila key cocok, atau error bila tidak ditemukan.

Fungsi hash kita memakai FNV-1a (Fowler-Noll-Vo variant 1a), algoritma hash non-kriptografi populer karena cepat dan distribusi baik. Setiap byte key di-XOR dengan state hash, lalu state dikalikan konstanta 16777619u. Akhirnya state dimodulo HT_SIZE untuk mendapat indeks bucket. Karakteristik hash yang baik: input berbeda menghasilkan output berbeda (avalanche effect), distribusi merata di seluruh bucket.

Implementasi #

Header hash_table.h:

c
#ifndef HASH_TABLE_H
#define HASH_TABLE_H

#define HT_SIZE 8

typedef struct HashNode {
    char key[32];
    int  value;
    struct HashNode *next;
} HashNode;

typedef struct {
    HashNode *buckets[HT_SIZE];
} HashTable;

void ht_init(HashTable *ht);
void ht_put(HashTable *ht, const char *key, int value);
int  ht_get(const HashTable *ht, const char *key, int *out);

#endif /* HASH_TABLE_H */

Implementasi hash_table.c:

c
#include "hash_table.h"
#include <stdlib.h>
#include <string.h>

static unsigned int hash(const char *key) {
    unsigned int h = 2166136261u;
    while (*key != '\0') {
        h ^= (unsigned char)*key++;
        h *= 16777619u;
    }
    return h % HT_SIZE;
}

void ht_init(HashTable *ht) {
    for (int i = 0; i < HT_SIZE; i++) ht->buckets[i] = 0;
}

void ht_put(HashTable *ht, const char *key, int value) {
    unsigned int idx = hash(key);
    HashNode *cur = ht->buckets[idx];
    while (cur != 0) {
        if (strcmp(cur->key, key) == 0) {
            cur->value = value;
            return;
        }
        cur = cur->next;
    }
    HashNode *n = (HashNode *)malloc(sizeof(HashNode));
    if (n == 0) return;
    strncpy(n->key, key, sizeof(n->key) - 1);
    n->key[sizeof(n->key) - 1] = '\0';
    n->value = value;
    n->next = ht->buckets[idx];
    ht->buckets[idx] = n;
}

int ht_get(const HashTable *ht, const char *key, int *out) {
    unsigned int idx = hash(key);
    HashNode *cur = ht->buckets[idx];
    while (cur != 0) {
        if (strcmp(cur->key, key) == 0) {
            *out = cur->value;
            return 0;
        }
        cur = cur->next;
    }
    return -1;
}

Demo mandiri:

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

#define HT_SIZE 8

typedef struct HashNode {
    char key[32];
    int  value;
    struct HashNode *next;
} HashNode;

typedef struct {
    HashNode *buckets[HT_SIZE];
} HashTable;

static unsigned int hash(const char *key) {
    unsigned int h = 2166136261u;
    while (*key != '\0') {
        h ^= (unsigned char)*key++;
        h *= 16777619u;
    }
    return h % HT_SIZE;
}

static void ht_init(HashTable *ht) {
    for (int i = 0; i < HT_SIZE; i++) ht->buckets[i] = 0;
}

static void ht_put(HashTable *ht, const char *key, int value) {
    unsigned int idx = hash(key);
    HashNode *cur = ht->buckets[idx];
    while (cur != 0) {
        if (strcmp(cur->key, key) == 0) {
            cur->value = value;
            return;
        }
        cur = cur->next;
    }
    HashNode *n = (HashNode *)malloc(sizeof(HashNode));
    if (n == 0) return;
    strncpy(n->key, key, sizeof(n->key) - 1);
    n->key[sizeof(n->key) - 1] = '\0';
    n->value = value;
    n->next = ht->buckets[idx];
    ht->buckets[idx] = n;
}

static int ht_get(const HashTable *ht, const char *key, int *out) {
    unsigned int idx = hash(key);
    HashNode *cur = ht->buckets[idx];
    while (cur != 0) {
        if (strcmp(cur->key, key) == 0) {
            *out = cur->value;
            return 0;
        }
        cur = cur->next;
    }
    return -1;
}

int main(void) {
    HashTable ht;
    ht_init(&ht);
    ht_put(&ht, "Budi", 25);
    ht_put(&ht, "Siti", 30);
    ht_put(&ht, "Andi", 28);

    int v;
    if (ht_get(&ht, "Siti", &v) == 0) printf("Siti -> %d\n", v);
    if (ht_get(&ht, "Budi", &v) == 0) printf("Budi -> %d\n", v);
    if (ht_get(&ht, "Dewi", &v) == 0) printf("Dewi -> %d\n", v);
    else printf("Dewi tidak ditemukan\n");

    printf("Distribusi bucket:\n");
    for (int i = 0; i < HT_SIZE; i++) {
        int count = 0;
        for (HashNode *c = ht.buckets[i]; c != 0; c = c->next) count++;
        printf("  bucket[%d] = %d node\n", i, count);
    }
    return 0;
}

Output yang Dihasilkan:

text
Siti -> 30
Budi -> 25
Dewi tidak ditemukan
Distribusi bucket:
  bucket[0] = 0 node
  bucket[1] = 0 node
  bucket[2] = 1 node
  bucket[3] = 0 node
  bucket[4] = 0 node
  bucket[5] = 1 node
  bucket[6] = 0 node
  bucket[7] = 1 node

Pengujian #

Build dan jalankan:

bash
gcc -std=c11 -Wall -Wextra -o hash_demo hash_table.c main.c
./hash_demo

Verifikasi perilaku update value: lakukan ht_put("Budi", 25) lalu ht_put("Budi", 26) — lookup harus menghasilkan 26, bukan 25. Tanpa traversal yang memeriksa key existing, kita akan mendapat dua node dengan key "Budi" di bucket yang sama — bug duplikat.

Untuk menguji collision distribution, masukkan 1000 key random lalu periksa panjang setiap bucket. Distribusi yang baik menghasilkan ~125 node per bucket (1000 / 8). Bila satu bucket berisi 800 node dan lainnya kosong, fungsi hash buruk.

bash
gcc -std=c11 -Wall -Wextra -fsanitize=address -o hash_asan hash_table.c main.c
./hash_asan 2>&1 | tail -5

Output yang Dihasilkan (potongan akhir):

text

SUMMARY: AddressSanitizer: 144 byte(s) leaked in 3 allocation(s).

ASan melaporkan tiga leak — masing-masing 48 byte (satu HashNode), total 144 byte. Demo memang tidak membebaskan node saat program keluar, sehingga leak ini sengaja dibiarkan untuk memotivasi Bagian 5 yang membahas pola _init/_destroy konsisten. Di Bagian 5 kita akan menambahkan ht_destroy yang traverse setiap bucket dan free setiap node.

Mari kita telaah baris-baris kunci pada hash dan ht_put:

Baris unsigned int h = 2166136261u;: inisialisasi FNV-1a offset basis. Konstanta ini dipilih oleh penulis algoritma berdasarkan eksperimen distribusi — bukan angka acak.
Baris h ^= (unsigned char)*key++;: XOR byte key ke hash, lalu advance pointer. Cast ke unsigned char penting — tanpa cast, karakter dengan bit tertinggi set (mis. UTF-8) akan menyebabkan sign extension yang menghasilkan hash negatif.
Baris h *= 16777619u;: konstanta FNV prime. Kombinasi XOR-multiply memberikan avalanche effect — perubahan 1 bit di input mengubah ~50% bit di output.
Baris return h % HT_SIZE;: modulo untuk dapatkan indeks bucket. HT_SIZE idealnya bilangan prima agar distribusi merata — kita pakai 8 (bukan prima) untuk kesederhanaan demo.
Baris HashNode *cur = ht->buckets[idx];: mulai traverse dari head bucket. Indeks idx sudah dijamin dalam [0, HT_SIZE) berkat modulo.
Baris while (cur != 0) loop dalam ht_put: cari node dengan key sama. Bila ditemukan, update value dan return — tidak menambah node baru. Bila tidak ditemukan, lanjut ke kode setelah loop yang menambahkan node baru.
Baris strncpy(n->key, key, sizeof(n->key) - 1); n->key[sizeof(n->key) - 1] = '\0';: salin key dengan batas aman. strncpy tidak selalu null-terminate bila key lebih panjang dari buffer, sehingga kita tambahkan null terminator manual.
Baris n->next = ht->buckets[idx]; ht->buckets[idx] = n;: sisipkan di awal linked list bucket (prepend). Operasi O(1) — tidak perlu traverse ke akhir.

Pada Bagian 5 kita akan membahas pola manajemen memori yang konsisten — _init/_destroy untuk setiap struktur data, realloc untuk resize dinamis, dan strategi deteksi leak.

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

c
/* hash_table.c -- simple hash table with chaining. */
#define _POSIX_C_SOURCE 200809L /* for strdup */
#include "hash_table.h"

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

/* djb2 hash function by Daniel J. Bernstein. */
static unsigned long hash_djb2(const char *str) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*str++)) {
        h = ((h << 5) + h) + c; /* h * 33 + c */
    }
    return h;
}

int ht_init(HashTable *ht, size_t capacity) {
    if (!ht || capacity == 0) return -1;
    ht->buckets = calloc(capacity, sizeof(HTNode *));
    if (!ht->buckets) return -1;
    ht->capacity = capacity;
    ht->size = 0;
    return 0;
}

void ht_destroy(HashTable *ht) {
    if (!ht) return;
    for (size_t i = 0; i < ht->capacity; i++) {
        HTNode *cur = ht->buckets[i];
        while (cur) {
            HTNode *next = cur->next;
            free(cur->key);
            free(cur);
            cur = next;
        }
    }
    free(ht->buckets);
    ht->buckets = NULL;
    ht->capacity = 0;
    ht->size = 0;
}

int ht_put(HashTable *ht, const char *key, int value) {
    if (!ht || !key) return -1;
    unsigned long h = hash_djb2(key) % ht->capacity;
    /* Update if key exists. */
    HTNode *cur = ht->buckets[h];
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            cur->value = value;
            return 0;
        }
        cur = cur->next;
    }
    /* Insert new node at head. */
    HTNode *node = malloc(sizeof(*node));
    if (!node) return -1;
    node->key = strdup(key);
    if (!node->key) {
        free(node);
        return -1;
    }
    node->value = value;
    node->next = ht->buckets[h];
    ht->buckets[h] = node;
    ht->size++;
    return 0;
}

int ht_get(const HashTable *ht, const char *key, int *out) {
    if (!ht || !key) return -1;
    unsigned long h = hash_djb2(key) % ht->capacity;
    HTNode *cur = ht->buckets[h];
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (out) *out = cur->value;
            return 0;
        }
        cur = cur->next;
    }
    return -1;
}

int ht_remove(HashTable *ht, const char *key) {
    if (!ht || !key) return -1;
    unsigned long h = hash_djb2(key) % ht->capacity;
    HTNode *cur = ht->buckets[h];
    HTNode *prev = NULL;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) prev->next = cur->next;
            else      ht->buckets[h] = cur->next;
            free(cur->key);
            free(cur);
            ht->size--;
            return 0;
        }
        prev = cur;
        cur = cur->next;
    }
    return -1;
}

size_t ht_size(const HashTable *ht) {
    return ht ? ht->size : 0;
}

c
/* linked_list.c -- singly linked list implementation. */
#include "linked_list.h"

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

void ll_init(LinkedList *list) {
    if (!list) return;
    list->head = NULL;
    list->size = 0;
}

void ll_destroy(LinkedList *list) {
    if (!list) return;
    LLNode *cur = list->head;
    while (cur) {
        LLNode *next = cur->next;
        free(cur);
        cur = next;
    }
    list->head = NULL;
    list->size = 0;
}

int ll_push_front(LinkedList *list, int value) {
    if (!list) return -1;
    LLNode *node = malloc(sizeof(*node));
    if (!node) return -1;
    node->data = value;
    node->next = list->head;
    list->head = node;
    list->size++;
    return 0;
}

int ll_push_back(LinkedList *list, int value) {
    if (!list) return -1;
    LLNode *node = malloc(sizeof(*node));
    if (!node) return -1;
    node->data = value;
    node->next = NULL;
    if (!list->head) {
        list->head = node;
    } else {
        LLNode *cur = list->head;
        while (cur->next) cur = cur->next;
        cur->next = node;
    }
    list->size++;
    return 0;
}

int ll_pop_front(LinkedList *list, int *out) {
    if (!list || !list->head) return -1;
    LLNode *node = list->head;
    if (out) *out = node->data;
    list->head = node->next;
    free(node);
    list->size--;
    return 0;
}

int ll_get(const LinkedList *list, size_t index, int *out) {
    if (!list || !out || index >= list->size) return -1;
    LLNode *cur = list->head;
    for (size_t i = 0; i < index; i++) cur = cur->next;
    *out = cur->data;
    return 0;
}

int ll_remove(LinkedList *list, size_t index) {
    if (!list || index >= list->size) return -1;
    LLNode *to_free;
    if (index == 0) {
        to_free = list->head;
        list->head = to_free->next;
    } else {
        LLNode *prev = list->head;
        for (size_t i = 0; i < index - 1; i++) prev = prev->next;
        to_free = prev->next;
        prev->next = to_free->next;
    }
    free(to_free);
    list->size--;
    return 0;
}

int ll_find(const LinkedList *list, int value) {
    if (!list) return -1;
    LLNode *cur = list->head;
    int index = 0;
    while (cur) {
        if (cur->data == value) return index;
        cur = cur->next;
        index++;
    }
    return -1;
}

size_t ll_size(const LinkedList *list) {
    return list ? list->size : 0;
}

void ll_print(const LinkedList *list) {
    if (!list) return;
    printf("[");
    LLNode *cur = list->head;
    while (cur) {
        printf("%d", cur->data);
        if (cur->next) printf(", ");
        cur = cur->next;
    }
    printf("]\n");
}

c
/* main.c -- demo of all four data structures. */
#include "linked_list.h"
#include "stack.h"
#include "queue.h"
#include "hash_table.h"

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

static void demo_linked_list(void) {
    printf("--- Linked List ---\n");
    LinkedList list;
    ll_init(&list);

    ll_push_back(&list, 10);
    ll_push_back(&list, 20);
    ll_push_back(&list, 30);
    ll_push_front(&list, 5);
    printf("After pushes: ");
    ll_print(&list);
    printf("Size: %zu\n", ll_size(&list));
    printf("Find 20: index %d\n", ll_find(&list, 20));

    int v;
    ll_pop_front(&list, &v);
    printf("After pop_front (%d): ", v);
    ll_print(&list);

    ll_destroy(&list);
    printf("\n");
}

static void demo_stack(void) {
    printf("--- Stack ---\n");
    Stack s;
    if (stack_init(&s, 4) != 0) {
        printf("stack_init failed\n");
        return;
    }

    stack_push(&s, 1);
    stack_push(&s, 2);
    stack_push(&s, 3);
    printf("Size: %zu\n", stack_size(&s));

    int v;
    while (!stack_is_empty(&s)) {
        stack_pop(&s, &v);
        printf("Popped: %d\n", v);
    }

    stack_destroy(&s);
    printf("\n");
}

static void demo_queue(void) {
    printf("--- Queue ---\n");
    Queue q;
    if (queue_init(&q, 4) != 0) {
        printf("queue_init failed\n");
        return;
    }

    queue_enqueue(&q, 10);
    queue_enqueue(&q, 20);
    queue_enqueue(&q, 30);
    printf("Size: %zu\n", queue_size(&q));

    int v;
    while (!queue_is_empty(&q)) {
        queue_dequeue(&q, &v);
        printf("Dequeued: %d\n", v);
    }

    queue_destroy(&q);
    printf("\n");
}

static void demo_hash_table(void) {
    printf("--- Hash Table ---\n");
    HashTable ht;
    if (ht_init(&ht, 8) != 0) {
        printf("ht_init failed\n");
        return;
    }

    ht_put(&ht, "satu", 1);
    ht_put(&ht, "dua", 2);
    ht_put(&ht, "tiga", 3);
    printf("Size: %zu\n", ht_size(&ht));

    int v;
    if (ht_get(&ht, "dua", &v) == 0) printf("get(dua) = %d\n", v);
    if (ht_get(&ht, "empat", &v) != 0) printf("get(empat) not found\n");

    ht_remove(&ht, "dua");
    printf("After remove dua, size: %zu\n", ht_size(&ht));

    ht_destroy(&ht);
    printf("\n");
}

int main(void) {
    printf("== Struktur Data Demo ==\n\n");
    demo_linked_list();
    demo_stack();
    demo_queue();
    demo_hash_table();
    printf("== Selesai ==\n");
    return 0;
}

c
/* queue.c -- FIFO queue (circular buffer). */
#include "queue.h"

#include <stdlib.h>

int queue_init(Queue *q, size_t capacity) {
    if (!q || capacity == 0) return -1;
    q->data = malloc(capacity * sizeof(int));
    if (!q->data) return -1;
    q->capacity = capacity;
    q->head = 0;
    q->tail = 0;
    q->size = 0;
    return 0;
}

void queue_destroy(Queue *q) {
    if (!q) return;
    free(q->data);
    q->data = NULL;
    q->capacity = 0;
    q->head = q->tail = q->size = 0;
}

int queue_enqueue(Queue *q, int value) {
    if (!q || q->size >= q->capacity) return -1;
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) % q->capacity;
    q->size++;
    return 0;
}

int queue_dequeue(Queue *q, int *out) {
    if (!q || q->size == 0) return -1;
    if (out) *out = q->data[q->head];
    q->head = (q->head + 1) % q->capacity;
    q->size--;
    return 0;
}

int queue_is_empty(const Queue *q) {
    return !q || q->size == 0;
}

size_t queue_size(const Queue *q) {
    return q ? q->size : 0;
}

c
/* stack.c -- LIFO stack (dynamic array). */
#include "stack.h"

#include <stdlib.h>

int stack_init(Stack *s, size_t capacity) {
    if (!s || capacity == 0) return -1;
    s->data = malloc(capacity * sizeof(int));
    if (!s->data) return -1;
    s->capacity = capacity;
    s->size = 0;
    return 0;
}

void stack_destroy(Stack *s) {
    if (!s) return;
    free(s->data);
    s->data = NULL;
    s->capacity = 0;
    s->size = 0;
}

int stack_push(Stack *s, int value) {
    if (!s) return -1;
    if (s->size >= s->capacity) {
        size_t new_cap = s->capacity * 2;
        int *p = realloc(s->data, new_cap * sizeof(int));
        if (!p) return -1;
        s->data = p;
        s->capacity = new_cap;
    }
    s->data[s->size++] = value;
    return 0;
}

int stack_pop(Stack *s, int *out) {
    if (!s || stack_is_empty(s)) return -1;
    if (out) *out = s->data[--s->size];
    return 0;
}

int stack_peek(const Stack *s, int *out) {
    if (!s || stack_is_empty(s) || !out) return -1;
    *out = s->data[s->size - 1];
    return 0;
}

int stack_is_empty(const Stack *s) {
    return !s || s->size == 0;
}

size_t stack_size(const Stack *s) {
    return s ? s->size : 0;
}

c
/* tests.c -- unit tests for all four data structures.
 *
 * Compile with:
 *   gcc -std=c11 -Wall -Wextra -fsanitize=address,undefined \
 *       tests.c linked_list.c stack.c queue.c hash_table.c -o test_runner
 */
#include "linked_list.h"
#include "stack.h"
#include "queue.h"
#include "hash_table.h"

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

static int tests_passed = 0;
static int tests_failed = 0;

#define ASSERT(cond, msg) do { \
    if (cond) { tests_passed++; } \
    else { tests_failed++; printf("FAIL: %s (line %d)\n", msg, __LINE__); } \
} while (0)

static void test_linked_list(void) {
    LinkedList list;
    ll_init(&list);
    ASSERT(ll_size(&list) == 0, "ll empty size");

    ll_push_back(&list, 10);
    ll_push_back(&list, 20);
    ll_push_front(&list, 5);
    ASSERT(ll_size(&list) == 3, "ll size after push");

    int v;
    ASSERT(ll_get(&list, 0, &v) == 0 && v == 5, "ll get(0) == 5");
    ASSERT(ll_get(&list, 2, &v) == 0 && v == 20, "ll get(2) == 20");

    ASSERT(ll_find(&list, 10) == 1, "ll find(10) == 1");
    ASSERT(ll_find(&list, 99) == -1, "ll find(99) not found");

    ASSERT(ll_pop_front(&list, &v) == 0 && v == 5, "ll pop_front == 5");
    ASSERT(ll_size(&list) == 2, "ll size after pop");

    ll_remove(&list, 0);
    ASSERT(ll_size(&list) == 1, "ll size after remove");

    ll_destroy(&list);
    ASSERT(ll_size(&list) == 0, "ll size after destroy");
}

static void test_stack(void) {
    Stack s;
    ASSERT(stack_init(&s, 2) == 0, "stack_init ok");
    ASSERT(stack_is_empty(&s), "stack empty initially");

    ASSERT(stack_push(&s, 100) == 0, "stack_push 100");
    ASSERT(stack_push(&s, 200) == 0, "stack_push 200");
    /* Force a grow. */
    ASSERT(stack_push(&s, 300) == 0, "stack_push 300 (grow)");

    ASSERT(stack_size(&s) == 3, "stack size 3");

    int v;
    ASSERT(stack_peek(&s, &v) == 0 && v == 300, "stack_peek == 300");
    ASSERT(stack_pop(&s, &v) == 0 && v == 300, "stack_pop == 300");
    ASSERT(stack_pop(&s, &v) == 0 && v == 200, "stack_pop == 200");
    ASSERT(stack_pop(&s, &v) == 0 && v == 100, "stack_pop == 100");
    ASSERT(stack_is_empty(&s), "stack empty at end");
    ASSERT(stack_pop(&s, &v) == -1, "stack_pop on empty returns -1");

    stack_destroy(&s);
}

static void test_queue(void) {
    Queue q;
    ASSERT(queue_init(&q, 4) == 0, "queue_init ok");
    ASSERT(queue_is_empty(&q), "queue empty initially");

    for (int i = 1; i <= 4; i++) {
        ASSERT(queue_enqueue(&q, i * 10) == 0, "queue_enqueue");
    }
    ASSERT(queue_size(&q) == 4, "queue full size");

    int v;
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 10, "queue_dequeue 10");
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 20, "queue_dequeue 20");
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 30, "queue_dequeue 30");
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 40, "queue_dequeue 40");
    ASSERT(queue_is_empty(&q), "queue empty after drain");
    ASSERT(queue_dequeue(&q, &v) == -1, "queue_dequeue on empty");

    queue_destroy(&q);
}

static void test_hash_table(void) {
    HashTable ht;
    ASSERT(ht_init(&ht, 4) == 0, "ht_init ok");
    ASSERT(ht_size(&ht) == 0, "ht empty");

    ASSERT(ht_put(&ht, "alpha", 1) == 0, "ht_put alpha");
    ASSERT(ht_put(&ht, "beta", 2) == 0, "ht_put beta");
    ASSERT(ht_put(&ht, "gamma", 3) == 0, "ht_put gamma");
    ASSERT(ht_size(&ht) == 3, "ht size 3");

    int v;
    ASSERT(ht_get(&ht, "beta", &v) == 0 && v == 2, "ht_get beta");
    ASSERT(ht_get(&ht, "missing", &v) == -1, "ht_get missing");

    /* Update existing key. */
    ASSERT(ht_put(&ht, "beta", 22) == 0, "ht_put beta update");
    ASSERT(ht_get(&ht, "beta", &v) == 0 && v == 22, "ht_get beta updated");
    ASSERT(ht_size(&ht) == 3, "ht size unchanged after update");

    ASSERT(ht_remove(&ht, "alpha") == 0, "ht_remove alpha");
    ASSERT(ht_get(&ht, "alpha", &v) == -1, "ht_get alpha gone");
    ASSERT(ht_size(&ht) == 2, "ht size 2 after remove");

    ht_destroy(&ht);
}

int main(void) {
    test_linked_list();
    test_stack();
    test_queue();
    test_hash_table();

    printf("\n=== Test Results ===\n");
    printf("Passed: %d\n", tests_passed);
    printf("Failed: %d\n", tests_failed);
    if (tests_failed == 0) {
        printf("Lulus : %d\n", tests_passed);
        return 0;
    }
    return 1;
}