What is Hashing?
Hashing is a technique to convert data (like a string, number, etc.) into a small fixed-size value called a hash code using a mathematical function called a hash function.
✅ Purpose:
What is a Hash Table?
A Hash Table is a data structure that stores data in an array-like format using the hash code as an index.
Key → Hash Function → Index → Store value at that index
If two keys generate the same index, we resolve it using methods like chaining (linked list at that index) or open addressing (find next empty spot).
How to Implement a Simple Hash Table?
Steps:
Choose a hash function (e.g., key % size).
Create an array of fixed size.
Insert, search, and delete elements based on the hash value.
Algorithms for Hash Table
Hash Table with Open Addressing (without Linked List)
Idea:
If a collision occurs, find the next empty slot in the table by probing.
Common Probing Methods:
-
Linear Probing: Try next index (index + 1) % SIZE
-
Quadratic Probing: Try (index + i*i) % SIZE
-
Double Hashing: Use a second hash function
🔹 Insertion Algorithm (Open Addressing - Linear Probing)
1. Compute index = hash(key)
2. If slot at index is empty, insert key-value
3. Else: a. Move to next index (index + 1) % SIZE b. Repeat step 2
4. If no empty slot found, table is full
🔹 Search Algorithm (Open Addressing - Linear Probing)
1. Compute index = hash(key) 2. If slot at index has key, return value
3. Else: a. Move to next index (index + 1) % SIZE b. Repeat step 2
4. If empty slot found during search, key not present
🔹 Deletion Algorithm (Open Addressing)
1. Search the key using above search procedure 2. If key found, mark slot as "deleted" (special marker)
3. During insertion/search, treat "deleted" slot as occupied
C Program Hash Table with Linear Probing
#include <stdio.h>
#include <stdlib.h>
#define SIZE 11
int hashTable[SIZE];
int flag[SIZE]; // 0 for empty, 1 for occupied, -1 for deleted
// Hash function
int hash(int key) {
return key % SIZE;
}
// Insert a key
void insert(int key) {
int index = hash(key);
int startIndex = index;
while (flag[index] == 1) {
index = (index + 1) % SIZE;
if (index == startIndex) {
printf("Hash Table is Full\n");
return;
}
}
hashTable[index] = key;
flag[index] = 1;
printf("Inserted key %d at index %d\n", key, index);
}
// Search a key
void search(int key) {
int index = hash(key);
int startIndex = index;
while (flag[index] != 0) {
if (flag[index] == 1 && hashTable[index] == key) {
printf("Key %d found at index %d\n", key, index);
return;
}
index = (index + 1) % SIZE;
if (index == startIndex) {
break;
}
}
printf("Key %d not found\n", key);
}
// Delete a key
void delete(int key) {
int index = hash(key);
int startIndex = index;
while (flag[index] != 0) {
if (flag[index] == 1 && hashTable[index] == key) {
flag[index] = -1; // Mark as deleted
printf("Key %d deleted from index %d\n", key, index);
return;
}
index = (index + 1) % SIZE;
if (index == startIndex) {
break;
}
}
printf("Key %d not found to delete\n", key);
}
// Display hash table
void display() {
printf("\nHash Table:\n");
for (int i = 0; i < SIZE; i++) {
if (flag[i] == 1)
printf("Index %d: %d\n", i, hashTable[i]);
else if (flag[i] == -1)
printf("Index %d: Deleted\n", i);
else
printf("Index %d: Empty\n", i);
}
}
int main() {
for (int i = 0; i < SIZE; i++) {
flag[i] = 0; // Initialize all slots as empty
}
int choice, key;
do {
printf("\nMenu\n1. Insert\n2. Search\n3. Delete\n4. Display\n5. Exit\nEnter choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter key to insert: ");
scanf("%d", &key);
insert(key);
break;
case 2:
printf("Enter key to search: ");
scanf("%d", &key);
search(key);
break;
case 3:
printf("Enter key to delete: ");
scanf("%d", &key);
delete(key);
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf("Invalid choice\n");
}
} while (1);
return 0;
}
Comments
Post a Comment