## Experiment (Lookup vs Brute Force Calculate)

Anything and everything that's related to OGRE or the wider graphics field that doesn't fit into the other forums.
jjp
Posts: 597
Joined: Sun Jan 07, 2007 11:55 pm
Location: Cologne, Germany
Contact:

### Re: Experiment (Lookup vs Brute Force Calculate)

jacmoe wrote:Yes, but is hash_map not the only map not using a tree?
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.
0 x
Enough is never enough.

stealth977
Gnoll
Posts: 638
Joined: Mon Dec 15, 2008 6:14 pm
Location: Istanbul, Turkey

### 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...

0 x
Ismail TARIM
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
Contact:

### Re: Experiment (Lookup vs Brute Force Calculate)

jjp wrote:
jacmoe wrote:Yes, but is hash_map not the only map not using a tree?
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.
Yes, of course. I think I was mostly referring to the STL.
Looking forward to when they get the cork out and actually release C++1x
0 x
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.

jjp