Assignment 5: Hash Table
Set A
a) Write a program to implement various types of hash functions which are used to place the data in a hash table
a. Division Method
b. Mid Square Method
c. Digit Folding Method
Accept n values from the user and display appropriate message in case of collision for each of the above functions.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define TABLE_SIZE 100
// Initialize hash table with -1 (empty)
void initTable(int table[]) {
for (int i = 0; i < TABLE_SIZE; i++) table[i] = -1;
}
// a. Division Method: h(k) = k mod m
int hashDivision(int key) {
return key % TABLE_SIZE;
}
// b. Mid-Square Method: Square key and extract middle digits
int hashMidSquare(int key) {
long long squared = (long long)key * key;
// For a table of size 100, we need 2 digits.
// Example: 1234^2 = 1522756. We take middle digits (e.g., 22).
char str[20];
sprintf(str, "%lld", squared);
int len = strlen(str);
int mid = len / 2;
// Extract 2 digits starting near the middle
int val = (squared / (long long)pow(10, mid - 1)) % 100;
return val;
}
// c. Digit Folding Method: Break key into parts and sum them
int hashDigitFolding(int key) {
int sum = 0;
int temp = key;
while (temp > 0) {
sum += temp % 100; // Take 2 digits at a time for TABLE_SIZE 100
temp /= 100;
}
return sum % TABLE_SIZE;
}
void insert(int table[], int key, int (*hashFunc)(int)) {
int index = hashFunc(key);
if (table[index] == -1) {
table[index] = key;
printf("Key %d inserted at index %d\n", key, index);
} else {
printf("COLLISION: Index %d already occupied by %d. Cannot place %d.\n", index, table[index], key);
}
}
int main() {
int n, key;
int table[TABLE_SIZE];
printf("Enter number of values (n): ");
scanf("%d", &n);
int keys[n];
for(int i=0; i<n; i++) {
printf("Enter value %d: ", i+1);
scanf("%d", &keys[i]);
}
printf("\n--- Division Method ---\n");
initTable(table);
for(int i=0; i<n; i++) insert(table, keys[i], hashDivision);
printf("\n--- Mid-Square Method ---\n");
initTable(table);
for(int i=0; i<n; i++) insert(table, keys[i], hashMidSquare);
printf("\n--- Digit Folding Method ---\n");
initTable(table);
for(int i=0; i<n; i++) insert(table, keys[i], hashDigitFolding);
return 0;
}
b) Write a C program to implement a hash table using separate chaining with linked lists with following operation.
a. Insert a key
b. Search a key
c. Delete a key
d. Display the hash table
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10
// Node structure for linked list
struct Node {
int key;
struct Node* next;
};
// Hash table (array of linked list heads)
struct Node* hashTable[TABLE_SIZE];
// Hash function
int hashFunction(int key) {
return key % TABLE_SIZE;
}
// Insert a key
void insertKey(int key) {
int index = hashFunction(key);
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->key = key;
newNode->next = hashTable[index];
hashTable[index] = newNode;
printf("Key %d inserted successfully.\n", key);
}
// Search a key
void searchKey(int key) {
int index = hashFunction(key);
struct Node* temp = hashTable[index];
while (temp != NULL) {
if (temp->key == key) {
printf("Key %d found at index %d.\n", key, index);
return;
}
temp = temp->next;
}
printf("Key %d not found.\n", key);
}
// Delete a key
void deleteKey(int key) {
int index = hashFunction(key);
struct Node* temp = hashTable[index];
struct Node* prev = NULL;
while (temp != NULL) {
if (temp->key == key) {
if (prev == NULL)
hashTable[index] = temp->next;
else
prev->next = temp->next;
free(temp);
printf("Key %d deleted successfully.\n", key);
return;
}
prev = temp;
temp = temp->next;
}
printf("Key %d not found.\n", key);
}
// Display hash table
void displayHashTable() {
for (int i = 0; i < TABLE_SIZE; i++) {
printf("Index %d: ", i);
struct Node* temp = hashTable[i];
while (temp != NULL) {
printf("%d -> ", temp->key);
temp = temp->next;
}
printf("NULL\n");
}
}
// Main function
int main() {
int choice, key;
// Initialize hash table
for (int i = 0; i < TABLE_SIZE; i++)
hashTable[i] = NULL;
do {
printf("\n--- Hash Table Operations ---\n");
printf("1. Insert Key\n");
printf("2. Search Key\n");
printf("3. Delete Key\n");
printf("4. Display Hash Table\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter key to insert: ");
scanf("%d", &key);
insertKey(key);
break;
case 2:
printf("Enter key to search: ");
scanf("%d", &key);
searchKey(key);
break;
case 3:
printf("Enter key to delete: ");
scanf("%d", &key);
deleteKey(key);
break;
case 4:
displayHashTable();
break;
case 5:
printf("Exiting program.\n");
break;
default:
printf("Invalid choice.\n");
}
} while (choice != 5);
return 0;
}
Set B
a) Write a C program to implement a hash table using open addressing with linear probing. Perform the following
operations.( Assume all keys are positive integers)
a. Insert
b. Search
c. Delete
d. Display
#include <stdio.h>
#define TABLE_SIZE 10
#define EMPTY -1
#define DELETED -2
int hashTable[TABLE_SIZE];
// Hash function
int hashFunction(int key) {
return key % TABLE_SIZE;
}
// Insert a key
void insertKey(int key) {
int index = hashFunction(key);
for (int i = 0; i < TABLE_SIZE; i++) {
int probeIndex = (index + i) % TABLE_SIZE;
if (hashTable[probeIndex] == EMPTY ||
hashTable[probeIndex] == DELETED) {
hashTable[probeIndex] = key;
printf("Key %d inserted at index %d.\n", key, probeIndex);
return;
}
}
printf("Hash table is full. Cannot insert key %d.\n", key);
}
// Search a key
void searchKey(int key) {
int index = hashFunction(key);
for (int i = 0; i < TABLE_SIZE; i++) {
int probeIndex = (index + i) % TABLE_SIZE;
if (hashTable[probeIndex] == EMPTY)
break;
if (hashTable[probeIndex] == key) {
printf("Key %d found at index %d.\n", key, probeIndex);
return;
}
}
printf("Key %d not found.\n", key);
}
// Delete a key
void deleteKey(int key) {
int index = hashFunction(key);
for (int i = 0; i < TABLE_SIZE; i++) {
int probeIndex = (index + i) % TABLE_SIZE;
if (hashTable[probeIndex] == EMPTY)
break;
if (hashTable[probeIndex] == key) {
hashTable[probeIndex] = DELETED;
printf("Key %d deleted successfully.\n", key);
return;
}
}
printf("Key %d not found. Cannot delete.\n", key);
}
// Display hash table
void displayHashTable() {
printf("\nHash Table:\n");
for (int i = 0; i < TABLE_SIZE; i++) {
printf("Index %d: ", i);
if (hashTable[i] == EMPTY)
printf("EMPTY");
else if (hashTable[i] == DELETED)
printf("DELETED");
else
printf("%d", hashTable[i]);
printf("\n");
}
}
// Main function
int main() {
int choice, key;
// Initialize hash table
for (int i = 0; i < TABLE_SIZE; i++)
hashTable[i] = EMPTY;
do {
printf("\n--- Hash Table Operations (Linear Probing) ---\n");
printf("1. Insert\n");
printf("2. Search\n");
printf("3. Delete\n");
printf("4. Display\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter positive key to insert: ");
scanf("%d", &key);
if (key > 0)
insertKey(key);
else
printf("Only positive keys allowed.\n");
break;
case 2:
printf("Enter key to search: ");
scanf("%d", &key);
searchKey(key);
break;
case 3:
printf("Enter key to delete: ");
scanf("%d", &key);
deleteKey(key);
break;
case 4:
displayHashTable();
break;
case 5:
printf("Exiting program.\n");
break;
default:
printf("Invalid choice.\n");
}
} while (choice != 5);
return 0;
}
b) Write a C program to implement a hash table using Open Addressing with Quadratic Probing. Perform the following
operations. (Assume all keys are positive integers)
a. Insert
b. Search
c. Delete
d. Display
#include <stdio.h>
#define TABLE_SIZE 10
#define EMPTY -1
#define DELETED -2
int hashTable[TABLE_SIZE];
// Hash function
int hashFunction(int key) {
return key % TABLE_SIZE;
}
// Insert a key using Quadratic Probing
void insertKey(int key) {
int index = hashFunction(key);
for (int i = 0; i < TABLE_SIZE; i++) {
int probeIndex = (index + i * i) % TABLE_SIZE;
if (hashTable[probeIndex] == EMPTY ||
hashTable[probeIndex] == DELETED) {
hashTable[probeIndex] = key;
printf("Key %d inserted at index %d.\n", key, probeIndex);
return;
}
}
printf("Hash table is full. Cannot insert key %d.\n", key);
}
// Search a key using Quadratic Probing
void searchKey(int key) {
int index = hashFunction(key);
for (int i = 0; i < TABLE_SIZE; i++) {
int probeIndex = (index + i * i) % TABLE_SIZE;
if (hashTable[probeIndex] == EMPTY)
break;
if (hashTable[probeIndex] == key) {
printf("Key %d found at index %d.\n", key, probeIndex);
return;
}
}
printf("Key %d not found.\n", key);
}
// Delete a key using Quadratic Probing
void deleteKey(int key) {
int index = hashFunction(key);
for (int i = 0; i < TABLE_SIZE; i++) {
int probeIndex = (index + i * i) % TABLE_SIZE;
if (hashTable[probeIndex] == EMPTY)
break;
if (hashTable[probeIndex] == key) {
hashTable[probeIndex] = DELETED;
printf("Key %d deleted successfully.\n", key);
return;
}
}
printf("Key %d not found. Cannot delete.\n", key);
}
// Display the hash table
void displayHashTable() {
printf("\nHash Table:\n");
for (int i = 0; i < TABLE_SIZE; i++) {
printf("Index %d: ", i);
if (hashTable[i] == EMPTY)
printf("EMPTY");
else if (hashTable[i] == DELETED)
printf("DELETED");
else
printf("%d", hashTable[i]);
printf("\n");
}
}
// Main function
int main() {
int choice, key;
// Initialize hash table
for (int i = 0; i < TABLE_SIZE; i++)
hashTable[i] = EMPTY;
do {
printf("\n--- Hash Table Operations (Quadratic Probing) ---\n");
printf("1. Insert\n");
printf("2. Search\n");
printf("3. Delete\n");
printf("4. Display\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter positive key to insert: ");
scanf("%d", &key);
if (key > 0)
insertKey(key);
else
printf("Only positive keys allowed.\n");
break;
case 2:
printf("Enter key to search: ");
scanf("%d", &key);
searchKey(key);
break;
case 3:
printf("Enter key to delete: ");
scanf("%d", &key);
deleteKey(key);
break;
case 4:
displayHashTable();
break;
case 5:
printf("Exiting program.\n");
break;
default:
printf("Invalid choice.\n");
}
} while (choice != 5);
return 0;
}
No comments:
Post a Comment