hash table c++

[Leon]

What is the best way to implement hash-based container in c++ to have
fast access when there is a huge number of <key,value> pairs? According
to what I've found out and experienced up to now, hash_map is the best?
Does anybody know anything better? Does boot have something better?

Thanks,
Leon

 

[google]

What is the best way to implement hash-based container in c++ to have
fast access when there is a huge number of <key,value> pairs? According
to what I've found out and experienced up to now, hash_map is the best?
Does anybody know anything better? Does boot have something better?

Boost.Unordered
http://www.boost.org/doc/libs/1_37_0/doc/html/unordered.html

Google Sparse Hash
http://goog-sparsehash.sourceforge.net/

Regards,
Anders Dalvander

 

[tni]

It's going to depend on the memory vs. speed tradeoff, which hashmap
will be best for you. The Google sparse/dense hashmap implementations
are quite good (sparse uses little memory, but is a bit slow; dense is
much faster and uses a lot more memory). There is a nice comparison of a
few different ones at:

http://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/

 

[Goran]

What is the best way to implement hash-based container in c++ to have
fast access when there is a huge number of <key,value> pairs? According
to what I've found out and experienced up to now, hash_map is the best?
Does anybody know anything better? Does boot have something better?

Thanks,
Leon

Did you verify that in your situation hash map indeed gives you a
significant performance boost over std::map? I am asking because a lot
of people disregard that simple thing.

 

[Leandro Melo]

Boost.Unorderedhttp://www.boost.org/doc/libs/1_37_0/doc/html/unordered.html

Google Sparse Hashhttp://goog-sparsehash.sourceforge.net/

Besides "fast" access, do you also need that elements are ordered in
the container? Because if you do, a hash table isn't a good option for
you.

Several hash table implementations will provide you an amortized
constant time access. However, you should also consider aspects that
are particular to your context. What is exactly "huge" (in comparison
to memory)? Is that table supposed to have a lot of insertions/
removals? What's the expected behavior for the load factor?

There are two well-known strategies for hash table implementations:
closed-addressing and open-addressing. Most implementations I've seen
around are based on closed-addressing. But if you can estimate the
number of elements in the table (and have contiguous memory) you might
wanna consider open-addressing. Another factor to evaluate is how you
would like to handle collisions.

I implemented a hash table based on open-addressing. Never profiled it
though. If you're interested: http://www.codeproject.com/KB/cpp/stllikeopenhash.aspx