Link to home
Start Free TrialLog in
Avatar of Axter
AxterFlag for United States of America

asked on

Example code for hash_map

I'm looking for example code that uses hash_map or any other hash template class.
I'm also looking for a good example in which using hash_map makes a big difference versus using std::map.

I don't have any experience using hash code of any kind, and I'm trying to figure out if it is worth brushing up my skills in this area.
It seems to me that for the most part, the std::map class can do the job good enough.

Any and all input would be appreciated.
Avatar of jkr
jkr
Flag of Germany image

Avatar of Axter

ASKER

Thanks for the example jkr, but I already had that link.

I'm really looking for an example where I can see a clear difference between hash_map and std::map.
The example in that link could just as easily used std::map.
>>I'm really looking for an example where I can see a
>>clear difference between hash_map and std::map

The 'clear difference' is that the mapping algorithm is/should be faster. I don't have too much experience in that area either, but the idea of a hashing algorithm is to 'calculate' the target from the input.

>>The example in that link could just as easily used
>>std::map

That's AFAIK the advantage of that type of map - it's so transparent that you can't see any difference...
Avatar of JackThornton
JackThornton

As long as the hash function is reasonable, a hash table is more efficient (i.e. faster insertions and lookups) for situations where there are large numbers of entries (e.g. > 1000) and where the compare-time per element is relatively large (e.g. string compares vs. integer compares). There is no overhead for balancing trees or for worse-case behavior on unbalanced trees, plus less overhead for element-to-element comparisons (as must be done in traversing trees). For smaller sets of elements, a hash-map may not pay any dividends over the standard black/red-tree maps (in much the same way as, if you only have 4 or 5 elements, you may as well keep an array and do a linear search instead of creating a map).

The major drawback with hash tables is that you cannot get an ordered set of elements back out of one - in other words, no forward or reverse iterator to go from begin() to end(). In many cases, e.g. symbol tables, this isn't a problem (unless, of course, you want to print out a list of symbols, in alphabetical order, at the end).

As with any other programming tools, select the appropriate one for the specific job at hand. It wouldn't hurt to brush up on the hash maps. Knowing and using only a single type of container is like having only one medium-size philips screwdriver and trying to use it to repair eyeglasses and pry 18-inch bolts out of battleships.

- jack
Avatar of Axter

ASKER

So am I correct in saying that the way you use the hash_map class is no difference then the way you use std::map???
And the only difference is in how fast one-vs-the-other for a particular requirement.

I just notice that the hash_map does not have its data sorted, where as the std::map has its data sorted.
>>So am I correct in saying that the way you use the
>>hash_map class is no difference then the way you
>>use std::map???

AFAIK - yes. Just the mapping algorithm is different...
Avatar of Axter

ASKER

I've seen you post this before, but never bothered to ask.
What is AFAIK?
That's correct - you use a hash_map just as you would a standard map, you just can't use iterators. The only cavaet is that there are a limited number of types for which hash functions have been defined; if you want to use other types (e.g. unicode strings), then you need to provide your own hash function in the template definition. Hash functions are used to create a simple index from an input; e.g. turning the string "Don't Panic - I have a towel" into, say, 42. Hash functions should be relatively quick (e.g. not take as much time to calculate as several comparisons would take) and generate fairly "random" outputs from inputs so as to reduce the number of collisions.
AFAIK = As far as I know
At least, that's what it means as far as I know   ;-)
At least, that's what it means as far as I know   ;-)
Avatar of Axter

ASKER

>>AFAIK = As far as I know

IMHO, I think before you know it, the internet is going to have so many acronyms & symbols, that a newbie is going to need a special dictionary in order to carry out a normal conversation. :- ) :-0 ;-}
Avatar of Axter

ASKER

If you don't mind jkr, I'll post a seperate 50pt question for you, and award this one to JackThornton.
Avatar of Axter

ASKER

JackThornton,
>>generate fairly "random" outputs from inputs so as to
>>reduce the number of collisions.
This part I don't understand.  I know what the collision problems are with hash, but I don't understand how random outputs would reduce the number of collisions.
Avatar of Axter

ASKER

Wouldn't the goal of a hash_map be to produce an evenly spaced set of keys?
I would think that random outputs would reduce the ability to produce evenly spaced keys.
Well, "random" was a poor choice of words. Obviously, the function must map a particular input uniquely to a particular output, or the whole thing would fail. What I meant to say was that the function should be able to generate outputs that spread evenly among the desired index range (i.e. size of hash table) for the types of inputs provided. You don't want functions that tend to "cluster" around a small number of values over the range of expected inputs. For example, if you were to hash a string using only the value of the first character, it would be a very fast function, but you would only generate (most likely fewer than) 96 index values, so you would get lots and lots of collisions. Alternately, you could build a CRC from the entire string, which would probably give a good spread of values, but be computationally expensive enough to ruin the benefits of hashing. Both of these are extreme examples of poorly chosen algorithms - it's probably pretty simple to come up with reasonable algorithms for any input type, it just means you have to think about the problem a little.
ASKER CERTIFIED SOLUTION
Avatar of JackThornton
JackThornton

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
Avatar of Axter

ASKER

>>I seem to be babbling now, so I'll sign this one off.

When the info is good, it's not babbling.

Thanks, this clear up somethings for me.  

I wounder what is the likely hood that hash_map/hash_set will get added to the ANSI C++ standards.