📋 Daftar Isi
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.
