Hash Table

Apa itu Hash Table?

Hash Table adalah struktur data yang digunakan untuk mengimplementasikan array asosiatif atau mapping, di mana data disimpan dalam pasangan key-value. Key digunakan untuk mengindeks value dan mempercepat pencarian dan pengambilan data.

Implementasi Hash Table didasarkan pada fungsi hash, yang mengubah key menjadi indeks dalam array. Pada implementasi yang baik, fungsi hash harus menghasilkan indeks yang unik untuk setiap key.

Notes

  • Sebuah hash function digunakan untuk mengubah key menjadi indeks dalam array yang digunakan untuk menyimpan value.
  • Hash function harus memberikan hasil yang unik untuk setiap key yang berbeda.
  • Hash table dapat digunakan untuk mempercepat pencarian data, karena data dapat diakses dengan cepat berdasarkan key yang diberikan.
  • Beberapa cara untuk menangani tabrakan dalam hash table adalah dengan separate chaining, linear probing, dan quadratic probing.

Ilustrasi

Berikut adalah visualisasi sebuah hash table dengan size 4,

hash table visualization

Kita menggunakan hashing function f(x) = x % 4 (SIZE), maka value 21 menjadi index 1, value 23 menjadi 3

hash table visualization

Dengan implementasi separate chaining, maka value baru 41 dengan key yang sama di index 1, menjadi di sebelah 21

hash table visualization

Dengan implementasi linear probing, maka value baru 41 dengan key yang sama di index 1 menjadi di tempat selanjutnya yaitu index 2

hash table visualization

Kita bisa melihat bahwa dengan implementasi linear probing, ada kemungkinan value baru tidak dapat ditampung lagi, karena berbeda dari separate chaining yang tidak memakai space array namun dirantai di sebelah value sebelumnya.

Linear probing akan membuat size array dikali 2 di implementasi library ketika sudah full, namun pada implementasi kita dibawah hanya akan mengatakan bahwa array sudah full.

Implementasi


Separate Chaining

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

#define MAX_SIZE 10 // Ukuran array untuk hash table

// Struktur node untuk linked list pada setiap elemen array hash table
typedef struct node {
    char* key;
    int value;
    struct node* next;
} node;

// Fungsi hash untuk menghasilkan indeks dari kunci yang diberikan
int hash(char* key) {
    int sum = 0;
    for (int i = 0; i < strlen(key); i++) {
        sum += (int) key[i];
    }
    return sum % MAX_SIZE;
}

// Fungsi untuk membuat node baru
node* create_node(char* key, int value) {
    node* new_node = malloc(sizeof(node));
    new_node->key = key;
    new_node->value = value;
    new_node->next = NULL;
    return new_node;
}

// Fungsi untuk memasukkan data ke dalam hash table
void insert(node** hash_table, char* key, int value) {
    int index = hash(key);
    node* new_node = create_node(key, value);
    if (hash_table[index] == NULL) {
        hash_table[index] = new_node;
    } else {
        node* current_node = hash_table[index];
        while (current_node->next != NULL) {
            current_node = current_node->next;
        }
        current_node->next = new_node;
    }
}

// Fungsi untuk mencari nilai dari kunci yang diberikan
int search(node** hash_table, char* key) {
    int index = hash(key);
    node* current_node = hash_table[index];
    while (current_node != NULL) {
        if (strcmp(current_node->key, key) == 0) {
            return current_node->value;
        }
        current_node = current_node->next;
    }
    return -1; // Nilai kunci tidak ditemukan
}

// Fungsi untuk menampilkan seluruh data dalam hash table
void display(node** hash_table) {
    for (int i = 0; i < MAX_SIZE; i++) {
        printf("[%d]: ", i);
        node* current_node = hash_table[i];
        while (current_node != NULL) {
            printf("(%s, %d) ", current_node->key, current_node->value);
            current_node = current_node->next;
        }
        printf("\n");
    }
}

int main() {
    node* hash_table[MAX_SIZE] = { NULL }; // Inisialisasi hash table dengan NULL

    // Memasukkan data ke dalam hash table
    insert(hash_table, "apple", 5);
    insert(hash_table, "banana", 2);
    insert(hash_table, "cherry", 9);
    insert(hash_table, "durian", 7);

    // Menampilkan data dalam hash table
    printf("Hash table:\n");
    display(hash_table);

    // Mencari nilai dari kunci yang diberikan
    printf("\n");
    printf("Value of 'apple': %d\n", search(hash_table, "apple"));
    printf("Value of 'banana': %d\n", search(hash_table, "banana"));
    printf("Value of 'cherry': %d\n", search(hash_table, "cherry"));
    printf("Value of 'durian': %d\n", search(hash_table, "durian"));
}

Output

Hash table:
[0]: (apple, 5)
[1]:
[2]:
[3]: (cherry, 9) (durian, 7)
[4]:
[5]:
[6]:
[7]:
[8]:
[9]: (banana, 2)
Value of 'apple': 5
Value of 'banana': 2
Value of 'cherry': 9
Value of 'durian': 7

Linear Probing

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

#define MAX_SIZE 10 // Ukuran array untuk hash table

// Struktur untuk setiap elemen dalam hash table
typedef struct {
    char* key;
    int value;
} element;

// Struktur untuk hash table
typedef struct {
    element table[MAX_SIZE];
} hash_table;

// Fungsi hash untuk menghasilkan indeks dari kunci yang diberikan
int hash(char* key) {
    int sum = 0;
    for (int i = 0; i < strlen(key); i++) {
        sum += (int) key[i];
    }
    return sum % MAX_SIZE;
}

// Fungsi untuk memasukkan data ke dalam hash table
void insert(hash_table* ht, char* key, int value) {
    int index = hash(key);
    int count = 0; // Menghitung jumlah iterasi yang dilakukan
    while (ht->table[index].key != NULL && strcmp(ht->table[index].key, key) != 0) {
        index = (index + 1) % MAX_SIZE; // Linier probing
        count++;
        if (count == MAX_SIZE) {
            printf("Hash table is full\n");
            return;
        }
    }
    ht->table[index].key = key;
    ht->table[index].value = value;
}

// Fungsi untuk mencari nilai dari kunci yang diberikan
int search(hash_table* ht, char* key) {
    int index = hash(key);
    int count = 0; // Menghitung jumlah iterasi yang dilakukan
    while (ht->table[index].key != NULL && strcmp(ht->table[index].key, key) != 0) {
        index = (index + 1) % MAX_SIZE; // Linier probing
        count++;
        if (count == MAX_SIZE) {
            return -1; // Nilai kunci tidak ditemukan
        }
    }
    if (ht->table[index].key == NULL) {
        return -1; // Nilai kunci tidak ditemukan
    } else {
        return ht->table[index].value;
    }
}

// Fungsi untuk menampilkan seluruh data dalam hash table
void display(hash_table* ht) {
    for (int i = 0; i < MAX_SIZE; i++) {
        printf("[%d]: ", i);
        if (ht->table[i].key == NULL) {
            printf("NULL\n");
        } else {
            printf("(%s, %d)\n", ht->table[i].key, ht->table[i].value);
        }
    }
}

int main() {
    hash_table ht = { 0 }; // Inisialisasi hash table dengan NULL

    // Memasukkan data ke dalam hash table
    insert(&ht, "apple", 5);
    insert(&ht, "banana", 2);
    insert(&ht, "cherry", 9);
    insert(&ht, "durian", 7);
    insert(&ht, "elderberry", 3);

    // Menampilkan data dalam hash table
    printf("Hash table:\n");
    display(&ht);

    // Mencari nilai dari kunci yang diberikan
    printf("\n");
    printf("Value of 'apple': %d\n", search(&ht, "apple"));
    printf("Value of 'banana': %d\n", search(&ht, "banana"));
}

Output

Hash table:
[0]: (apple, 5)
[1]: NULL
[2]: (elderberry, 3)
[3]: (cherry, 9)
[4]: (durian, 7)
[5]: NULL
[6]: NULL
[7]: NULL
[8]: NULL
[9]: (banana, 2)
Value of 'apple': 5
Value of 'banana': 2

ON THIS PAGE

Apa itu Hash Table?NotesIlustrasiImplementasiSeparate ChainingLinear Probing