CODEWITHSUNDEEP
c++templateshashruntimehashtable
Alfred Zhong
Alfred Zhong

Reputation: 7091

Implementing a C++ hashtable class using template

I am trying to implement a hashtable in C++ that sort of like the Java version

I would like it has the form of 

template <class Key, class Value> 
class hashtable {
...
}

Soon enough I notice that I need to somehow convert Key into a number, so that I can use the simple hash function 

int h(int hashkey) { 
    return hashkey%some_prime;
}

But the headache is, Key type is only known at run time. Is it possible to check what type Key is on run time in C++. Or I have to create this hashtable class with different type manually? That is easier to do but ugly. Anyone know an elegant solution?

Upvotes: 1

Views: 7836

Answers (3)

user1252446
user1252446

Reputation:

If you would like try to implement a "generic" one, perhaps you can start with a skeleton much like this: 

template <class T, class K>
struct HashEntry {  // you would need this to deal with collision
    T curr;
    K next;
}

template <class V, size_t n>
class HashTable {
    void insert(V v)
    {
        ...
        size_t idx = v->getHashCode(n);
        ...
    }
private:
    HashEntry <V> table_[n];

}

It is usually instantiated with some pointer type, to figure out where a pointer should go, it requires the type implement member function "getHashCode" ...

Upvotes: 1

StoryTeller - Unslander Monica
StoryTeller - Unslander Monica

Reputation: 170221

C++ templates are usually duck typed, meaning that you can explicitly cast to an integeral type in the template, and all types that implement the appropriate conversion can be used as a key. That has the disadvantage of requiring that the classes implement the conversion operator in such a fashion that the hash function will be decent, which is asking for a lot.

You could instead provide a function template

template<typename T> int hash (T t);

Along with specializations for the built in types, and any user that wants to use a custom class as key will just have to provide his own specialzation. I think this is a decent approach.

Upvotes: 3

Charles Salvia
Charles Salvia

Reputation: 53339

You seem to have a few misunderstandings. Key type is known at compile time - that's the whole point of using templates. Secondly, there is really no such thing as a completely generic hash function that will work on any type. You need to implement different hash functions for different types, using function overloading or template specialization. There are many common hash functions used for strings, for example.

Finally, C++11 includes a standard hash table (std::unordered_map) which you can use instead of implementing your own.

Upvotes: 2

Related Questions