- Linear Probing resolves hash collision(same hash value for two or more data).
- It allows user to get the free space by searching the hash table sequentially.
Example: hashIndex = key % tableSize (hash table size)
If the resultant hash index is already occupied by another data, we need to do linear probing to find a free space in hash table.
Example: hashIndex = (key + i) % tableSize where i = 0,1,2...
To delete an element from the hash table, we need to calculate the hash index from the given key.
hashIndex = key % tableSize
If the given key is not available at the resultant hash index, we need to probe forward until we encounter the given key or the value '0' for marker.
If the marker of any bucket is 0, then the given data is not present in the hash table. If we encounter the given key in the hash table, then delete it and set the marker value to -1.
What is the purpose of marker in linear probing?
Just for example, try to insert the keys 21, 32 and 31 into the hash table.
hashIndex = key % tableSize(5)
hashIndex for 21 = 21 % 5 = 1
hashIndex for 32 = 32 % 5 = 2
hashIndex for 31 = 31 % 5 = 1
We are getting collision for data 31 because index 1 is already occupied by 21. So, we need to check the next available location by doing linear probing.
Check for next available location(for key 31)
hashIndex = (key + i) % 5 where i=0,1,2,...
hashIndex for 31 = (31 + 1) % 5 = 2
Hash index 2 is also occupied already. So, we need to check for the next available location.
hashIndex for 31 = (31+2) % 5 = 3.
Hash index 3 is not occupied. So, we can insert key 31 in the third bucket.
Suppose if user deletes 32 and then he wants to delete 31. We will get hash index as 1 for the key 31. But, the bucket at hash index 1 holds the data 21. So, we will check the next bucket((31 +1) % 5 = 2nd bucket) and it would be empty. So, we might think that either the key 31 is not present or it's already gone. In order to avoid that, we will set the marker to -1 which indicates that the data we search might be present in the subsequent buckets.
See Also:
C Program To Implement Double Hashing
C Program To Implement Linear Probing
C Program To Implement Chain Hashing (Separate Chaining With Linked List)
C Program To Implement Linear Probing
C Program To Implement Chain Hashing (Separate Chaining With Linked List)
Example program for Linear Probing(in C):
#include <stdlib.h>
#include <string.h>
int tableSize = 0, totEle = 0;
struct node *hashTable = NULL;
struct node {
int age, key;
char name[100];
int marker;
};
void insertInHash(int key, char *name, int age) {
int hashIndex = key % tableSize;
if (tableSize == totEle) {
printf("Can't perform Insertion..Hash Table is full!!");
return;
}
while (hashTable[hashIndex].marker == 1) {
hashIndex = (hashIndex + 1)%tableSize;
}
hashTable[hashIndex].key = key;
hashTable[hashIndex].age = age;
strcpy(hashTable[hashIndex].name, name);
hashTable[hashIndex].marker = 1;
totEle++;
return;
}
void deleteFromHash(int key) {
int hashIndex = key % tableSize, count = 0, flag = 0;
if (totEle == 0) {
printf("Hash Table is Empty!!\n");
return;
}
while (hashTable[hashIndex].marker != 0 && count <= tableSize) {
if (hashTable[hashIndex].key == key) {
hashTable[hashIndex].key = 0;
/* set marker to -1 during deletion operation*/
hashTable[hashIndex].marker = -1;
hashTable[hashIndex].age = 0;
strcpy(hashTable[hashIndex].name, "\0");
totEle--;
flag = 1;
break;
}
hashIndex = (hashIndex + 1)%tableSize;
count++;
}
if (flag)
printf("Given data deleted from Hash Table\n");
else
printf("Given data is not available in Hash Table\n");
return;
}
void searchElement(int key) {
int hashIndex = key % tableSize, flag = 0, count = 0;
if (totEle == 0) {
printf("Hash Table is Empty!!");
return;
}
while (hashTable[hashIndex].marker != 0 && count <= tableSize) {
if (hashTable[hashIndex].key == key) {
printf("Voter ID : %d\n", hashTable[hashIndex].key);
printf("Name : %s\n", hashTable[hashIndex].name);
printf("Age : %d\n", hashTable[hashIndex].age);
flag = 1;
break;
}
hashIndex = (hashIndex + 1)%tableSize;
}
if (!flag)
printf("Given data is not present in hash table\n");
return;
}
void display() {
int i;
if (totEle == 0) {
printf("Hash Table is Empty!!\n");
return;
}
printf("Voter ID Name Age Index \n");
printf("-----------------------------------------\n");
for (i = 0; i < tableSize; i++) {
if (hashTable[i].marker == 1) {
printf("%-13d", hashTable[i].key);
printf("%-15s", hashTable[i].name);
printf("%-7d", hashTable[i].age);
printf("%d\n", i);
}
}
printf("\n");
return;
}
int main() {
int key, age, ch;
char name[100];
printf("Enter the no of elements:");
scanf("%d", &tableSize);
hashTable = (struct node *)calloc(tableSize, sizeof(struct node));
while (1) {
printf("1. Insertion\t2. Deletion\n");
printf("3. Searching\t4. Display\n");
printf("5. Exit\nEnter ur choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter the key value:");
scanf("%d", &key);
getchar();
printf("Name:");
fgets(name, 100, stdin);
name[strlen(name) - 1] = '\0';
printf("Age:");
scanf("%d", &age);
insertInHash(key, name, age);
break;
case 2:
printf("Enter the key value:");
scanf("%d", &key);
deleteFromHash(key);
break;
case 3:
printf("Enter the key value:");
scanf("%d", &key);
searchElement(key);
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf("U have entered wrong Option!!\n");
break;
}
}
return 0;
}
Output (Closed Hashing - Linear probing Example):
jp@jp-VirtualBox:~/cpgms/data_structures$ ./a.out
Enter the no of elements:3
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:1
Enter the key value:1
Name:Harry
Age:23
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:1
Enter the key value:2
Name:Ram
Age:24
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:1
Enter the key value:3
Name:Raj
Age:23
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:4
Voter ID Name Age Index
-----------------------------------------
3 Raj 23 0
1 Harry 23 1
2 Ram 24 2
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:2
Enter the key value:1
Given data deleted from Hash Table
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:4
Voter ID Name Age Index
-----------------------------------------
3 Raj 23 0
2 Ram 24 2
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:1
Enter the key value:10
Name:Ravi
Age:23
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:4
Voter ID Name Age Index
-----------------------------------------
3 Raj 23 0
10 Ravi 23 1
2 Ram 24 2
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:3
Enter the key value:10
Voter ID : 10
Name : Ravi
Age : 23
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:5
Enter the no of elements:3
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:1
Enter the key value:1
Name:Harry
Age:23
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:1
Enter the key value:2
Name:Ram
Age:24
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:1
Enter the key value:3
Name:Raj
Age:23
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:4
Voter ID Name Age Index
-----------------------------------------
3 Raj 23 0
1 Harry 23 1
2 Ram 24 2
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:2
Enter the key value:1
Given data deleted from Hash Table
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:4
Voter ID Name Age Index
-----------------------------------------
3 Raj 23 0
2 Ram 24 2
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:1
Enter the key value:10
Name:Ravi
Age:23
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:4
Voter ID Name Age Index
-----------------------------------------
3 Raj 23 0
10 Ravi 23 1
2 Ram 24 2
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:3
Enter the key value:10
Voter ID : 10
Name : Ravi
Age : 23
1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter ur choice:5
KY Faltu program banaya hai!!!!!!!!!!!!!
ReplyDeleteCoding chod doh tumlog!!!!
Kal se bhaaji bechna chalu karde!!