Creating generic hashtables - C++

Question

.NET framework has got a Dictionary<TKey,TValue> class which is implemented as hash tables and provides data retrieval in constant time (O(1)). I am looking for a similar implementation in C++. I know about std::map but in this data retrieval takes logarithmic time. Is there any good hash table implementation in C++ which will retrieve data in constant time?

If I am writing my own, how will I calculate hash code for the key? Like .NET, I thought of having GetHashCode() method on types.

template<typename TKey,typename TVal>
class Dictionary
{
public:
   void Add(TKey key, TVal val){
       int hashCode = key.GetHashCode();
       /* .... */
   }
}

If I did like the above and the given key type doesn't have GetHashCode() method, compiler will throw error. But this method won't work when key is primitive types like int. I may need to write a wrapper for int by providing GetHashCode.

I wonder what is the C++ way of implementing this?

Any thoughts?

Answer 1

Perhaps, std::hash_map?

Note that this isn't part of the standard STL library specifications but is often available. It's in the MS libraries and the SGI libraries (as the link suggests) and in STLport.

Answer 2

In C++ you would pass a the type of a functor which has the hash function as a type parameter to the template.

Answer 3

Also, check out C++ Technical Report 1 for std::tr1::unordered_map if a strict adherence to C++ standard is required.

Actually std::hash_map is not C++ standard but widely used anyway.

Answer 4

boost::unordered_map is probably your best and most widely portable solution at this point, if you don't have a TR1 implementation to hand.

Answer 5

Assuming you're using VS 2008 with the Feature Pack or service pack 1 installed, you have an implementation of TR1, which includes TR1::unordered_map.

OTOH, unless you're really creating a huge collection, chances are that std::map will be more competitive than you expect. In my tests, it's pretty common for the two to nearly tie, and std::map can and does come out faster fairly frequently.

Answer 6

If you're looking for ready-to-use implementation, then apart from STL/TR1 and Boost hashmaps, there's also google-sparsehash (it contains two implementations - one optimised for space and one optimised for speed).

If you want to write your own, then GetHashCode could be implemented as a separate functor, e.g.

template < typename TKey, typename TValue, typename THash = someDefaultHash<TKey> >
class Dictionary
{
public:
   void Add(TKey key, TVal val){
       int hashCode = THash()(key);
       /* .... */
   }
}

That's how SGI's hash_map does it.