Hash Table with Linear Probing

Learn Theory - Linear probing

#include<stdio.h>
#include<stdlib.h>
 
/* to store a data (consisting of key and value) in hash table array */
struct item 
{
    int key;
    int value;
};
 
/* each hash table item has a flag (status) and data (consisting of key and value) */
struct hashtable_item 
{
     int flag;
    /*
     * flag = 0 : data does not exist
     * flag = 1 : data exists
     * flag = 2 : data existed at least once
    */
 
    struct item *data;
 
};
 

int size = 0;
int max = 10;
struct hashtable_item array[10];
/* initializing hash table array */
void init_array()
{
    int i;
    for (i = 0; i < max; i++) 
    {
array[i].flag = 0;
array[i].data = NULL;
    }
}
 
/* to every key, it will generate a corresponding index */
int hashcode(int key)
{
    return (key % max);
}
 
/* to insert an element in the hash table */
void insert(int key, int value)
{
    int index = hashcode(key);
    int i = index;
 
    /* creating new item to insert in the hash table array */
    struct item *new_item = (struct item*) malloc(sizeof(struct item));
    new_item->key = key;
    new_item->value = value;
 
    /* probing through the array until we reach an empty space */
    while (array[i].flag == 1) 
    {
 
if (array[i].data->key == key) 
        {
 
/* case where already existing key matches the given key */
printf("\n Key already exists, hence updating its value \n");
array[i].data->value = value;
return;
 
}
 
i = (i + 1) % max;
if (i == index) 
        {
printf("\n Hash table is full, cannot insert any more item \n");
return;
}
 
    }
 
    array[i].flag = 1;
    array[i].data = new_item;
    size++;
    printf("\n Key (%d) has been inserted \n", key);
 
} 
 
 
/* to remove an element from the hash table */
void remove_element(int key)
{
    int index = hashcode(key);
    int  i = index;
 
    /* probing through array until we reach an empty space where not even once an element had been present */
    while (array[i].flag != 0) 
    {
 
if (array[i].flag == 1  &&  array[i].data->key == key ) 
        {
 
// case when data key matches the given key
array[i].flag =  2;
array[i].data = NULL;
size--;
printf("\n Key (%d) has been removed \n", key);
return;
 
}
i = (i + 1) % max;
if (i == index)
        {
break;
    }
     }
     printf("\n This key does not exist \n");
 }
 
/* to display all the elements of hash table */
void display()
{
    int i;
    for (i = 0; i < max; i++)
    {
struct item *current = (struct item*) array[i].data;
 
if (current == NULL) 
        {
    printf("\n Array[%d] has no elements \n", i);
}
else
        {
    printf("\n Array[%d] has elements -: \n  %d (key) and %d(value) ", i, current->key, current->value);
}
    }
 
}
 
int size_of_hashtable()
{
    return size;
}
 
void main()
{
int choice, key, value, n;
init_array();
 
do {
printf("MENU-: \n1.Inserting item in the Hashtable" 
                              "\n2.Removing item from the Hashtable" 
                              "\n3.Check the size of Hashtable"
                              "\n4.Display Hashtable"
                              "\n5.Exit"
       "\n\n Please enter your choice-:");
 
scanf("%d", &choice);
 
switch(choice) 
                {
 
case 1:
 
      printf("Inserting element in Hashtable\n");
      printf("Enter key and value-:\t");
      scanf("%d%d", &key, &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 = size_of_hashtable();
      printf("Size of Hashtable is-:%d\n", n);
 
      break;
 
case 4:
 
      display();
 
      break;
            case 5:
 
      exit(0);
 
      break;
default:
 
       printf("Wrong Input\n");
 
}
 
}while(1);
 
}

Comments

Post a Comment

Popular posts from this blog

Data Structure Lab CSL 201 Manual KTU - Dr Binu V P-9847390760

 Dr Binu V P - About Me Data Structures CST 201 KTU Theory Notes  ( Learn Theory Before You Attempt Lab Exercise) SCHEME AND SYLLABUS 1. Polynomial Addition using Arrays 2. Sparse Matrix Representation and sum 3. Stack using Array 4. Queue using Array 5. Circular Queue using Arrays 6. Double Ended Queue  7. Priority Queue  8. Infix to postfix 9. Infix to prefix conversion 10. Prefix to infix conversion 11. Evaluation of postfix expression 12. Singly Linked List 13. Doubly Linked List   14. Stack using Linked List 15. Queue using Linked List 16. Polynomial Addition using Linked list 17. Polynomial Multiplication using Linked List 18. Binary Tree using arrays and traversals 19. Binary Tree using Linked List and Traversal 20. Binary Search Tree Implementation and Traversal 21.Sorting Algorithms       Bubble sort       Exchange sort       Selection Sort       Insertion Sort       Quick Sort ...
Read more

Singly Linked List Implementation

Singly Linked List /**************************************************************************/ #include<stdio.h> #include<stdlib.h> struct Node {  int data;  struct Node *next; }*head=NULL,*tail=NULL,*temp=NULL,*trav=NULL,*prev=NULL; void create() {  temp=(struct Node*)malloc(sizeof(struct Node));  printf("Enter data:");  scanf("%d",&temp->data);  temp->next=NULL;  if(head==NULL)  {   head=temp;   tail=temp;  }  else  {   tail->next=temp;   tail=temp;  } } void display() {  temp=head;  while(temp!=NULL)  {   printf(" %d---->",temp->data);   temp=temp->next;  }  printf(" NULL"); }  void insert_begin()  {      temp=(struct Node*)malloc(sizeof(struct Node));      printf("Enter data:");      scanf("%d",&temp->data);      temp->next=NULL;      if(head...
Read more

Binary search Tree Implementation and Traversal

Binary Search Tree and Operations /******* BST Tree and Operations **********/ #include <stdio.h> #include <stdlib.h>struct Node { int key; struct Node* left; struct Node* right; }; struct Node *root=NULL,*temp=NULL; struct Node* createNode(int key) {      struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));      newNode->key = key;      newNode->left = newNode->right = NULL;      return newNode; } struct Node* insert(struct Node* node, int key) { // Base case: if the tree is empty, create a new node if (node == NULL) {      return createNode(key);      } // Compare the key with the current node's key if (key < node->key) { // Recursively insert into the left subtree      node->left = insert(node->left, key);      } else if (key > node->key) { // Recursively insert into the right subtree    node->...
Read more