Which is faster? a hash Table or a std::map lookup table

[Jack]

I would like to map D3DXVECTOR3 points to
boolean values. They are used as markers of obstacles to be used in
pathfinding. I wonder which one is
faster? a hash table or std::map lookup table
for example
if Point(10,10,10) is an obstacle, I want to look it
up quickly and returns false.... or vice versa..
Thank in advance for any suggestion...
Jack

[David Webber]

Post by Jack
I would like to map D3DXVECTOR3 points to
boolean values. They are used as markers of obstacles to be used in
pathfinding. I wonder which one is
faster? a hash table or std::map lookup table
for example
if Point(10,10,10) is an obstacle, I want to look it
up quickly and returns false.... or vice versa..
Thank in advance for any suggestion...

My own feeling (and it is no more than that) is that if the table is large,
then you should be using something like std:map.

If it is small, then you shouldn't really care about speed as it is unlikely
to make a significant difference.

Dave

[Ben Voigt [C++ MVP]]

std::map is a hash table in most compiler libraries, I believe.

Although for your example, you probably want to optimize nearest-neighbor
searching and I've heard there are much better data structures for that.

Post by Jack
I would like to map D3DXVECTOR3 points to
boolean values. They are used as markers of obstacles to be used in
pathfinding. I wonder which one is
faster? a hash table or std::map lookup table
for example
if Point(10,10,10) is an obstacle, I want to look it
up quickly and returns false.... or vice versa..
Thank in advance for any suggestion...
Jack
__________ Information from ESET NOD32 Antivirus, version of virus
signature database 4498 (20091011) __________
The message was checked by ESET NOD32 Antivirus.
http://www.eset.com

__________ Information from ESET NOD32 Antivirus, version of virus signature database 4498 (20091011) __________

The message was checked by ESET NOD32 Antivirus.

http://www.eset.com

[Ulrich Eckhardt]

Post by Ben Voigt [C++ MVP]
std::map is a hash table in most compiler libraries, I believe.

No, it's usually a tree. A hash table doesn't satisfy the complexity
guarantees for various operations, even though it performs better on
average.

Uli

[Stephan T. Lavavej [MSFT]]

std::map's logarithmic complexity guarantee is just one of several reasons
why it can't ever be implemented with a hash table. Among the others are
the facts that it doesn't require a hash function (only less-than) and it
sorts its keys (as an ordered associative container).

Stephan T. Lavavej
Visual C++ Libraries Developer

Post by Ulrich Eckhardt

Post by Ben Voigt [C++ MVP]
std::map is a hash table in most compiler libraries, I believe.

No, it's usually a tree. A hash table doesn't satisfy the complexity
guarantees for various operations, even though it performs better on
average.
Uli
--
C++ FAQ: http://parashift.com/c++-faq-lite
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932

[Ulrich Eckhardt]

Post by Jack
I would like to map D3DXVECTOR3 points to
boolean values. They are used as markers of obstacles to be used in
pathfinding. I wonder which one is faster? a hash table or std::map
lookup table for example if Point(10,10,10) is an obstacle, I want
to look it up quickly and returns false.... or vice versa..

The term "faster" doesn't apply. std::map provides some guarantees
concerning the lookup time based on the number of elements. A hash table
(like e.g. those supplied in TR1) can provide a better lookup time on
average, but it has a worse lookup time in worst-case scenarios.

Use a std::map unless you have measured that the lookup speed is not
sufficient.

Uli

[Jack]

Hi guys,
Thanks for all of the advices, I'll take them into a/c.
Thanks
Jack