119 views
C++ hashing programme with chaining
Creating a basic C++ program that implements hashing with chaining involves defining a hash table and implementing basic hash table operations like insertion and retrieval using linked lists to handle collisions. Here’s a simple example of a hash table with chaining:
C++
#include <iostream>
#include <vector>
#include <list>
// Define the size of the hash table
const int tableSize = 10;
// Define a class to represent key-value pairs
class KeyValuePair {
public:
int key;
int value;
KeyValuePair(int k, int v) : key(k), value(v) {}
};
// Define a hash table using an array of lists (chaining)
class HashTable {
public:
HashTable() : table(tableSize) {}
// Hash function to determine the index for a given key
int hash(int key) {
return key % tableSize;
}
// Insert a key-value pair into the hash table
void insert(int key, int value) {
int index = hash(key);
for (auto& pair : table[index]) {
if (pair.key == key) {
// Key already exists; update the value
pair.value = value;
return;
}
}
// Key does not exist; insert a new key-value pair
table[index].emplace_back(key, value);
}
// Retrieve the value associated with a key
int get(int key) {
int index = hash(key);
for (auto& pair : table[index]) {
if (pair.key == key) {
return pair.value; // Key found; return the associated value
}
}
return -1; // Key not found
}
private:
std::vector<std::list<KeyValuePair>> table;
};
int main() {
HashTable hashTable;
// Insert key-value pairs into the hash table
hashTable.insert(1, 42);
hashTable.insert(11, 101);
hashTable.insert(21, 999);
// Retrieve values using keys
int value1 = hashTable.get(1);
int value11 = hashTable.get(11);
int valueNonExistent = hashTable.get(7);
// Display the retrieved values
std::cout << "Value for key 1: " << value1 << std::endl; // 42
std::cout << "Value for key 11: " << value11 << std::endl; // 101
std::cout << "Value for non-existent key 7: " << valueNonExistent << std::endl; // -1
return 0;
}
In this example:
- We define a
HashTable
class that uses an array ofstd::list
to implement chaining for handling collisions. - The
hash()
method calculates the index in the array for a given key using a simple modulus operation. - The
insert()
method inserts a key-value pair into the hash table. If the key already exists, it updates the value; otherwise, it adds a new key-value pair. - The
get()
method retrieves the value associated with a key. If the key is not found, it returns -1 to indicate that the key does not exist.
This is a basic example of a hash table with chaining. In practice, you can enhance it with more features and handle edge cases as needed.