fbpx

Struktur Data : Contoh Program Hashing dalam Bahasa C

Contoh 1

Program hash table denan ketentuan ketika data pada baris/indeks yang dihapus (flag = 2) tidak dapat diisi lagi.

#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;
        }
    }
    
    if(array[i].flag == 2)
    {
        printf("\nMemory has been used, cannot insert data!");
    }
    else
    {
        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;
}


Contoh 2

Program Hash Tabel tanpa pointer dan collison resolution dengan menggunakan quadratic probing

Misalkan akan diinputkan key seperti beriku

Table Size 11 (0..10)

Hash Function: \(h(x)=z \bmod 11\)

Insert Key: 20, 30, 2, 13, 25, 24, 10, 9

Maka hasil yang diharapkan adalah

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

struct hashtable_item
{
    int key[10001];
    int value[10001];
    int flag[10001];
};

struct hashtable_item thehash;
int max;

void init_array()
{
    for(int i = 0; i < max; i++)
    {
        thehash.flag[i] = 0;
        thehash.key[i] = -1;
        thehash.value[i] = -1;
    }
}

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;

    int quad = 1;
    while(thehash.flag[i] == 1)
    {
        if(thehash.key[i] == key)
        {
            printf("\nKey already exist, hence updating its value\n");
            thehash.value[i] = value;
            return;
        }
        
        i = (hashCode(key) + quad*quad) % max;
        quad++;
        if(i == index)
        {
            printf("\nHash table is full, cannot insert any more item\n");
            return;
        }
    }
    
    if(thehash.flag[i] == 2)
    {
        printf("\nMemory has been used, cannot insert data!");
    }
    else
    {
        thehash.flag[i] = 1;
        thehash.key[i] = key;
        thehash.value[i] = value;
        size++;
        printf("\nKey %d has been inserted\n", value);
    }
}

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

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

void display()
{
    for(int i = 0; i < max; i++)
    {
        if(thehash.value[i] == -1)
        {
            printf("\nArray[%d] has no elements \n", i);
        }
        else
        {
            printf("\nArray[%d] has elements -: \n %d(key) and %d(value) \n", i, thehash.key[i], thehash.value[i]);
        }
    }
}

int main()
{
    int choice, key, value, n, c;
    printf("\nMasukkan ukuran memori yang ingin digunakan : ");
    scanf("%d", &max);
    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;
}

Output yang dihasilkan sesuai dengan yang diharapkan


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Heap dan Hash, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up