Implementing a HashMap using a HashTable implementation

Question

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?

std::unordered_set and std::unordered_map are good alternatives :-) — AndyG
– AndyG, Commented Sep 20, 2016 at 19:05

AntiClimacus · Accepted Answer · 2016-09-20 19:10:49Z

1

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.

answered Sep 20, 2016 at 19:10

AntiClimacus

1,4308 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user183833 Over a year ago

In the new hashtable the hashing is still based on the key(?) and it just carries along a value? Then how can one insert a value alone? Nevertheless if hashing is based on the key, they essentially first implement a hash map and using that they can implement a hashtable with a dummy value object? Good one.

AntiClimacus Over a year ago

@user183833 yes, the hashing is always based on the key only. It does not insert the value alone: in insert(const Value&), Value refers to std::pair<Key, Value>, see line using ht = hash_table<std::pair<Key, Value>, Key>.

Collectives™ on Stack Overflow

Implementing a HashMap using a HashTable implementation

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related