Hash Search Algorithm (Linear Probing)
Introduction
Hash search is an efficient data lookup method that maps keys to index positions in a hash table via a hash function, enabling fast retrieval of target data. This article introduces a hash search algorithm based on open addressing (linear probing), along with detailed C implementation code and comments.
Overview of the Hash Search Algorithm
The hash search algorithm primarily performs data insertion, lookup, and deletion through the following steps:
- Hash Function: Maps a key to an index position in the hash table.
- Collision Handling: When two keys are mapped to the same index by the hash function, a mechanism is needed to resolve the collision.
- Lookup Operation: Computes the index from the key using the hash function and locates the target position according to the collision handling mechanism.
- Deletion Operation: Marks or removes a specified key-value pair from the hash table.
Open Addressing (Linear Probing)
Open addressing is a method for resolving hash collisions. Its simplest form is linear probing. The basic idea is: when a hash collision occurs, probe the next available position in a linear fashion (one position at a time) until an empty slot is found or the starting position is revisited.
Linear Probing Steps
- Compute the Initial Index: Use the hash function to compute the initial index position for the key.
- Check for Collision: If the current position is already occupied, check the next position in sequence.
- Wrap-Around Check: If the end of the hash table is reached, start checking from the beginning, continuing until an empty slot is found or the starting position is revisited.
Code Implementation
Header Files and Macro Definitions
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10 // Define hash table size
Structure Definition
typedef struct {
int key;
int value;
} HashItem;
// Define hash table as pointer array
HashItem* hashTable[TABLE_SIZE];
Hash Function
int hashFunction(int key) {
return key % TABLE_SIZE;
}
Insertion Function
void insert(int key, int value) {
int index = hashFunction(key); // Compute hash value
int originalIndex = index; // Save initial index
// Create new hash table item
HashItem* newItem = (HashItem*) malloc(sizeof(HashItem));
newItem->key = key;
newItem->value = value;
// Handle collision using linear probing
while (hashTable[index] != NULL && hashTable[index]->key != -1) {
index = (index + 1) % TABLE_SIZE; // Move to next position
if (index == originalIndex) { // Check if returned to initial position
printf("Hash table is full\n");
return; // Hash table is full
}
}
// Insert new item into hash table
hashTable[index] = newItem;
}
Search Function
int search(int key) {
int index = hashFunction(key); // Compute hash value
int originalIndex = index; // Save initial index
// Search for key using linear probing
while (hashTable[index] != NULL) {
if (hashTable[index]->key == key) {
return hashTable[index]->value; // Key found, return value
}
index = (index + 1) % TABLE_SIZE; // Move to next position
if (index == originalIndex) {
return -1; // Not found
}
}
return -1; // Not found
}
Deletion Function
void delete(int key) {
int index = hashFunction(key); // Compute hash value
int originalIndex = index; // Save initial index
// Search for key to delete using linear probing
while (hashTable[index] != NULL) {
if (hashTable[index]->key == key) {
hashTable[index]->key = -1; // Mark this position as deleted
return;
}
index = (index + 1) % TABLE_SIZE; // Move to next position
if (index == originalIndex) {
return; // Not found
}
}
}
Main Function
int main() {
// Initialize hash table to empty
for (int i = 0; i < TABLE_SIZE; i++) {
hashTable[i] = NULL;
}
// Insert key-value pairs
insert(1, 10);
insert(11, 20);
insert(21, 30);
// Search and print values
printf("Value for key 1: %d\n", search(1));
printf("Value for key 11: %d\n", search(11));
printf("Value for key 21: %d\n", search(21));
// Delete key-value pair
delete(11);
printf("Value for key 11 after deletion: %d\n", search(11));
return 0;
}
Detailed Comments
Hash Table Item Structure
- Defining the
HashItemstruct: Contains two integers representing the key and its corresponding value.
Hash Table Definition
- Defining the
hashTablepointer array: Sized atTABLE_SIZE, used to store hash table items.
Hash Function
- Using the modulo operation: Maps a key to an index position in the hash table.
Insertion Function
- Computing the hash value: Calculates the index from the key.
- Creating a new hash table item: Allocates memory for the newly inserted key-value pair.
- Handling collisions: Uses linear probing to find the next available position.
- Inserting into the hash table: Places the new item in the found empty slot.
Search Function
- Computing the hash value: Calculates the index from the key.
- Linear probing search: Checks index positions one by one until the target key is found or the starting position is revisited.
- Returning the result: Returns the corresponding value if found; returns -1 if not found.
Deletion Function
- Computing the hash value: Calculates the index from the key.
- Linear probing search: Checks index positions one by one, marking the target key as deleted once found.
Main Function
- Initializing the hash table: Sets all positions to empty.
- Inserting key-value pairs: Calls the
insertfunction to insert multiple key-value pairs. - Searching and printing values: Calls the
searchfunction to look up and print values for specified keys. - Deleting key-value pairs: Calls the
deletefunction to remove key-value pairs and verifies the deletion.
Running Example
Compile and run the above code; the output is as follows:
Value for key 1: 10
Value for key 11: 20
Value for key 21: 30
Value for key 11 after deletion: -1
Complete Code
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10 // Define hash table size
// Define hash table item structure
typedef struct {
int key;
int value;
} HashItem;
// Define hash table as pointer array
HashItem* hashTable[TABLE_SIZE];
// Hash function using modulo operation
int hashFunction(int key) {
return key % TABLE_SIZE;
}
// Insert function
void insert(int key, int value) {
int index = hashFunction(key); // Compute hash value
int originalIndex = index; // Save initial index
// Create new hash table item
HashItem* newItem = (HashItem*) malloc(sizeof(HashItem));
newItem->key = key;
newItem->value = value;
// Handle collision using linear probing
while (hashTable[index] != NULL && hashTable[index]->key != -1) {
index = (index + 1) % TABLE_SIZE; // Move to next position
if (index == originalIndex) { // Check if returned to initial position
printf("Hash table is full\n");
return; // Hash table is full
}
}
// Insert new item into hash table
hashTable[index] = newItem;
}
// Search function
int search(int key) {
int index = hashFunction(key); // Compute hash value
int originalIndex = index; // Save initial index
// Search for key using linear probing
while (hashTable[index] != NULL) {
if (hashTable[index]->key == key) {
return hashTable[index]->value; // Key found, return value
}
index = (index + 1) % TABLE_SIZE; // Move to next position
if (index == originalIndex) {
return -1; // Not found
}
}
return -1; // Not found
}
// Delete function
void delete(int key) {
int index = hashFunction(key); // Compute hash value
int originalIndex = index; // Save initial index
// Search for key to delete using linear probing
while (hashTable[index] != NULL) {
if (hashTable[index]->key == key) {
hashTable[index]->key = -1; // Mark this position as deleted
return;
}
index = (index + 1) % TABLE_SIZE; // Move to next position
if (index == originalIndex) {
return; // Not found
}
}
}
int main() {
// Initialize hash table to empty
for (int i = 0; i < TABLE_SIZE; i++) {
hashTable[i] = NULL;
}
// Insert key-value pairs
insert(1, 10);
insert(11, 20);
insert(21, 30);
// Search and print values
printf("Value for key 1: %d\n", search(1));
printf("Value for key 11: %d\n", search(11));
printf("Value for key 21: %d\n", search(21));
// Delete key-value pair
delete(11);
printf("Value for key 11 after deletion: %d\n", search(11));
return 0;
}
Code Explanation:
- Hash Function: Uses the modulo operation
key % TABLE_SIZEto compute the hash value. - Insertion Function: If a collision occurs, uses linear probing, i.e., checks the next position one by one until an empty slot is found.
- Search Function: Uses linear probing to find the value corresponding to the target key.
- Deletion Function: Marks the target key as
-1, indicating that the position has been deleted.
This code demonstrates how to implement a simple hash table using the open addressing method, without using linked lists to handle collisions.