Hashing using linear probing :
Algorithm to insert a value in linear probing
Hashtable is an array of size = TABLE_SIZE
Step 1: Read the value to be inserted, key
Step 2: let i = 0
Step 3: hkey = key% TABLE_SIZE
Step 4 :compute the index at which the key has to be inserted in hash table
index = (hkey + i) % TABLE_SIZE
Step 5: if there is no element at that index then insert the value at index and STOP
Step 6: If there is already an element at that index
step 4.1: i = i+1
step 7: if i < TABLE_SIZE then go to step 4
Algorithm to search a value in linear probing
Hashtable is an array of size = TABLE_SIZE
Step 1: Read the value to be searched, key
Step 2: let i = 0
Step 3: hkey = key% TABLE_SIZE
Step 4: compute the index at which the key can be found
index = (hkey+ i) % TABLE_SIZE
Step 5: if the element at that index is same as the search value then print element
found and STOP
Step 6: else
step 4.1: i = i+1
step 7: if i < TABLE_SIZE then go to step 4
Program:
#include <stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10
int h[TABLE_SIZE]={NULL};
void insert()
{
int key,index,i,flag=0,hkey;
printf("\nenter a value to insert into hash table\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE;i++)
{
index=(hkey+i)%TABLE_SIZE;
if(h[index] == NULL)
{
h[index]=key;
break;
}
if(i == TABLE_SIZE)
printf("\nelement cannot be inserted\n");
}
void search()
{
int key,index,i,flag=0,hkey;
printf("\nenter search element\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE; i++)
{
index=(hkey+i)%TABLE_SIZE;
if(h[index]==key)
{
printf("value is found at index %d",index);
break;
}
}
if(i == TABLE_SIZE)
printf("\n value is not found\n");
}
void display()
{
int i;
printf("\nelements in the hash table are \n");
for(i=0;i< TABLE_SIZE; i++)
printf("\nat index %d \t value = %d",i,h[i]);
}
main()
{
int opt,i;
while(1)
{
printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
scanf("%d",&opt);
switch(opt)
{
case 1:
insert();
break;
case 2:
display();
break;
case 3:
search();
break;
case 4:exit(0);
}
}
}
Output
Press 1. Insert 2. Display 3. Search 4.Exit
1
enter a value to insert into hash table
12
Press 1. Insert 2. Display 3. Search 4.Exit
1
enter a value to insert into hash table
13
Press 1. Insert 2. Display 3. Search 4.Exit
1
enter a value to insert into hash table
22
Press 1. Insert 2. Display 3. Search 4.Exit
2
elements in the hash table are
at index 0 value = 0
at index 1 value = 0
at index 2 value = 12
at index 3 value = 13
at index 4 value = 22
at index 5 value = 0
at index 6 value = 0
at index 7 value = 0
at index 8 value = 0
at index 9 value = 0
Press 1. Insert 2. Display 3. Search 4.Exit
3
enter search element
12
value is found at index 2
Press 1. Insert 2. Display 3. Search 4.Exit
23
enter search element
23
value is not found
Press 1. Insert 2. Display 3. Search 4.Exit
4
Quadratic Probing:
Algorithm to insert a value in quadratic probing
Hashtable is an array of size = TABLE_SIZE
Step 1: Read the value to be inserted, key
Step 2: let i = 0
Step 3: hkey=key%TABLE_SIZE
Step 4: compute the index at which the value has to be inserted in hash table
index = (hkey+ i * i) % TABLE_SIZE
Step 5: if there is no element at that index then insert the value at index and STOP
Step 6: If there is already an element at that index
step 4.1: i = i+1
step 7: if i < TABLE_SIZE then go to step 4
Algorithm to search a value in quadratic probing
Hashtable is an array of size = TABLE_SIZE
Step 1: Read the value to be searched, key
Step 2: let i = 0
Step 3: hkey=key%TABLE_SIZE
Step 4: compute the index at which the value can be found
index = (hkey + i * i) % TABLE_SIZE
Step 5: if the element at that index is same as the search value then print element
found and STOP
Step 6: else
step 4.1: i = i+1
step 7: if i < TABLE_SIZE then go to step 4
#include <stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10
int h[TABLE_SIZE]={NULL};
void insert()
{
int key,index,i,flag=0,hkey;
printf("\nenter a value to insert into hash table\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE;i++)
{
index=(hkey+i*i)%TABLE_SIZE;
if(h[index] == NULL)
{
h[index]=key;
break;
}
}
if(i == TABLE_SIZE)
printf("\nelement cannot be inserted\n");
}
void search()
{
int key,index,i,flag=0,hkey;
printf("\nenter search element\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE; i++)
{
index=(hkey+i*i)%TABLE_SIZE;
if(h[index]==key)
{
printf("value is found at index %d",index);
break;
}
}
if(i == TABLE_SIZE)
printf("\n value is not found\n");
}
void display()
{
int i;
printf("\nelements in the hash table are \n");
for(i=0;i< TABLE_SIZE; i++)
printf("\nat index %d \t value = %d",i,h[i]);
}
main()
{
int opt,i;
while(1)
{
printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
scanf("%d",&opt);
switch(opt)
{
case 1:
insert();
break;
case 2:
display();
break;
case 3:
search();
break;
case 4:exit(0);
}
}
}
Output:
Press 1. Insert 2. Display 3. Search 4.Exit
1
enter a value to insert into hash table
12
Press 1. Insert 2. Display 3. Search 4.Exit
1
enter a value to insert into hash table
22
Press 1. Insert 2. Display 3. Search 4.Exit
1
enter a value to insert into hash table
32
Press 1. Insert 2. Display 3. Search 4.Exit
2
elements in the hash table are
at index 0 value = 0
at index 1 value = 0
at index 2 value = 12
at index 3 value = 22
at index 4 value = 0
at index 5 value = 0
at index 6 value = 32
at index 7 value = 0
at index 8 value = 0
at index 9 value = 0
Press 1. Insert 2. Display 3. Search 4.Exit
3
enter search element
22
value is found at index 3
Press 1. Insert 2. Display 3. Search 4.Exit
3
enter search element
123
value is not found
Press 1. Insert 2. Display 3. Search 4.Exit
4
Hash table implementation in c using arrays
#include<stdio.h>
#define size 7
int arr[size];
void init()
{
int i;
for(i = 0; i < size; i++)
arr[i] = -1;
}
void insert(int value)
{
int key = value % size;
if(arr[key] == -1)
{
arr[key] = value;
printf("%d inserted at arr[%d]\n", value,key);
}
else
{
printf("Collision : arr[%d] has element %d already!\n",key,arr[key]);
printf("Unable to insert %d\n",value);
}
}
void del(int value)
{
int key = value % size;
if(arr[key] == value)
arr[key] = -1;
else
printf("%d not present in the hash table\n",value);
}
void search(int value)
{
int key = value % size;
if(arr[key] == value)
printf("Search Found\n");
else
printf("Search Not Found\n");
}
void print()
{
int i;
for(i = 0; i < size; i++)
printf("arr[%d] = %d\n",i,arr[i]);
}
int main()
{
init();
insert(10); //key = 10 % 7 ==> 3
insert(4); //key = 4 % 7 ==> 4
insert(2); //key = 2 % 7 ==> 2
insert(3); //key = 3 % 7 ==> 3 (collision)
printf("Hash table\n");
print();
printf("\n");
printf("Deleting value 10..\n");
del(10);
printf("After the deletion hash table\n");
print();
printf("\n");
printf("Deleting value 5..\n");
del(5);
printf("After the deletion hash table\n");
print();
printf("\n");
printf("Searching value 4..\n");
search(4);
printf("Searching value 10..\n");
search(10);
return 0;
}
