Pre-Requisite:
Before doing programming in C++, we must know which IDE i have to use. Follow just few steps to execute your code:
1. Install Dev-C++
Download Dev-C++:
- Open your browser visit the official Embarcadero Dev-C++ website or use a trusted source like SourceForge.
- Download and install the IDE.
Ensure the installer includes the MinGW (GCC) Compiler:
- Dev-C++ often comes bundled with MinGW, which supports STL
2. Configure Dev-C++
Launch the IDE after installation.
Set the Compiler:
- Go to
Tools > Compiler Options. - Check the compiler version and ensure it is modern (preferably GCC 9 or higher for full STL and modern C++ standard support).
- Go to
Set the C++ Standard (Optional but Recommended):
- Under
Compiler Options, add the following flags in the "Add the following commands when calling the compiler" - -std=c++17
3. Create a New Project
- Go to
File > New > Project. - Select "Console Application" and set the language to "C++."
- Save the project in your desired location.
Let's Start Implementation:
Problem Statement:
Consider telephone book database of n clients make use of a hash table implementation to quickly look up client's telephone number. Make use of two collision handling techniques and compare them using number of comparisons required to find a set of telephone numbers.
Algorithm:
Step 1: Start
Step 2: Define a Hash Table class with the following components:
Step 2.1: For chaining, use an array of linked lists to handle collisions.
Step 2.2: For open addressing, use an array to store keys directly, along with a status array to track filled slots.
Step 3: Hash Function:
Step 3.1: Use a simple modulo operation to calculate the hash index.
Step 4: Insert a client's phone number:
Step 4.1: Compute the hash index using the hash function.
Step 4.2: Handle collisions using the chosen technique.
Step 5: Search for a client's phone number:
Step 5.1: Compute the hash index and probe the table until the number is found or confirmed absent.
Step 6: Compare the techniques:
Step 6.1: Measure the number of comparisons for both techniques when looking up a set of numbers.
Step 7: Stop.
Code 1:
1. Hash Table with Chaining:
#include <iostream>
#include <cstring>
using namespace std;
#define TABLE_SIZE 10
#define MAX_CHAIN_SIZE 5 // Maximum number of entries in a chain
class HashTable {
private:
string names[TABLE_SIZE][MAX_CHAIN_SIZE]; // 2D array for names
string phones[TABLE_SIZE][MAX_CHAIN_SIZE]; // 2D array for phone numbers
int chainSize[TABLE_SIZE]; // To track the number of entries in each bucket
// Hash function
int hashFunction(const string& key) {
int hash = 0;
for (char c : key) {
hash += c;
}
return hash % TABLE_SIZE;
}
public:
// Constructor
HashTable() {
memset(chainSize, 0, sizeof(chainSize));
}
// Insert function
void insert(const string& name, const string& phone) {
int index = hashFunction(name);
if (chainSize[index] < MAX_CHAIN_SIZE) {
names[index][chainSize[index]] = name;
phones[index][chainSize[index]] = phone;
chainSize[index]++;
} else {
cout << "Error: Bucket overflow! Cannot insert " << name << ".\n";
}
}
// Search function with static variable to count comparisons
string search(const string& name) {
static int totalComparisons = 0; // Static variable to keep track of total comparisons
int comparisons = 0; // Local variable for comparisons in this call
int index = hashFunction(name);
for (int i = 0; i < chainSize[index]; ++i) {
comparisons++;
totalComparisons++; // Increment the static variable
if (names[index][i] == name) {
//cout << "Comparisons for this search: " << comparisons << endl;
cout << "Total comparisons so far: " << totalComparisons << endl;
return phones[index][i];
}
}
//cout << "Comparisons for this search: " << comparisons << endl;
cout << "Total comparisons so far: " << totalComparisons << endl;
return "Not Found";
}
void display() {
cout << "Hash Table Contents:\n";
for (int i = 0; i < TABLE_SIZE; ++i) {
cout << "Bucket " << i << ": ";
if (chainSize[i] == 0) {
cout << "Empty\n";
} else {
for (int j = 0; j < chainSize[i]; ++j) {
cout << "[" << names[i][j] << ": " << phones[i][j] << "] ";
}
cout << "\n";
}
}
}
};
int main() {
HashTable hashTable;
int n;
cout << "Enter the number of clients: ";
cin >> n;
// Insert data into the hash table
for (int i = 0; i < n; ++i) {
string name, phone;
cout << "Enter name of client " << i + 1 << ": ";
cin >> name;
cout << "Enter phone number of client " << i + 1 << ": ";
cin >> phone;
hashTable.insert(name, phone);
}
cout<<"\n";
cout<<"\n Let's Search name from Hash Table:\n";
// Search for a key
string searchName;
cout << "Enter the name to search for: ";
cin >> searchName;
string result = hashTable.search(searchName);
if (result != "Not Found") {
cout << "Phone number of " << searchName << ": " << result <<endl;
} else {
cout << searchName << " not found in the telephone book.\n";
}
cout<<"\n";
cout<<"\nHash Table element are as follows...\n";
hashTable.display();
return 0;
}
Output:
Explanation of Output:
As we see in above output some inputs are get stored in same bucket. As shown in above Bucket no 4 Three inputs are stored in same Bucket no 4 this happens just because of Hash Function we used. The hash function returns the same index for all those inputs, so they gets stored in same bucket.
let's see how hash function works:
S = 83 + o = 111 + n = 110 + a = 97 + l = 108 + i = 105 Total = 614
when we find the reminder of above name ASCII Values sum will get 614%10 = 4
N = 78 + i = 105 + t = 116 + i = 105 + n = 110 Total = 514
when we find the reminder of above name ASCII Values sum will get 514%10 = 4
Code 2:
2. A C++ implementation of a hash table using open addressing with linear probing for collision resolution. This implementation includes insert, search, and display operations.
#include <iostream>
#include <cstring>
using namespace std;
#define TABLE_SIZE 10
#define EMPTY "EMPTY" // Placeholder for empty slots
#define DELETED "DELETED" // Placeholder for deleted slots
class HashTable {
private:
string names[TABLE_SIZE]; // Array for names
string phones[TABLE_SIZE]; // Array for phone numbers
bool occupied[TABLE_SIZE]; // Tracks occupied slots
// Hash function
int hashFunction(const string& key) {
int hash = 0;
for (char c : key) {
hash += c;
}
return hash % TABLE_SIZE;
}
public:
// Constructor
HashTable() {
for (int i = 0; i < TABLE_SIZE; ++i) {
names[i] = EMPTY;
phones[i] = EMPTY;
occupied[i] = false;
}
}
// Insert function
void insert(const string& name, const string& phone) {
int index = hashFunction(name);
int start = index;
while (names[index] != EMPTY && names[index] != DELETED) {
index = (index + 1) % TABLE_SIZE;
if (index == start) { // Table is full
cout << "Error: Hash table is full. Cannot insert " << name << ".\n";
return;
}
}
names[index] = name;
phones[index] = phone;
occupied[index] = true;
}
// Search function
string search(const string& name) {
int index = hashFunction(name);
int start = index;
int comparison=0;
while (names[index] != EMPTY) {
comparison++;
if (names[index] == name) {
cout<<"\nTotal Comparisions take to search is:"<<comparison<<endl;
return phones[index];
}
index = (index + 1) % TABLE_SIZE;
if (index == start) { // Avoid infinite loops
break;
}
}
cout<<"\nTotal Comparisions take to search is:"<<comparison<<endl;
return "Not Found";
}
// Display function
void display() {
cout << "Hash Table Contents:\n";
for (int i = 0; i < TABLE_SIZE; ++i) {
if (names[i] == EMPTY || names[i] == DELETED) {
cout << "Bucket " << i << ": [EMPTY]\n";
} else {
cout << "Bucket " << i << ": [" << names[i] << ": " << phones[i] << "]\n";
}
}
}
};
int main() {
HashTable hashTable;
int n;
cout << "Enter the number of clients: ";
cin >> n;
// Insert data into the hash table
for (int i = 0; i < n; ++i) {
string name, phone;
cout << "Enter name of client " << i + 1 << ": ";
cin >> name;
cout << "Enter phone number of client " << i + 1 << ": ";
cin >> phone;
hashTable.insert(name, phone);
}
// Display the hash table
hashTable.display();
// Search for a key
string searchName;
cout << "Enter the name to search for: ";
cin >> searchName;
string result = hashTable.search(searchName);
if (result != "Not Found") {
cout << "Phone number of " << searchName << ": " << result << endl;
} else {
cout << searchName << " not found in the telephone book.\n";
}
return 0;
}
Output:
Question 1: When to use chaining and when to use open addressing Method?
Ans: You use chaining when data is more or we can say when we expect a high load factor, one more thing when we are inserting data at that time memory is not a constraint that is we may use memory as we want means there is no restriction that only 550MB we have to use then in that case we may go with chaining also when we want frequent insertion and deletion operation in that case also we can go with chaining.
You use open addressing when there is no frequent insertion and deletion operation, when there is memory constraint, also when dataset is smaller, or we can say we keep load factor low in those cases we may go with open addressing method.
Note: For chaining we have used array, you can use linked list as a data structure.