Hash map, string compares, and std::map?

Question

First off, I would like to make a few points I believe to be true. Please can these be verified?

• A hash map stores strings by converting them into an integer somehow.
• std::map is not a hash map, and if I'm using strings, I should consider using a hash map for memory issues?
• String compares are not good to rely on.

If std::map is not a hash map and I should not be relying on string compares (basically, I have a map with strings as keys...I was told to look up using hash maps instead?), is there a hash map in the C++ STL? If not, how about Boost?

Secondly, Is a hash map worth it for [originally] an std::map< std::string, non-POD GameState >?

I think my point is getting across...I plan to have a store of different game states I can look up and register into a factory. If any more info is needed, please ask.

Thanks for your time.

Answer 1

I don't most of your points are correct.

• there is no hash map in the current standard. C++0x introduces unordered_map, who's implementation will be a hash table and your compiler probably already supports it.

• std::map is implemented as a balanced tree, not a hash table. There are no "memory issues" when using either map type with strings, either as keys or data.

• strings are not stored as numbers in either case - an unordered_map will use a hashing function to derive a numeric key from the string, but this is not stored.

• my experience is that unordered_map is about twice the speed of map - they have basically the same interface, so you can try both with your own data - whenever you are interested in performance you should always perform tests your self with your own real data, rather than depending on the experience of others. Both map types will be somewhat sensitive to the length of the string key.

Assuming you have some class A, that you want to access via a string key, the maps would be declared as:

map <string, A> amap;
unordered_map <string, A> umap;

Answer 2

A hash map will typically have some integral representation of a string, yes.

std::map has a requirement to be sorted, so implementing it as a hash table is unlikely, and I've never seen it in practice.

Whether string comparisons are good or bad depends entirely on what you're doing, what data you're comparing, and how often. If the first letter differs then that's barely any different from an integer comparison, for example.

You want unordered_map (that's the Boost version - there is also a version in the TR1 standard library if your compiler has that).

Is it worth it for game states? Yes, but only because using an unordered_map is simple. You're prematurely worrying about optimisations at this stage. Save the worries over access patterns for things you're going to look up thousands of times a second (ie. when your profiler tells you that it's a problem).

Answer 3

I made a benchmark that compares std::map with boost::unordered_map. My conclusion was basically this: If you do not need map-specific things like equal_range, then always use boost::unordered_map. The full benchmark can be found here