Solved

Hash Map Usage

Posted on 2011-02-15
9
1,136 Views
Last Modified: 2012-05-11
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
0
Comment
Question by:w00te
  • 2
  • 2
  • 2
  • +3
9 Comments
 
LVL 53

Accepted Solution

by:
Infinity08 earned 250 total points
ID: 34896703
>> First of all... can someone tell me if hash_maps are actually a part of STL

No, they are an extension that several platforms have made available (including popular compilers like GNU C++ and Visual C++).


>> where I get/how I include the files to use them?

Depends what compiler you are using ... ?


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

If you're using the SGI implementation, then the reference page for it will help (it includes sample code) :

        http://www.sgi.com/tech/stl/hash_map.html
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 250 total points
ID: 34896962
Google have an excellent implementation of various hash map containers. They are portable, working on Windows and Linux and are available as packages on most Linux platforms.

http://google-sparsehash.googlecode.com/svn/trunk/doc/index.html
0
 
LVL 33

Expert Comment

by:sarabande
ID: 34896970
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
0
 
LVL 11

Expert Comment

by:DeepuAbrahamK
ID: 34897008
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 1

Expert Comment

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

Boris
0
 
LVL 40

Expert Comment

by:evilrix
ID: 34897494
>> 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.
0
 
LVL 12

Author Closing Comment

by:w00te
ID: 34897943
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 :)
0
 
LVL 33

Expert Comment

by:sarabande
ID: 34899217
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
0
 
LVL 12

Author Comment

by:w00te
ID: 34899605
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
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
TTimer no longer functioning 7 84
how to understand recursion 12 218
returning a dereferenced pts in C++ 10 141
Writing a parser for java language 4 71
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

914 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now