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?

Gart · Accepted Answer · 2009-10-08 10:27:33Z

8

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.

answered Oct 8, 2009 at 10:27

Gart

2,3363 gold badges28 silver badges37 bronze badges

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

3 Comments

sbi Over a year ago

Note that there are two different versions of the (non-standard) std::hash_map around. I'd use std::tr1::unordered_map which is bound to become the next standard version's std::unordered_map.

Michael Ekstrand Over a year ago

std::hash_map is an SGI extension. It's available in G++ as well, but in a different namespace (__gnu_cxx, I believe).

sbi Over a year ago

But there's also a Dinkumware version. (I think it's now in the stdext namespace or something like it, but it used to be in the std namespace so there's versions of their library out there where it is.)

Kylotan · Accepted Answer · 2009-10-08 10:36:13Z

7

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.

answered Oct 8, 2009 at 10:36

Kylotan

18.5k7 gold badges50 silver badges75 bronze badges

Comments

Cat Plus Plus · Accepted Answer · 2009-10-08 14:59:40Z

4

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.

answered Oct 8, 2009 at 14:59

Cat Plus Plus

131k27 gold badges205 silver badges226 bronze badges

1 Comment

Navaneeth K N Over a year ago

Thanks for the reply. This looks promising. I will give a try.

Pete Kirkham · Accepted Answer · 2009-10-08 10:21:46Z

2

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

answered Oct 8, 2009 at 10:21

Pete Kirkham

49.5k5 gold badges96 silver badges176 bronze badges

Comments

Skizz · Accepted Answer · 2009-10-08 10:37:26Z

2

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.

edited Oct 8, 2009 at 10:37

answered Oct 8, 2009 at 10:14

Skizz

71.4k10 gold badges75 silver badges109 bronze badges

1 Comment

Joe Over a year ago

While not truly standard, nearly every compiler the last 5 years implements one (though MSVC and G++ have slightly different semantics.) Preference should be on unordered_map or the equivalent boost container.

Jerry Coffin · Accepted Answer · 2009-10-08 14:45:14Z

2

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.

answered Oct 8, 2009 at 14:45

Jerry Coffin

494k83 gold badges656 silver badges1.2k bronze badges

3 Comments

sbi Over a year ago

In fact, often a std::vector<std::pair<K,V> > competes with a std::map<K,V>. I think there's an item for this in Meyers' "Effective STL" book (amazon.com/gp/product/0321334876).

Jerry Coffin Over a year ago

There is, but it only competes under rather specific circumstances. For fast lookups, the vector has to be sorted. It works nicely if things work in phases, where you collect all the data, then you can sort it, then you do searches (but rarely insert or delete after you sort). Something like map is better if you intermix insertions, deletions, and searches.

sbi Over a year ago

@Jerry: Yes, you summarized it very nicely.

Collectives™ on Stack Overflow

Creating generic hashtables - C++

6 Answers 6

3 Comments

Comments

1 Comment

Comments

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

3 Comments

Comments

1 Comment

Comments

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related