#include <stdio.h>
#include <stdlib.h>
// Define the structure for the nodes in the linked list
struct Node {
int data;
struct Node* next;
};
// Function to create a new node with given data
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a value into the hash table
void insert(struct Node* hashTable[], int key, int tableSize) {
int index = key % tableSize;
struct Node* newNode = createNode(key);
newNode->next = hashTable[index];
hashTable[index] = newNode;
}
// Function to search for a value in the hash table
int search(struct Node* hashTable[], int key, int tableSize) {
int index = key % tableSize;
struct Node* temp = hashTable[index];
while (temp) {
if (temp->data == key) {
return 1; // Key found
}
temp = temp->next;
}
return 0; // Key not found
}
// Function to delete a value from the hash table
void delete(struct Node* hashTable[], int key, int tableSize) {
int index = key % tableSize;
struct Node* temp = hashTable[index];
struct Node* prev = NULL;
// Traverse the linked list at that index
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// If the key is not present
if (temp == NULL) {
printf("Key %d not found.\n", key);
return;
}
// Key is present at the head of the linked list
if (prev == NULL) {
hashTable[index] = temp->next;
} else {
prev->next = temp->next;
}
free(temp);
printf("Key %d deleted.\n", key);
}
// Function to display the hash table
void display(struct Node* hashTable[], int tableSize) {
for (int i = 0; i < tableSize; i++) {
printf("HashTable[%d]: ", i);
struct Node* temp = hashTable[i];
while (temp) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
}
// Main function
int main() {
int tableSize = 10; // Define size of the hash table
struct Node* hashTable[tableSize];
// Initialize the hash table
for (int i = 0; i < tableSize; i++) {
hashTable[i] = NULL;
}
// Insert elements into the hash table
insert(hashTable, 5, tableSize);
insert(hashTable, 15, tableSize);
insert(hashTable, 25, tableSize);
insert(hashTable, 35, tableSize);
printf("Hash table after insertion:\n");
display(hashTable, tableSize);
// Search for a key in the hash table
int searchKey = 15;
if (search(hashTable, searchKey, tableSize)) {
printf("Key %d found.\n", searchKey);
} else {
printf("Key %d not found.\n", searchKey);
}
// Delete a key from the hash table
delete(hashTable, 15, tableSize);
printf("Hash table after deletion:\n");
display(hashTable, tableSize);
return 0;
}
Explanation
- Structure of Node:
- The
struct Noderepresents each node in a linked list. - Each node stores an integer
dataand a pointernextto the next node.
- The
- Creating a Node:
- The
createNodefunction allocates memory for a new node, assigns the data, and initializes thenextpointer toNULL.
- The
- Hash Function:
- The hash function used here is a simple modulus operation (
key % tableSize), which calculates the index where a particular key should be stored.
- The hash function used here is a simple modulus operation (
- Insert Function:
- The
insertfunction calculates the index using the hash function. - It creates a new node with the given key and inserts it at the beginning of the linked list at that index.
- The
- Search Function:
- The
searchfunction calculates the index and traverses the linked list at that index. - If a node with the key is found, it returns
1(key found). - Otherwise, it returns
0(key not found).
- The
- Delete Function:
- The
deletefunction calculates the index and searches for the node with the given key. - If the node is found, it adjusts the pointers to remove the node from the linked list and frees its memory.
- The
- Display Function:
- The
displayfunction iterates through the hash table. - For each index, it prints the keys stored in the linked list at that index.
- The
- Main Function:
- It initializes the hash table with a given size.
- It inserts values into the hash table, displays it, searches for a value, deletes a value, and displays the updated hash table.
Output
Hash table after insertion:
HashTable[0]: NULL
HashTable[1]: NULL
HashTable[2]: NULL
HashTable[3]: NULL
HashTable[4]: NULL
HashTable[5]: 35 -> 25 -> 15 -> 5 -> NULL
HashTable[6]: NULL
HashTable[7]: NULL
HashTable[8]: NULL
HashTable[9]: NULL
Key 15 found.
Key 15 deleted.
Hash table after deletion:
HashTable[0]: NULL
HashTable[1]: NULL
HashTable[2]: NULL
HashTable[3]: NULL
HashTable[4]: NULL
HashTable[5]: 35 -> 25 -> 5 -> NULL
HashTable[6]: NULL
HashTable[7]: NULL
HashTable[8]: NULL
HashTable[9]: NULL
Summary
This implementation of a hash table using chaining effectively handles collisions by storing keys in a linked list at each index. It allows for efficient insertion, searching, and deletion of keys. By chaining, we can manage cases where multiple keys hash to the same index without loss of data.
