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.

I think you're going to have to ask a more specific question.

What's wrong with the map container provided by your standard library? All of those have optimal performance characteristics.

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.

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?

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.

This may be of some help:
Perfect Hashing

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.

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.

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.