Simple Hash Map (Hash Table) Implementation in C++
Hash table (also, hash map) is a data structure that basically maps keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the corresponding value can be found.
We will go through a basic Hash Map implementation in C++ that is supporting generic type key-value pairs with the help of templates. It is genuinely not a production-ready implementation of HashMap class, however it simply shows how this data structure can be implemented in C++.
Below, HashNode class represents each bucket node in the table. This class has key() and value() accessor functions for corresponding pair elements. It also includes a pointer to the next node sharing the same key.
The hash function ideally assigns each key to a unique bucket, but most hash table designs assume that hash collisions can occur. My hash function just returns the remainder when the key is divided by the hash table size.
By user, custom hash function class with operator() method implementation should be defined according to the key distribution. i.e. if the range of key values is very small, then most of the hash table is not used and chains get longer.
Below is the Hash Map implementation in C++. HashMap class contains the hash table, which is a double pointer to HashNode class and default table size in constant is used to construct this hash table.
In addition, the class contains get(key) function to access mapped value by key, put(key,value) function to put key-value pair in table and remove(key) function to remove hash node by key. For collision resolution, separate chaining strategy has been used.
As an example usage, you first create a container by template initialising and put key-value pairs in it. Then, you can get or remove elements from the map. If the key searched does not exist, false is returned and value is not updated.
This is basic and complete hash map, but some of the expected functionality is missing. I can call some of them:
- Iterators for traversal,
- comparator for key comparisons,
- capacity and size functions,
- load factor and rehashing,
- allocator for dynamic memory allocations, and
- thread safety.
The complete project is on GitHub https://github.com/aozturk/HashMap.
For any of your queries or suggestions, you can create a new issue or contribute to the project by sending a pull request with your improvements.
Originally published at tech.aozturk.me on October 22, 2013.
