KAL
Menu

Hash Table dan Trie

Fungsi hash, penanganan tabrakan dengan chaining, pengubahan ukuran, dan trie.

Daftar isi

Hash table (tabel hash) menyimpan pasangan kunci dan nilai pada sebuah array. Hash function atau fungsi hash menghitung posisi setiap kunci secara langsung, sehingga pencarian tidak perlu menyusuri data satu per satu. Dua kunci yang berbeda kadang jatuh ke slot yang sama, dan kejadian ini disebut tabrakan (collision). Topik ini membangun hash table dengan penanganan tabrakan berupa chaining, membahas pengubahan ukuran saat tabel penuh, lalu menutupnya dengan trie, yaitu pohon prefiks yang menyimpan kata per karakter.

Fungsi hash dan penanganan tabrakan#

Fungsi hash mengubah kunci menjadi indeks array, dan versi yang paling sederhana untuk kunci berupa string adalah menjumlahkan nilai setiap karakternya lalu mengambil sisa bagi banyaknya slot. Slot array pada hash table lazim disebut bucket, dan setiap bucket boleh memuat lebih dari satu entri. Strategi chaining menampung tabrakan dengan rantai linked list pada setiap bucket, sehingga entri baru tetap dapat disisipkan meskipun indeksnya sudah terisi.

Diagram berikut memperlihatkan tabel lima bucket yang diisi lima kunci daftar belanja. Tiga kunci, yaitu beras, kopi, dan gula, kebetulan berbagi bucket 0 karena jumlah nilai karakternya sama-sama habis dibagi lima, sehingga ketiganya tersusun sebagai satu rantai.

bucket0beras=2kopi=1gula=11telur=12234minyak=2NULLNULLNULLNULL
Tabel lima bucket dengan rantai entri pada bucket yang bertabrakan

Program utuh berikut menerapkan ide tersebut. Fungsi sisip_entri memakai pointer ke pointer struct entri **tempat, sehingga penyisipan di ujung rantai maupun pembaruan kunci yang sudah ada ditangani dalam satu perulangan. Fungsi cari_entri menghitung banyaknya perbandingan agar biaya pencarian pada rantai terlihat.

c hash-table.c 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUCKET_AWAL 5

struct entri {
    char kunci[16];
    int nilai;
    struct entri *berikut;
};

struct tabel {
    struct entri **bucket;
    int jumlah_bucket;
};

unsigned int fungsi_hash(const char *kunci, int jumlah_bucket)
{
    unsigned int total = 0;
    for (int i = 0; kunci[i] != '\0'; i++) {
        total = total + (unsigned char)kunci[i];
    }
    return total % jumlah_bucket;
}

void tabel_buat(struct tabel *t, int jumlah_bucket)
{
    t->bucket = calloc(jumlah_bucket, sizeof(struct entri *));
    if (t->bucket == NULL) {
        fprintf(stderr, "Alokasi gagal.\n");
        exit(1);
    }
    t->jumlah_bucket = jumlah_bucket;
}

void sisip_entri(struct tabel *t, const char *kunci, int nilai)
{
    unsigned int indeks = fungsi_hash(kunci, t->jumlah_bucket);

    struct entri **tempat = &t->bucket[indeks];
    while (*tempat != NULL) {
        if (strcmp((*tempat)->kunci, kunci) == 0) {
            (*tempat)->nilai = nilai;   /* kunci sudah ada, perbarui nilainya */
            return;
        }
        tempat = &(*tempat)->berikut;
    }

    struct entri *baru = malloc(sizeof(struct entri));
    if (baru == NULL) {
        fprintf(stderr, "Alokasi gagal.\n");
        exit(1);
    }
    snprintf(baru->kunci, sizeof baru->kunci, "%s", kunci);
    baru->nilai = nilai;
    baru->berikut = NULL;
    *tempat = baru;
}

struct entri *cari_entri(struct tabel *t, const char *kunci, int *perbandingan)
{
    *perbandingan = 0;
    unsigned int indeks = fungsi_hash(kunci, t->jumlah_bucket);
    struct entri *e = t->bucket[indeks];
    while (e != NULL) {
        *perbandingan = *perbandingan + 1;
        if (strcmp(e->kunci, kunci) == 0) {
            return e;
        }
        e = e->berikut;
    }
    return NULL;
}

void tabel_perbesar(struct tabel *t, int jumlah_baru)
{
    struct entri **bucket_baru = calloc(jumlah_baru, sizeof(struct entri *));
    if (bucket_baru == NULL) {
        fprintf(stderr, "Alokasi gagal.\n");
        exit(1);
    }
    for (int i = 0; i < t->jumlah_bucket; i++) {
        struct entri *e = t->bucket[i];
        while (e != NULL) {
            struct entri *berikutnya = e->berikut;
            unsigned int indeks = fungsi_hash(e->kunci, jumlah_baru);
            e->berikut = bucket_baru[indeks];
            bucket_baru[indeks] = e;
            e = berikutnya;
        }
    }
    free(t->bucket);
    t->bucket = bucket_baru;
    t->jumlah_bucket = jumlah_baru;
}

void tabel_cetak(const struct tabel *t)
{
    for (int i = 0; i < t->jumlah_bucket; i++) {
        printf("bucket %2d:", i);
        if (t->bucket[i] == NULL) {
            printf(" (kosong)");
        } else {
            for (struct entri *e = t->bucket[i]; e != NULL; e = e->berikut) {
                printf(" %s=%d", e->kunci, e->nilai);
                if (e->berikut != NULL) {
                    printf(" ->");
                }
            }
        }
        printf("\n");
    }
}

void tabel_bebaskan(struct tabel *t)
{
    for (int i = 0; i < t->jumlah_bucket; i++) {
        struct entri *e = t->bucket[i];
        while (e != NULL) {
            struct entri *berikutnya = e->berikut;
            free(e);
            e = berikutnya;
        }
    }
    free(t->bucket);
    t->bucket = NULL;
    t->jumlah_bucket = 0;
}

int main(void)
{
    struct tabel t;
    tabel_buat(&t, BUCKET_AWAL);

    sisip_entri(&t, "beras", 2);
    sisip_entri(&t, "kopi", 1);
    sisip_entri(&t, "telur", 12);
    sisip_entri(&t, "gula", 1);
    sisip_entri(&t, "minyak", 2);

    printf("Tabel dengan %d bucket:\n", t.jumlah_bucket);
    tabel_cetak(&t);

    int perbandingan = 0;
    struct entri *hasil = cari_entri(&t, "gula", &perbandingan);
    if (hasil != NULL) {
        printf("Cari 'gula': nilai %d, %d perbandingan.\n", hasil->nilai, perbandingan);
    }

    tabel_perbesar(&t, 11);
    printf("Tabel setelah diperbesar ke %d bucket:\n", t.jumlah_bucket);
    tabel_cetak(&t);

    tabel_bebaskan(&t);
    return 0;
}
text Keluaran 
Tabel dengan 5 bucket:
bucket  0: beras=2 -> kopi=1 -> gula=1
bucket  1: telur=12
bucket  2: (kosong)
bucket  3: (kosong)
bucket  4: minyak=2
Cari 'gula': nilai 1, 3 perbandingan.
Tabel setelah diperbesar ke 11 bucket:
bucket  0: minyak=2
bucket  1: (kosong)
bucket  2: (kosong)
bucket  3: (kosong)
bucket  4: (kosong)
bucket  5: (kosong)
bucket  6: telur=12 -> kopi=1
bucket  7: gula=1
bucket  8: beras=2
bucket  9: (kosong)
bucket 10: (kosong)

Pencarian gula membutuhkan tiga perbandingan karena kunci itu menempati posisi ketiga pada rantai bucket 0, dan panjang rantai inilah yang menentukan biaya pencarian setelah fungsi hash menemukan bucketnya.

Pengubahan ukuran tabel#

Rasio banyaknya entri terhadap banyaknya bucket disebut load factor, atau α=n/m\alpha = n / m. Nilai inilah yang menentukan panjang rantai rata-rata ketika fungsi hash menyebar kuncinya secara merata. Apabila α\alpha terus tumbuh, pencarian makin lama karena makin banyak entri berbagi satu bucket. Solusinya adalah membuat array bucket yang lebih besar lalu memindahkan seluruh entri ke posisi barunya. Langkah ini disebut rehash karena fungsi hash dipanggil ulang untuk setiap kunci terhadap banyak bucket yang baru.

Fungsi tabel_perbesar pada program di atas melakukan rehash tanpa mengalokasikan entri baru, yaitu mengaitkan kembali setiap simpul lama ke bucket baru. Dampaknya terlihat pada keluaran program. Rantai tiga kunci pada bucket 0 pecah menjadi tiga bucket berbeda, meskipun bucket 6 tetap memuat dua kunci karena tabrakan tidak pernah sepenuhnya mustahil. Pemilihan waktu perbesaran biasanya mengikuti ambang α\alpha, misalnya perbesar ketika rasionya melampaui 1. Biaya rehash sekali jalan itu dibayar dengan pencarian yang tetap cepat setelahnya.

Trie sebagai pohon prefiks#

Trie menyimpan kata per karakter, yaitu setiap simpul memuat satu huruf dan setiap jalur dari akar ke penanda akhir kata membentuk satu kata utuh. Kata-kata yang berbagi awalan juga berbagi jalur yang sama, sehingga trie sangat hemat untuk koleksi kata dengan banyak awalan bersama. Pencarian kata utuh dan penghitungan awalan bergerak sepanjang kedalaman kata, tidak bergantung pada banyaknya kata yang tersimpan.

mulaikautkdaiakatakakikudaLingkaran ganda menandai akhir sebuah kata.
Trie untuk kata kaki, kata, dan kuda yang berbagi awalan huruf k

Program berikut memakai simpul yang berisi 26 pointer anak, satu untuk setiap huruf kecil, dengan penanda akhir_kata yang membedakan simpul perhentian dari simpul jalur. Kata kak berhenti di simpul yang bukan akhir kata sehingga dianggap tidak ada, sedangkan prefiks ka menjangkau dua kata yang tersimpan di bawahnya.

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

#define ANAK 26

struct simpul_trie {
    struct simpul_trie *anak[ANAK];
    int akhir_kata;
};

struct simpul_trie *simpul_baru(void)
{
    struct simpul_trie *baru = calloc(1, sizeof(struct simpul_trie));
    if (baru == NULL) {
        fprintf(stderr, "Alokasi gagal.\n");
        exit(1);
    }
    return baru;
}

void trie_sisip(struct simpul_trie *akar, const char *kata)
{
    struct simpul_trie *p = akar;
    for (int i = 0; kata[i] != '\0'; i++) {
        int indeks = kata[i] - 'a';
        if (p->anak[indeks] == NULL) {
            p->anak[indeks] = simpul_baru();
        }
        p = p->anak[indeks];
    }
    p->akhir_kata = 1;
}

int trie_cari(struct simpul_trie *akar, const char *kata)
{
    struct simpul_trie *p = akar;
    for (int i = 0; kata[i] != '\0'; i++) {
        int indeks = kata[i] - 'a';
        if (p->anak[indeks] == NULL) {
            return 0;
        }
        p = p->anak[indeks];
    }
    return p->akhir_kata;
}

struct simpul_trie *turun_prefiks(struct simpul_trie *akar, const char *prefiks)
{
    struct simpul_trie *p = akar;
    for (int i = 0; prefiks[i] != '\0'; i++) {
        int indeks = prefiks[i] - 'a';
        if (p->anak[indeks] == NULL) {
            return NULL;
        }
        p = p->anak[indeks];
    }
    return p;
}

int hitung_kata(struct simpul_trie *p)
{
    if (p == NULL) {
        return 0;
    }
    int jumlah = p->akhir_kata;
    for (int i = 0; i < ANAK; i++) {
        jumlah = jumlah + hitung_kata(p->anak[i]);
    }
    return jumlah;
}

void trie_bebaskan(struct simpul_trie *p)
{
    if (p == NULL) {
        return;
    }
    for (int i = 0; i < ANAK; i++) {
        trie_bebaskan(p->anak[i]);
    }
    free(p);
}

int main(void)
{
    struct simpul_trie *akar = simpul_baru();

    trie_sisip(akar, "kata");
    trie_sisip(akar, "kaki");
    trie_sisip(akar, "kuda");

    printf("Cari 'kata'  : %s\n", trie_cari(akar, "kata") ? "ditemukan" : "tidak ada");
    printf("Cari 'kak'   : %s\n", trie_cari(akar, "kak") ? "ditemukan" : "tidak ada");
    printf("Cari 'kamu'  : %s\n", trie_cari(akar, "kamu") ? "ditemukan" : "tidak ada");

    printf("Prefiks 'ka' : %d kata\n", hitung_kata(turun_prefiks(akar, "ka")));
    printf("Prefiks 'ku' : %d kata\n", hitung_kata(turun_prefiks(akar, "ku")));

    trie_bebaskan(akar);
    return 0;
}
text Keluaran 
Cari 'kata'  : ditemukan
Cari 'kak'   : tidak ada
Cari 'kamu'  : tidak ada
Prefiks 'ka' : 2 kata
Prefiks 'ku' : 1 kata

Alokasi simpul trie memakai calloc alih-alih malloc karena seluruh 26 pointer anak harus dimulai dari NULL, dan calloc menjamin keadaan nol tersebut tanpa perulangan tambahan. Model 26 anak per simpul memang boros ketika kata-katanya jarang berbagi awalan, sehingga trie untuk alfabet besar sering memakai peta anak yang lebih hemat.

Kesalahan umum#

Lima kesalahan berikut mencakup kedua struktur data, dan sebagian besar bermuara pada indeks atau kunci yang tidak diperiksa sebelum dipakai.

  • Fungsi hash yang tidak merata. Fungsi yang mengambil satu karakter saja, atau yang menjumlahkan karakter tanpa operasi sisa bagi, membuat banyak kunci bergerombol pada bucket yang sama. Rantai yang panjang menaikkan biaya pencarian hingga setara pencarian linier. Uji sebarannya dengan data kunci nyata.
  • Membaca kunci dari rantai tanpa pemeriksaan NULL. Perulangan rantai harus berhenti pada NULL, dan pembacaan e->kunci pada e yang sudah NULL menghentikan program. Gunakan kondisi while (e != NULL) sebagaimana cari_entri.
  • Lupa menyalin kunci ke entri. Menyimpan const char * yang menunjuk buffer pemanggil membuat entri bergantung pada memori yang bisa saja sudah dibebaskan. Salin karakternya ke dalam struct, atau alokasikan salinan tersendiri.
  • Menghitung panjang kata sebagai ukuran trie. Pencarian trie berjalan sepanjang kedalaman huruf, bukan banyaknya kata tersimpan, sehingga trie dengan jutaan kata tetap cepat selama katanya pendek.
  • Memakai karakter di luar huruf kecil pada trie. Perhitungan kata[i] - 'a' menghasilkan indeks di luar 0 sampai 25 untuk huruf besar, angka, atau tanda baca, dan penulisan di luar array itulah penyebab banyak crash. Normalisasi masukan menjadi huruf kecil lebih dahulu atau perluas tabel anaknya.

Ringkasan#

  • Fungsi hash memetakan kunci ke indeks bucket, dan tabrakan ditangani chaining berupa linked list pada bucket yang sama.
  • Load factor α=n/m\alpha = n / m menjadi penanda waktu perbesaran tabel, dan rehash memindahkan entri lama ke bucket hasil perhitungan baru.
  • Trie menyimpan kata per karakter dengan jalur awalan yang dibagi bersama, sehingga pencarian kata dan penghitungan prefiks hanya bergantung pada panjang katanya.

Referensi#