Home Data Structures and Algorithms with C++ Hash Tables in C++

Lesson 12 of 48

In Progress

← Previous Next→

Hash Tables in C++

Yasin Cakal

Hash tables are a fundamental data structure used in computer science, and are essential in helping to define algorithms and solve problems. There are many different implementations of hash tables in different programming languages, but in this article, we will focus on how to implement hash tables in C++. We will discuss the overview of hash tables, how to implement them using arrays, different types of hash functions, strategies for handling collisions, and the various applications of hash tables.

Overview of Hash Tables

A hash table is a data structure which organizes data using a key-value pair. A key is a unique identifier of a data item, and the value is the data itself. The hash table allows us to quickly search for data items in a collection by using their key. Hash tables are also known as hash maps, dictionaries, or associative arrays.

In C++, a hash table can be implemented as a template class. The template class will contain two type parameters: the type of the key, and the type of the value. The class will also provide methods for inserting, retrieving, and removing elements from the hash table.

Implementing Hash Tables Using Arrays

To implement a hash table in C++, we will use an array data structure. The array will store the key-value pairs that make up the hash table. We will also use a hash function to determine the index of the array where the key-value pair should be stored.

template<typename Key, typename Value>
class HashTable {
private:
    std::vector<std::pair<Key, Value>> table;

public:
    HashTable(int size);
    void insert(Key key, Value value);
    Value get(Key key);
    void remove(Key key);
};

The above template class provides a constructor to initialize the size of the array and three methods to insert, retrieve, and remove elements from the hash table.

Hash Functions

A hash function is a function that takes a key as an input and returns an index into the array as an output. The index is used to store the key-value pair in the array.

There are a few different types of hash functions. The most common type is a modulo hash function, which takes the modulus of the key with the size of the array. This type of hash function is simple to implement and is suitable for small datasets.

The following is an example of a modulo hash function implemented in C++:

int hash(int key, int arraySize) {
    return key % arraySize;
}

The modulo hash function takes an integer key and the size of the array as parameters, and returns the index of the array where the key-value pair should be stored.

Collision Handling

A collision occurs when two different keys are hashed to the same index. When this happens, we must find a way to store both keys at the same index. There are a few different strategies for handling collisions. The most common strategies are chaining and open addressing.

Chaining is a strategy where a linked list is used to store multiple key-value pairs at the same index. This is a simple strategy to implement, but it can be inefficient if the hash table is too small or if the hash function is not evenly distributed.

Open addressing is a strategy where the hash table is searched for an empty slot to store the key-value pair. If an empty slot is found, the key-value pair is stored in the empty slot. If no empty slot is found, then the hash table is rehashed and the search is repeated.

The following is an example of a collision handling strategy implemented in C++ using open addressing:

void handleCollision(Key key, Value value, int arraySize) {
    int index = hash(key, arraySize);
    while (table[index].first != NULL) {
        index = (index + 1) % arraySize;
    }
    table[index] = std::make_pair(key, value);
}

The above code takes a key and a value as parameters, and a hash table size. It first computes the index of the array where the key-value pair should be stored. If the slot is already occupied, it searches for the next empty slot. If an empty slot is found, the key-value pair is stored in the empty slot.

Applications of Hash Tables

Hash tables are a very versatile data structure and are used in many different applications. They are often used for data storage and retrieval, caching, and for efficiently solving problems.

Hash tables are often used for data storage and retrieval. They allow us to quickly insert, retrieve, and delete data items by using their key. This makes them an ideal data structure for databases and other storage systems.

Hash tables are also used for caching. Caching is a technique used to store data in a faster storage system in order to improve the performance of a program. Hash tables are often used to cache data because they allow us to quickly retrieve data items by their key.

Finally, hash tables are often used to efficiently solve problems. Many algorithms can be implemented using hash tables, such as searching, sorting, and graph traversal algorithms. Hash tables can also be used to solve problems such as finding the shortest path or the maximum value in a collection.

Conclusion

In this article, we discussed how to implement hash tables in C++. We discussed the overview of hash tables, how to implement them using arrays, different types of hash functions, strategies for handling collisions, and the various applications of hash tables. Hash tables are an essential data structure for computer science and are used in many different applications.

Exercises

Write a C++ program that implements a hash table using an array data structure. The hash table should contain integers as keys and strings as values.

#include <iostream>
#include <vector>
#include <utility>

template<typename Key, typename Value>
class HashTable {
private:
    std::vector<std::pair<Key, Value>> table;

public:
    HashTable(int size);
    void insert(Key key, Value value);
    Value get(Key key);
    void remove(Key key);
};

template<typename Key, typename Value>
HashTable<Key, Value>::HashTable(int size) {
    table.resize(size);
}

template<typename Key, typename Value>
void HashTable<Key, Value>::insert(Key key, Value value) {
    int index = key % table.size();
    table[index] = std::make_pair(key, value);
}

template<typename Key, typename Value>
Value HashTable<Key, Value>::get(Key key) {
    int index = key % table.size();
    return table[index].second;
}

template<typename Key, typename Value>
void HashTable<Key, Value>::remove(Key key) {
    int index = key % table.size();
    table[index] = std::make_pair(NULL, NULL);
}

int main() {
    HashTable<int, std::string> hashTable(10);
    hashTable.insert(1, "one");
    hashTable.insert(2, "two");
    hashTable.insert(3, "three");
    std::cout << hashTable.get(1) << std::endl;
    std::cout << hashTable.get(2) << std::endl;
    std::cout << hashTable.get(3) << std::endl;
    hashTable.remove(2);
    std::cout << hashTable.get(2) << std::endl;
    return 0;
}

Write a C++ program that implements a hash table using open addressing for collision handling. The hash table should contain strings as keys and integers as values.

#include <iostream>
#include <vector>
#include <utility>
#include <string>

template<typename Key, typename Value>
class HashTable {
private:
    std::vector<std::pair<Key, Value>> table;

public:
    HashTable(int size);
    int hash(Key key);
    void insert(Key key, Value value);
    Value get(Key key);
    void remove(Key key);
};

template<typename Key, typename Value>
HashTable<Key, Value>::HashTable(int size) {
    table.resize(size);
}

template<typename Key, typename Value>
int HashTable<Key, Value>::hash(Key key) {
    int hash = 0;
    for (int i = 0; i < key.length(); i++) {
        hash += (int)key[i];
    }
    return hash % table.size();
}

template<typename Key, typename Value>
void HashTable<Key, Value>::insert(Key key, Value value) {
    int index = hash(key);
    while (table[index].first != NULL) {
        index = (index + 1) % table.size();
    }
    table[index] = std::make_pair(key, value);
}

template<typename Key, typename Value>
Value HashTable<Key, Value>::get(Key key) {
    int index = hash(key);
    return table[index].second;
}

template<typename Key, typename Value>
void HashTable<Key, Value>::remove(Key key) {
    int index = hash(key);
    table[index] = std::make_pair(NULL, NULL);
}

int main() {
    HashTable<std::string, int> hashTable(10);
    hashTable.insert("one", 1);
    hashTable.insert("two", 2);
    hashTable.insert("three", 3);
    std::cout << hashTable.get("one") << std::endl;
    std::cout << hashTable.get("two") << std::endl;
    std::cout << hashTable.get("three") << std::endl;
    hashTable.remove("two");
    std::cout << hashTable.get("two") << std::endl;
    return 0;
}

Write a C++ program to find the maximum value in a hash table. The hash table should contain strings as keys and integers as values.

#include <iostream>
#include <vector>
#include <utility>
#include <string>

template<typename Key, typename Value>
class HashTable {
private:
    std::vector<std::pair<Key, Value>> table;

public:
    HashTable(int size);
    int hash(Key key);
    void insert(Key key, Value value);
    Value get(Key key);
    void remove(Key key);
};

template<typename Key, typename Value>
HashTable<Key, Value>::HashTable(int size) {
    table.resize(size);
}

template<typename Key, typename Value>
int HashTable<Key, Value>::hash(Key key) {
    int hash = 0;
    for (int i = 0; i < key.length(); i++) {
        hash += (int)key[i];
    }
    return hash % table.size();
}

template<typename Key, typename Value>
void HashTable<Key, Value>::insert(Key key, Value value) {
    int index = hash(key);
    while (table[index].first != NULL) {
        index = (index + 1) % table.size();
    }
    table[index] = std::make_pair(key, value);
}

template<typename Key, typename Value>
Value HashTable<Key, Value>::get(Key key) {
    int index = hash(key);
    return table[index].second;
}

template<typename Key, typename Value>
void HashTable<Key, Value>::remove(Key key) {
    int index = hash(key);
    table[index] = std::make_pair(NULL, NULL);
}

int findMaxValue(HashTable<std::string, int> &hashTable) {
    int maxValue = 0;
    for (int i = 0; i < hashTable.table.size(); i++) {
        if (hashTable.table[i].second > maxValue) {
            maxValue = hashTable.table[i].second;
        }
    }
    return maxValue;
}

int main() {
    HashTable<std::string, int> hashTable(10);
    hashTable.insert("one", 1);
    hashTable.insert("two", 2);
    hashTable.insert("three", 3);
    std::cout << findMaxValue(hashTable) << std::endl;
    return 0;
}

Write a C++ program to sort a hash table. The hash table should contain integers as keys and strings as values.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

template<typename Key, typename Value>
class HashTable {
private:
    std::vector<std::pair<Key, Value>> table;

public:
    HashTable(int size);
    void insert(Key key, Value value);
    Value get(Key key);
    void remove(Key key);
    void sort();
};

template<typename Key, typename Value>
HashTable<Key, Value>::HashTable(int size) {
    table.resize(size);
}

template<typename Key, typename Value>
void HashTable<Key, Value>::insert(Key key, Value value) {
    int index = key % table.size();
    table[index] = std::make_pair(key, value);
}

template<typename Key, typename Value>
Value HashTable<Key, Value>::get(Key key) {
    int index = key % table.size();
    return table[index].second;
}

template<typename Key, typename Value>
void HashTable<Key, Value>::remove(Key key) {
    int index = key % table.size();
    table[index] = std::make_pair(NULL, NULL);
}

template<typename Key, typename Value>
void HashTable<Key, Value>::sort() {
    std::sort(table.begin(), table.end());
}

int main() {
    HashTable<int, std::string> hashTable(10);
    hashTable.insert(1, "one");
    hashTable.insert(2, "two");
    hashTable.insert(3, "three");
    hashTable.sort();
    std::cout << hashTable.get(1) << std::endl;
    std::cout << hashTable.get(2) << std::endl;
    std::cout << hashTable.get(3) << std::endl;
    return 0;
}

Write a C++ program to search for a key in a hash table. The hash table should contain strings as keys and integers as values.

#include <iostream>
#include <vector>
#include <utility>
#include <string>

template<typename Key, typename Value>
class HashTable {
private:
    std::vector<std::pair<Key, Value>> table;

public:
    HashTable(int size);
    int hash(const Key &key);
    void insert(const Key &key, const Value &value);
    Value search(const Key &key);
};

template<typename Key, typename Value>
HashTable<Key, Value>::HashTable(int size) {
    table.resize(size);
}

template<typename Key, typename Value>
int HashTable<Key, Value>::hash(const Key &key) {
    // Implement your own hash function here
    return 0;
}

template<typename Key, typename Value>
void HashTable<Key, Value>::insert(const Key &key, const Value &value) {
    int index = hash(key);
    table[index] = std::make_pair(key, value);
}

template<typename Key, typename Value>
Value HashTable<Key, Value>::search(const Key &key) {
    int index = hash(key);
    return table[index].second;
}

int main() {
    HashTable<std::string, int> table(10);
    table.insert("Hello", 5);
    table.insert("World", 10);

    std::cout << "Hello: " << table.search("Hello") << std::endl;
    std::cout << "World: " << table.search("World") << std::endl;

    return 0;
}

Data Structures and Algorithms with C++

Participants 942