Struktur Data : Implementasi Hash dalam Bahasa C

📋 Daftar Isi

Insert

Untuk menambahkan data baru, key perlu dikonversi menjadi index array hash table menggunakan salah satu fungsi hash.

Contoh:

Fungsi untuk memetakan NIP Pegawai/key adalah hash(key) = key mod 701 NIP Pegawai 580625685 🡪 maka hash(580625685) = 580625685 mod 701 = 3 (Jika terjadi collision, maka bisa diimplementasikan collision resolution)
Tambahkan data baru (nama, tanggal lahir, alamat, dll) pada array hash table index ke-3

//fungsi insert dengan berbagai kemungkinan
void insert(int key, int value)
{
    int index = hashcode(key);
    int i = index;

    //membuat item baru untuk insert ke tabel hash arrat
    struct item* new_item = (struct item*)malloc(sizeof(struct item));
    new_item->key = key;
    new_item->value = value;

    //linear probing untuk mencari space kosong pada indeks array
    while (array[i].flag == 1)
    {
        if (array[i].data->key == key)
        {
            //kasus dimana terdapat key yang sama dengan yang diberikan
            printf("\n Key telah ada, update nilai\n");
            array[i].data->value = value;
            return;
        }

        i = (i + 1) % max; //maju satu langkah
        if (i == index) //jika sudah mengecek satu-satu indeks sampai balik lagi ke index penug
        {
            printf("\n Hash table telah penuh, tidak dapat menambahkan item lagi\n");
            return;
        }
    }

    array[i].flag = 1;
    array[i].data = new_item;
    size++;
    printf("\n Key (%d) telah di insert \n", key);
}

Search

Hitung nilai hash value/index array menggunakan fugsi hash yang digunakan untuk operasi insert (termasuk juga implementasi collision resolution-nya). Baca nilai array pada index tersebut.

Delete

Data dapat dihapus dari hash table
Tetapi index array/lokasi yang dihapus datanya tidak boleh dibiarkan sebagai lokasi yang kosong karena akan mempengaruhi hasil proses search
Index array/lokasi tersebut harus ditandai bahwa lokasi tersebut sebelumnya ada isinya. Karena jika kita biarkan dia kosong setelah penghapusan, jika kita mau search suatu elemen A, akan mengubah proses atau alur awal ketika kita insert elemen A

void remove_element(int key)
{
    int index = hashCode(key);
    int i = index;

    while(array[i].flag != 0)
    {
        if(array[i].flag == 1 && array[i].data->key == key)
        {
            array[i].flag = 2;
            array[i].data = NULL;
            size--;
            printf("\nKey %d has been removed\n", key);
            return;
        }
        i = (i + 1) % max;
        if(i == index)
        {
            break;
        }
    }
    printf("\nThis key does not exist\n");
}

Source Code Lengkap

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

struct item
{
    int key;
    int value;
};

struct hashtable_item
{
    int flag;
    struct item *data;
};

struct hashtable_item *array;
int max;

void init_array()
{
    for(int i = 0; i < max; i++)
    {
        array[i].flag = 0;
        array[i].data = NULL;
    }
}

int hashCode(int key)
{
    return (key % max);
}

int size = 0;

int sizeOfHashtable()
{
    return size;
}

void insert(int key, int value)
{
    printf("\n");
    int index = hashCode(key);
    int i = index;

    struct item *new_item = (struct item*)malloc(sizeof(struct item));
    new_item->key = key;
    new_item->value = value;

    while(array[i].flag == 1)
    {
        if(array[i].data->key == key)
        {
            printf("\nKey already exist, hence updating its value\n");
            array[i].data->value = value;
            return;
        }

        i = (i + 1) % max;
        if(i == index)
        {
            printf("\nHash table is full, cannot insert any more item\n");
            return;
        }
    }

    array[i].flag = 1;
    array[i].data = new_item;
    size++;
    printf("\nKey %d has been inserted\n", value);
}

void remove_element(int key)
{
    int index = hashCode(key);
    int i = index;

    while(array[i].flag != 0)
    {
        if(array[i].flag == 1 && array[i].data->key == key)
        {
            array[i].flag = 2;
            array[i].data = NULL;
            size--;
            printf("\nKey %d has been removed\n", key);
            return;
        }
        i = (i + 1) % max;
        if(i == index)
        {
            break;
        }
    }
    printf("\nThis key does not exist\n");
}

void display()
{
    for(int i = 0; i < max; i++)
    {
        struct item *current = (struct item*)array[i].data;
        if(current == NULL)
        {
            printf("\nArray[%d] has no elements \n", i);
        }
        else
        {
            printf("\nArray[%d] has elements -: \n %d(key) and %d(value) ", i, current->key, current->value);
        }
    }
}

int main()
{
    int choice, key, value, n, c;
    printf("\nMasukkan ukuran memori yang ingin digunakan : ");
    scanf("%d", &max);
    array = (struct hashtable_item*)malloc(max * sizeof(struct hashtable_item));
    init_array();

    do
    {
        printf("Implementation of Hash Table in C with Linear Probing\n\n");
        printf("MENU :- \n1.Inserting item in the Hashtable \n2.Removing item from the Hashtable \n3.Check the size of Hashtable \n4.Display Hashtable\n\nPlease enter your choice-: ");
        scanf("%d", &choice);

        switch(choice)
        {
        printf(" ");
        case 1:
            printf("Inserting element in hashtable\n");
            printf("Enter key-:\t");
            scanf("%d", &key);
            printf("Enter value-:\t");
            scanf("%d", &value);
            insert(key,value);
            break;
        
        case 2:
            printf("Deleting in hashtable \n Enter the key to delete-:");
            scanf("%d", &key);
            remove_element(key);
            break;
        
        case 3:
            n = sizeOfHashtable();
            printf("Size of hashtable is-:%d\n", n);
            break;

        case 4:
            display();
            break;

        default:
            printf("Wrong Input\n");
            break;
        }

        printf("\n Do you want to continue-: (press 1 for yes)\t");
        scanf("%d", &c);
    } while (c == 1);
    getchar();
    return 0;
}