Within the STL? Well, until C1X all map-like data structure implementations in the STL use trees (although they probably could use something else if it gave the same complexities for operations as trees do). But that wasn't the point. The point was that it is not true to say map = tree. Repeating myself: a map (or associative array) is an abstract data structure that can be implemented in a number of ways. Hashing, search trees, skip lists.. and probably there are even more exotic ways to do it.jacmoe wrote:Yes, but is hash_map not the only map not using a tree?
Experiment (Lookup vs Brute Force Calculate)
-
- Silver Sponsor
- Posts: 597
- Joined: Sun Jan 07, 2007 11:55 pm
- Location: Cologne, Germany
- Contact:
Re: Experiment (Lookup vs Brute Force Calculate)
Enough is never enough.
- stealth977
- Gnoll
- Posts: 638
- Joined: Mon Dec 15, 2008 6:14 pm
- Location: Istanbul, Turkey
- x 42
Re: Experiment (Lookup vs Brute Force Calculate)
Ok guys, you are right in theory its my mistake to confuse my own requirements with the general requirements.
I checked std's implementation again and it uses vector buckets with the hashmap and thats fine with small hashmaps, the confusion was that where i need hashmaps, those maps are huge in size compared to general use. So, using basic buckets was not an option, i guess that experience caused the confusion...
Anyway, hashmaps are only O(1) in ideal cases (am i wrong again?) since usually there are not one to one correspondence between hash value and the bucket, there can be far too less buckets compared to number of available hashes, in that case, each bucket hold a number of key/value pairs per a fixed number of hashes. Which means O(1) to find bucket and O(n) to find the correct pair in the bucket.
An example:
lets say there are 1024*1024 possible hashes and our hashmap uses 1024 buckets. And lets say you insert 4096 pairs into hashmap, which means an avarage 4 pairs per bucket, the search will have an avarage O(1) + O(4) = O(5) steps (the first one to find bucket, the others to find the correct pair in the bucket)
And of course thats if the pairs inserted are distributed equally by the hash, there can be 1024 items in one bucket and the rest distributed to other buckets...in which case lookup for a key can take 1025 iterations...
To avoid such cases (in crowded hashmaps), trees are used as buckets and thats how i use them due to my projects' requirement of crowded hashmaps...
Sorry about my confusion again...
I checked std's implementation again and it uses vector buckets with the hashmap and thats fine with small hashmaps, the confusion was that where i need hashmaps, those maps are huge in size compared to general use. So, using basic buckets was not an option, i guess that experience caused the confusion...
Anyway, hashmaps are only O(1) in ideal cases (am i wrong again?) since usually there are not one to one correspondence between hash value and the bucket, there can be far too less buckets compared to number of available hashes, in that case, each bucket hold a number of key/value pairs per a fixed number of hashes. Which means O(1) to find bucket and O(n) to find the correct pair in the bucket.
An example:
lets say there are 1024*1024 possible hashes and our hashmap uses 1024 buckets. And lets say you insert 4096 pairs into hashmap, which means an avarage 4 pairs per bucket, the search will have an avarage O(1) + O(4) = O(5) steps (the first one to find bucket, the others to find the correct pair in the bucket)
And of course thats if the pairs inserted are distributed equally by the hash, there can be 1024 items in one bucket and the rest distributed to other buckets...in which case lookup for a key can take 1025 iterations...
To avoid such cases (in crowded hashmaps), trees are used as buckets and thats how i use them due to my projects' requirement of crowded hashmaps...
Sorry about my confusion again...
Ismail TARIM
Ogitor - Ogre Scene Editor
WWW:http://www.ogitor.org
Repository: https://bitbucket.org/ogitor
Ogitor - Ogre Scene Editor
WWW:http://www.ogitor.org
Repository: https://bitbucket.org/ogitor
- jacmoe
- OGRE Retired Moderator
- Posts: 20570
- Joined: Thu Jan 22, 2004 10:13 am
- Location: Denmark
- x 179
- Contact:
Re: Experiment (Lookup vs Brute Force Calculate)
Yes, of course. I think I was mostly referring to the STL.jjp wrote:Within the STL? Well, until C1X all map-like data structure implementations in the STL use trees (although they probably could use something else if it gave the same complexities for operations as trees do). But that wasn't the point.jacmoe wrote:Yes, but is hash_map not the only map not using a tree?
Looking forward to when they get the cork out and actually release C++1x
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
-
- Silver Sponsor
- Posts: 597
- Joined: Sun Jan 07, 2007 11:55 pm
- Location: Cologne, Germany
- Contact:
Re: Experiment (Lookup vs Brute Force Calculate)
That is correct If the hash map gets too crowded it won't perform that good any more. In this case the hash map may resize itself, for example. Which obviously isn't for free either, but if you do amortized analysis you end up again with lookup/insert in O(1). In other words: while resizing the hash map is costy it only has to happen rarely, for example whenever the hash map is half full it could double it's size.. pretty much like a std::vector. In the end it really depends on the use case if a tree-based or a hashing-based map is the better choice.stealth977 wrote:Anyway, hashmaps are only O(1) in ideal cases (am i wrong again?)
Enough is never enough.