Link to home
Start Free TrialLog in
Avatar of w00te
w00teFlag for United States of America

asked on

Hash Map Usage

Hey guys, long time no see!

First of all... can someone tell me if hash_maps are actually a part of STL, and if not, where I get/how I include the files to use them?  I've used them back in university

Can someone provide me with some short sample code for using a hash_map (a simple, but full/compileable file)?

Thanks :D

-John
ASKER CERTIFIED SOLUTION
Avatar of Infinity08
Infinity08
Flag of Belgium image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
for many problems a normal std::map would also be a good and easy-to-use choice.

you can add entries by statements like

    mymap[key] = value;

Sara
As [sarabande] pointed out - the std::map class in STL has exactly the hash table functionality of storing values according to the key.

Boris
>> exactly the hash table functionality of storing values
A map is not a hash map. They have the same basic functionality (in terms of storing key/value with retrieval by key) but don't confuse them. They are implemented very differently and have very different runtime complexities in terms of speed and memory usage. There are also functional difference, for example items in a map are stored in a way that allow for easy retrieval in a sorted order, this is not possible with a hash map.
Avatar of w00te

ASKER

Thanks for the answers guys, the SGI page was exactly what I was looking for.  Got a nice example coded on our system now :)  The google pages were an interesting read too!

I just needed something with a little more speed than a normal map (as evilrix pointed out in the last comment) and wasn't sure how to get access to the C++ implementation of a hashmap.  This should work perfectly :)
a std::map has logarithmic speed for searches. it normally is implemented as balanced sorted tree (that's why you get a sorted list for free when iterating). std::map is relatively slow for inserts when it requires new balancing.

the performance of a hash_map is highly dependent on the goodness of the hash algorithm on the given keys and on the relation of number of keys to number of hash keys. for example if you have string keys which all begin with same prefix "xxxxx_" you may get very lousy performance cause too many strings were mapped to the same hash. you normally get good performance with an equal-distributed or normal-distributed numeric key.

so you can't say that hash_map is faster than std::map before you measured it. but you can make more mistakes with hash_map than with std::map.

Sara
Avatar of w00te

ASKER

Hi Sara,

I understand, I've actually done quite alot with hashing algorithms in other languages - It's just been a while (college) since I touched them in C++, and we run on some proprietary OS's here which I was having trouble finding the headers on.

It turns out that the OS we compile to didn't have the header, but the unix system we cross-compile from did and it was messing with me a little.  It's all good now though :)  I worked it out once I saw the sgi page.

I apprecaite all the insight though :D  Have a good day!

-w00te