C++ hash table
Date: 2022-12-27Last modified: 2023-12-22
Table of contents
What is a hash table?
A Hash Table in C/C++ (Associative array) is a data structure that maps keys to values. This uses a hash function to compute indexes for a key.
Based on the Hash Table index, we can store the value at the appropriate location.
The C++ STL (Standard Template Library) has the unordered_map()
data structure which implements all these hash table functions.
Components
Any Hash Table implementation has the following three components:
- A good Hash function to map keys to values
- A Hash Table Data Structure that supports insert, search and delete operations.
- A Data Structure to account for collision of keys
map
vs unordered_map
Property | map |
unordered_map |
---|---|---|
Ordering | increasing by default | no ordering |
Implementation | self balancing BST like Red-Black tree | Hash table |
Search time | log(N) | O(1) avarage, O(N) worst case |
Insertion time | log(N) + rebalance | Same as search |
Deletion time | log(N) + rebalance | Same as search |
Advantages of BST over Hash Table
- We can get all keys in sorted order by just doing Inorder Traversal of BST.
- This is not a natural operation in Hash Tables and requires extra efforts.
- Doing order statistics, finding closest lower and greater elements, doing range queries are easy to do with BSTs
- Like sorting, these operations are not a natural operation with Hash Tables.
- BSTs are easy to implement compared to hashing
- With BSTs, all operations are garanteed to work in O(log(N))
- But with Hashing, O(1) is average time and some particular operations may be costly i.e, O(n²), especially when table resizing happens.
- In BST we can do range searches efficiently but in Hash Table we cannot do range search efficiently.
- BST are memory efficient but Hash table is not.
Size
The size of our Hash Table and so the number with which we do our modulo calculation, should be a prime number that is only divisible with itself or 1. That way we prevent stacking of many values in one place like 2 when the numbers are even!
Very simple hash table implementation
class VerySimpleHashTable {
// Table: array of list of integer with 7 buckets
array<list<int>, 7> mTable{}; // must be a prime number
size_t hashFunction(int item) { return item % mTable.size(); }
public:
void insertItem(int item) {
auto index = hashFunction(item);
auto it = find(mTable[index].begin(), mTable[index].end(), item);
if (it == mTable[index].end()) {
mTable[index].push_back(item);
}
}
void deleteItem(int item) {
auto index = hashFunction(item);
auto it = find(mTable[index].begin(), mTable[index].end(), item);
if (it != mTable[index].end()) {
mTable[index].erase(it);
}
}
void print() {
size_t index = 0;
for (const auto& lst : mTable) {
cout << "Bucket " << index << ":";
for (const auto& i : lst) {
cout << ' ' << i;
}
cout << '\n';
++index;
}
cout << "-----------------\n";
}
};
Example of use
VerySimpleHashTable simpleTable;
simpleTable.print();
int element;
srand(0);
for (int i = 0; i < 50; ++i) {
element = rand() % 100;
simpleTable.insertItem(element);
}
simpleTable.print();
simpleTable.deleteItem(101);
srand(0);
for (int i = 0; i < 45; ++i) {
element = rand() % 100;
simpleTable.deleteItem(element);
}
simpleTable.print();
C++ unordered_map example
// Helper function
auto print_unorderd_map = [](const auto& table) {
for (const auto& [key, value] : table) {
cout << "Key:[" << key << "] Value:[" << value << "]\n";
};
cout << "-----------------\n";
};
unordered_map<string, string> colorTable = {
{"RED", "#FF0000"}, {"GREEN", "#00FF00"}, {"BLUE", "#0000FF"}};
print_unorderd_map(colorTable);
// Add two new entries to the unordered_map
colorTable["BLACK"] = "#000000";
colorTable["WHITE"] = "#FFFFFF";
// Replace item
colorTable["RED"] = "#FF6666";
print_unorderd_map(colorTable);
colorTable.erase("RED");
print_unorderd_map(colorTable);
Possible output
Bucket 0:
Bucket 1:
Bucket 2:
Bucket 3:
Bucket 4:
Bucket 5:
Bucket 6:
-----------------
Bucket 0: 77 35 49 21 63 56 42 84 98 70
Bucket 1: 15 92 36 29 22
Bucket 2: 86 93 72 30 23 2 58 37
Bucket 3: 59 73 24
Bucket 4: 11 67
Bucket 5: 26 40 68 82 19
Bucket 6: 83 62 27 90 69
-----------------
Bucket 0: 98 70
Bucket 1:
Bucket 2: 37
Bucket 3: 24
Bucket 4:
Bucket 5:
Bucket 6:
-----------------
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]
-----------------
Key:[WHITE] Value:[#FFFFFF]
Key:[BLACK] Value:[#000000]
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF6666]
-----------------
Key:[WHITE] Value:[#FFFFFF]
Key:[BLACK] Value:[#000000]
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
-----------------