Cover Image for C++ hashing programme with chaining
88 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 of std::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.

YOU MAY ALSO LIKE...

The Tech Thunder

The Tech Thunder

The Tech Thunder


COMMENTS