Implementing a HashMap using a HashTable implementation

I have a hashtable implementation which contains functions such as insert, remove, find, exists.

Using that hashtable I wanted to implement a hashmap.

So I had in mind to create a simple pair class that would just contain a key and a value. It would have the operator= overloaded to take into account only the keys equality. Also the hash function would get as input a pair object and return the hash, again taking into account only the key part.

Thus I would have a hashtable<pair> inside the hashmap which in essence would be something like hashtable<key> because it would take into account only the key part and just carry along a value member.

But then problems arised.

For example I wanted to implement an exists function that would check whether a pair with a specified key existed in the hashmap. So that would take in a key and check if the key is inside the map. This would be implemented using the hashtable's exists. But the hashtable::exists now takes as input a pair type.

So now I had these alternatives which I don't kinda like.

Create a pair object with the key, and leave the value part uninitialized
Cast the key object to a pair object (like reinterpret_cast(&key)) as the hashtable's functions will use only the key part of the pair in this situation.

The first one creates an unnecessary copy. And with the second one key's address may not be equal to pair's object address. Although I believe I can know for sure the key's address taking into account that I can calculate

(&pair.key) - (&pair)

And using that I could do proper casts to pass the key as a pair.

Any ideas for alternatives?

Solution

If you look at existing implementations of hash map like google::dense_hash_map here (I take this as example because I believe it is easier to read than STL code like std::unordered_map), you will see that the hash map is not simply a templated hash table.

In other words, it is not implemented like:

template <class T>
struct hash_table { ... };

template <class Key, class Value>
using hash_map = hash_table<std::pair<Key, Value>>;

... but like:

template <class Value, class Key> 
struct hash_table { ... };

template <class Key, class Value> 
struct hash_map
{
    using ht = hash_table<std::pair<Key, Value>, Key>;
    ht _ht;
};

Then, in hash_table<Value, Key> you can have insert(const Value&) but also find(const Key&), as this class is aware of all the types.

On the top of that you can implement very easily hash_set. The entire logic will be in your hash_table class, hash_map and hash_set only forward the calls and do some cosmetic stuff for the client of the API.