Hash Map in C++ using OOP and Template

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Table of contents:

Introduction to Hash Maps
What is a Hash Map?
Applying OOP Concepts to Hash Maps
Benefits of Templates in Hash Map Implementation
Useful Applications
Implementing a Hash Map Using OOP and Template
Testing the Hash Map Implementation
Handling Collisions

Reading time: 15 minutes

Introduction to Hash Maps

Hash maps are useful data structures utilized for efficient storage and retrieval of key-value pairs. In this article at OpenGenus, we will review the fundamental concepts of a hash map, how to implement them in C++ using OOP concepts and Template, and useful applications.

What is a Hash Map?

A hash map, or a hash table, is a data structure implemented as an array of fixed size that contains buckets, which hold the key-value pairs. Each key-value pair is placed in the array based on a calculated hash index. This involves utilizing a hash function and implementing methods to avoid hash collisions. A hash collision occurs when two values in a hash map possess the same hash value or index in the array. Later in the article, we will discuss ways in which these collisions can be avoided.

Applying OOP Concepts to Hash Maps

Object Oriented Programming (OOP) allows us to hide internal details of the hash map structure while allowing user access to the essential functionality, also known as abstraction. That way, the user can utilize the program as intended without needing to understand the implementation.

Encapsulation lets us protect our implementation while condensing all its functionality in a well-organized class.

Through inheritance, we can expand upon the already defined hash map class and introduce new functionalities such as overriding previously defined methods or implementing new collision resolution functions.

To make our hash map implementation more flexible, we can use polymorphism to create a base hash map class in addition to specialized hash map classes that will inherit and override the original functionality. This allows us to manipulate the specific methods or add functionality based on the needs and requirements of the specialized class.

Benefits of Templates in Hash Map Implementation

Through the use of template, our hash map implementation will have the ability to handle data of multiple types. This allows for code flexibility and performance optimization since we are eliminating the need to rewrite code to accommodate different data types.

Useful Applications

Cache: Caching involves storing frequently used data in a computer to improve performance and data access. Hash maps are perfect for efficient data retrieval, making them the perfect choice for implementing caching mechanisms.
Graphs: Hash maps are well-suited for graph algorithms such as BFS and DFS since they help provide quick and easy access to adjacent nodes in the graph. This allows for fast graph traversal, and therefore desirable performance.

Implementing a Hash Map Using OOP and Template

We will begin by defining the base hash map class as shown below. This will become the parent super class from which all specialized hash map classes will inherit:

#include <vector>
using namespace std;
template <typename keyType, typename valueType>
class HashMap {
public:
    HashMap();
    ~HashMap();
    void Insert(const keyType &key, const valueType &value);
    valueType GetValue(const keyType &key);
    void Remove(const keyType &key);
private:
    int numBuckets;
    vector<vector<pair<keyType, valueType>>> buckets;
};

First, we will implement the HashMap constructor, HashMap():

#include <vector>
using namespace std;
template <typename keyType, typename valueType>
HashMap<keyType, valueType>:: HashMap() {
    numBuckets = 16;
    buckets.resize(numBuckets);
}

This allows us to create a HashMap object in our code and resize it as necessary. Let's also implement the HashMap destructor, ~HashMap():

#include <vector>
using namespace std;
template <typename keyType, typename valueType>
HashMap<keyType, valueType>:: ~HashMap() {
    for (auto &bucket: buckets) {
        bucket.clear();
    }
}

Vector::clear() removes all vector objects and resets the size to 0.

To insert a key-value pair into our hash map, let's define our Insert function:

#include <vector>
using namespace std;
template <typename keyType, typename valueType>
void HashMap<keyType, valueType>::Insert(const keyType &key, const valueType &value) {
    int hashIndex = hash<keyType>{}(key) % numBuckets; // Compute hash index
    for (auto &pair: buckets[hashIndex]) {
        if (pair.first == key) { // If pair already exists, return from function
            pair.second = value;
            return;
        }
    }
    buckets[hashIndex].push_back(make_pair(key, value)); // Otherwise, insert the pair into the hash map
}

If we want to retrieve the value of a specific key-value pair, we can implement GetValue that allows us to find a value given its corresponding key:

#include <vector>
using namespace std;
template <typename keyType, typename valueType>
valueType HashMap<keyType, valueType>::GetValue(const keyType &key) {
    int hashIndex = hash<keyType>{}(key) % numBuckets; // Compute hash index
    for (auto &pair : buckets[hashIndex]) {
        if (pair.first == key) { // If key is found, return corresponding value
            return pair.second;
        }
        else {
            return valueType(); // If key is not found, return default constructor
        }
    }
}

Lastly, let's implement the Remove function that allows us to remove a key-value pair given the key:

#include <vector>
using namespace std;
template <typename keyType, typename valueType>
void HashMap<keyType, valueType>::Remove(const keyType &key) {
    int hashIndex = hash<keyType>{}(key) % numBuckets;
    for (auto it = buckets[hashIndex].begin(); it != buckets[hashIndex].end(); ++it){
        if (it->first == key) {
            buckets[hashIndex].erase(it); // If pair is found, erase it
            return;
        }
    }
}

Testing the Hash Map Implementation

Here is an example of how a hash map object can be initiated and tested:

int main() {
    HashMap<string, int> myHashMap;
    
    myHashMap.Insert("Three", 3);
    myHashMap.Insert("Ten", 10);
    myHashMap.Insert("Six", 6);

    cout << "Value of Three: " << myHashMap.GetValue("Three") << endl;
    cout << "Value of Ten: " << myHashMap.GetValue("Ten") << endl;
    cout << "Value of Six: " << myHashMap.GetValue("Six") << endl;
    
    myHashMap.Insert("Ten", 11);
    cout << "Value of Ten: " << myHashMap.GetValue("Ten") << endl;
    
    myHashMap.Remove("Ten");

    cout << "Value of Ten Post-removal: " << myHashMap.GetValue("Ten") << endl;

    return 0;

}

We inserted three different key-value pairs and obtained the correct value for each. When inserting a new value for a given key, it is correctly updated. After removing a key-value pair and attempting to retrieve its value, we obtained a default constructor value. This shows that our code is working as intended.

Handling Collisions

As briefly mentioned earlier, hash collisions can cause a multitude of issues in our program. So, it is best to incorporate a design that lowers the risk of these collisions for our code to work optimally.

When we first created our hash map class, we initialized our buckets as a vector of vectors to deal with collisions.

vector<vector<pair<keyType, valueType>>> buckets;

This works because a vector of vectors data structure allows us to store multiple key-value pairs with the same hash value inside of the same bucket.

Here is an example of how we can utilize linked lists, or chaining instead of a vector of vectors to initialize our buckets:

#include <vector>
#include <list>
#include <iostream>
using namespace std;

template <typename keyType, typename valueType>
class HashMap {
public:
    HashMap();
    ~HashMap();
    void Insert(const keyType &key, const valueType &value);
    valueType GetValue(const keyType &key);
    void Remove(const keyType &key);
private:
    int numBuckets;
    vector<list<pair<keyType, valueType>>> buckets;
};

Using a linked list can be preferable in many instances due to better performance and flexibility. Through using a linked list, we can ensure that more than one value can co-exist in each bucket without being overwritten.

Here is the complete code for a hash map:

#include <vector>
#include <iostream>
using namespace std;
template <typename keyType, typename valueType>
class HashMap {
public:
    HashMap();
    ~HashMap();
    void Insert(const keyType &key, const valueType &value);
    valueType GetValue(const keyType &key);
    void Remove(const keyType &key);
private:
    int numBuckets;
    vector<vector<pair<keyType, valueType>>> buckets;
};
// Constructor
template <typename keyType, typename valueType>
HashMap<keyType, valueType>:: HashMap() {
    numBuckets = 16;
    buckets.resize(numBuckets);
}
// Destructor
template <typename keyType, typename valueType>
HashMap<keyType, valueType>:: ~HashMap() {
    for (auto &bucket: buckets) {
        bucket.clear();
    }
}
// Insert
template <typename keyType, typename valueType>
void HashMap<keyType, valueType>::Insert(const keyType &key, const valueType &value) {
    int hashIndex = hash<keyType>{}(key) % numBuckets; // Compute hash index
    for (auto &pair: buckets[hashIndex]) {
        if (pair.first == key) { // If pair already exists, update to new value
            pair.second = value;
            return;
        }
    }
    buckets[hashIndex].push_back(make_pair(key, value)); // Otherwise, insert the pair into the hash map
}
// GetValue
template <typename keyType, typename valueType>
valueType HashMap<keyType, valueType>::GetValue(const keyType &key) {
    int hashIndex = hash<keyType>{}(key) % numBuckets; // Compute hash index
    for (auto &pair : buckets[hashIndex]) {
        if (pair.first == key) { // If key is found, return corresponding value
            return pair.second;
        }
        else {
            return valueType(); // If key is not found, return default constructor
        }
    }
}
// Remove
template <typename keyType, typename valueType>
void HashMap<keyType, valueType>::Remove(const keyType &key) {
    int hashIndex = hash<keyType>{}(key) % numBuckets;
    for (auto it = buckets[hashIndex].begin(); it != buckets[hashIndex].end(); ++it){
        if (it->first == key) {
            buckets[hashIndex].erase(it); // If pair is found, erase it
            return;
        }
    }
}

int main() {
    HashMap<string, int> myHashMap;
    
    myHashMap.Insert("Three", 3);
    myHashMap.Insert("Ten", 10);
    myHashMap.Insert("Six", 6);

    cout << "Value of Three: " << myHashMap.GetValue("Three") << endl;
    cout << "Value of Ten: " << myHashMap.GetValue("Ten") << endl;
    cout << "Value of Six: " << myHashMap.GetValue("Six") << endl;
    
    myHashMap.Insert("Ten", 11);
    cout << "Value of Ten: " << myHashMap.GetValue("Ten") << endl;
    
    myHashMap.Remove("Ten");

    cout << "Value of Ten Post-removal: " << myHashMap.GetValue("Ten") << endl;

    return 0;

}