Sign in to follow this  
Aressera

Hash Map implementation

Recommended Posts

I want to implement my own version of a hash map for use in my physics engine, but I'm not quite sure how this would be done. I'm aware of how the data structure behaves and I've already implemented a hash table, so I really just need a push in the right direction as far as the design is concerned.

Share this post


Link to post
Share on other sites
What's wrong with the map container provided by your standard library? All of those have optimal performance characteristics.

Share this post


Link to post
Share on other sites
I'd rather gain the experience of implementing the data structure myself, and to also reduce the dependencies of my library on 3rd party software.

I just need clues on how to implement what is essentially an adjacency graph.

Share this post


Link to post
Share on other sites
Quote:
Original post by Aressera
I'd rather gain the experience of implementing the data structure myself, and to also reduce the dependencies of my library on 3rd party software.
Out of curiosity, what language are you using?

Share this post


Link to post
Share on other sites
C++, but don't just tell me to use std::map like I know you will. I need to write my own implementation because it needs to be very fast and specialized because I'm using it in collision detection and will be doing 10000+ queries a frame.

Share this post


Link to post
Share on other sites
Quote:
Original post by Aressera
C++, but don't just tell me to use std::map like I know you will. I need to write my own implementation because it needs to be very fast and specialized because I'm using it in collision detection and will be doing 10000+ queries a frame.


And why exactly is std::map slow? It has log n performance, and has no problem performing tens of millions of queries per second.

Unless you know exactly where the bottleneck lies, you cannot fix the problem.

BTW: did profiler indicate that std::map is the bottleneck, or is this just a belief? If std::map is the real bottleneck, then optimize your collision detection to minimize queries.

Share this post


Link to post
Share on other sites
Actually, it looks like this is related to the question posed here (correct me if I'm wrong, OP). IMO the other thread provides a lot more useful information about the problem in question, and I'm guessing you'll get more useful (and relevant) feedback there than in this thread.

Share this post


Link to post
Share on other sites
Quote:
Original post by Aressera
C++, but don't just tell me to use std::map like I know you will. I need to write my own implementation because it needs to be very fast and specialized because I'm using it in collision detection and will be doing 10000+ queries a frame.


I wouldn't tell you to use std::map... thats because std::map isn't a hash table.

std::map is a balanced red-black binary tree, which like a hash table is in a category of data structures called dictionaries.

The standard C++ library doesn't have a hash table implementation. hash_map (which is a hash table) is offered as an extension to the C++ standard library and depending on the tools you're using may or may not be available to you. For example, I know that with the latest OS X C++ sdk hash_map is available.

The claim that std::map is slow has some merit. This is because search and insert in a binary tree takes O(log n) time whereas for a hash table search and insert are O(1) (thats in the case with no collisions ... the average case is something good as well, but I can't remember what it is). But like a poster before be said, you won't know if this actually matters until you profile your application and identify the slow spots.

Your question is awfully broad so the only suggestion we can offer is "google" [grin] ... or a good data structures book (does CLRS mean anything to you yet?). But I can tell you that a hash table isn't terribly daunting to code once you get the few core concepts down. Just so you know, a good hash table depends heavily on a damn good hashing function.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Actually, it looks like this is related to the question posed here (correct me if I'm wrong, OP). IMO the other thread provides a lot more useful information about the problem in question, and I'm guessing you'll get more useful (and relevant) feedback there than in this thread.


you would be correct, but the reason for this thread is that I need an explanation of how one would go about implementing a hash map, not how the resulting system would be integrated into my physics code. I've already implemented a hash table so I have a grasp of how they work, just not how they would be extended to function as a map.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
I think you're going to have to ask a more specific question.


Share this post


Link to post
Share on other sites
Quote:
Original post by Aressera
I've already implemented a hash table so I have a grasp of how they work, just not how they would be extended to function as a map.


Huh? You perform "map lookup" by hashing the key, finding the key-hash in the table, verifying that the key matches and returning the value. What's the problem?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this