+10  Q: 

Hashtable in C++?

I usually use C++ STL map whenever I need to store some data associated with a specific type of value (a key value - e.g. a string or other object). The STL map implementation is based on trees which provides better performance (O(log n)) than the standard array or STL vector.

My questions is, do you know of any C++ "standard" hashtable implementation that provides even better performance (O(1))? Something similar to what is available in the Hashtable class from the Java API.



+4  A: 

Have a look at this blog posting: Comparison of Hash Table Libraries.

+1  A: 

See std::hash_map from SGI.

This is included in the STLPort distribution as well.

Adam Tegen
It may be included in STLPort, but it's still not "standard", as the question sought after. There is no _standard_ class called hash_map; it's called unordered_map instead, and it's in TR1.
Chris Jester-Young
+17  A: 

If you're using a C++ Standard Library with support for TR1 (e.g., GCC 4.0+, or Visual Studio 2008 SP1), then you have access to the <unordered_map> and <unordered_set> headers. These provide classes std::tr1::unordered_map and std::tr1::unordered_set.

Hope it helps!

Edit: I've downvoted all the std::hash_map answers; that's an SGI extension, not really part of the C++ standard. Use the TR1 facilities instead.

Chris Jester-Young
In GCC, you have to use header names <tr1/unordered_map> and <tr1/unordered_set> instead. It's a GCC quirk. :-)
Chris Jester-Young
The VS2008 Feature Pack has been superseded by SP1.
IIRC the VC9 Feature Pack and SP1 tr1::unordered_* implementations came wih release notes warninig of sub-optimal performance. I would assume that this will be fixed eventually.
Thanks, Ferruccio! I've incorporated your fix. (I apologise for misspelling your name in the edit comment, but I don't believe I now have a way to fix that.)
Chris Jester-Young
That answer will have to be updated for C++0x at some point
Alexandre Jasmin
+3  A: 

There is a hash_map object as many here have mentioned, but it is not part of the stl. It is a SGI extension, so if you were looking for something in the STL, I think you are out of luck.

Craig H
+2  A: 

Visual Studio has the class stdext::hash_map in the header <hash_map>, and gcc has the class __gnu_cxx::hash_map in the same header.

Adam Rosenfield
If they have the same interface, it's pretty easy to make an implementation that supports both of them using namespace aliases and some pre-processor work.
Jasper Bekkers
I know, I know, this is deprecated stuff. Not every collegue may be convinced to switch to VS 2008 or install Boost. So here is a good trick on how to get these together:` namespace std { #ifdef __GNUC__ using namespace __gnu_cxx; #elif using namespace stdext; #endif }`
+1  A: 

hash_map is also supported in GNU's libstdc++.

Dinkumware also supports this, which means that lots of implementations will have a hash_map (I think even Visual C++ delivers with Dinkumware).

Ben Collins
It may be widely supported, but it's not "standard", as the questioner asked for. Only the TR1 facilities can be considered standard.
Chris Jester-Young
The point I was making is that if all the compiler vendors support it (or stdlibc++ vendors, as the case may be), then it may be a good enough substitute for "standard". BTW, TR1 isn't "standard" yet. It's accepted for the next standard, which is enough to get vendors to implement it (my point...)
Ben Collins
I think that's just for libstdc++ version >= 4.0?
+7  A: 

If you don't already have unordered_map or unordered_set, they are part of boost.
Here's the documentation for both.

Mark Ransom
Yay for Boost providing _maximal portability_ once again. :-) See for another instance of this.
Chris Jester-Young
+1  A: 

If you have the TR1 extensions available for yor compiler, use those. If not, has a version that's quite similar except for the std:: namespace. In that case, put in a using-declaration so you can switch to std:: later.

+1  A: 

std::tr1::unordered_map, in <unordered_map>

if you don't have tr1, get boost, and use boost::unordered_map in <boost/unordered_map.hpp>