Sign in to follow this  

Hashing in gamedev

This topic is 4747 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

In my engine I store nearly all plugins, renderables, ect. in a single tree that allows infinite branches and members on each branch. This is nice because it allows content creators to rather quickly search it for particular resources by using locks and accesskeys on branches. However, on each branch I am currently using Hashtables to store its child branches by string ID, and also hashing its members by string ID. I understand the high memory overhead with hashtables, and I am wondering if the O(1) lookup will be better in the longrun vs. a BST sorted map with O(log(n)). These hashtables will contain many members in the finished engine, despite being broken up by the tree structure, and I am wondering exactly how badly this high overhead will impact the performance compared to a BST sorted map. Finally, which option would you suggest I choose?

Share this post


Link to post
Share on other sites
Quote:
Original post by C-Junkie
er, well....

Profile.

It shouldn't be hard to change later on.

This isn't really helpful currently. I have a very small amount of actual content that I'm using to test the engine, and I would like to know how it will operate under larger amounts. I'm actually more worried about the memory overhead, since I'm positive the hashtable will be faster for the small numbers of members in each hashtable currently. Keys are of a complete random distribution, so there is no opportunity to optimize the hash function.

Share this post


Link to post
Share on other sites
Really, it's probably not a big deal either way. I doubt the memory requirements will be significant when compared to the other memory requirements within the game. Plus, if you structure it in a nice way, you should be able to switch later if you need to as C-Junkie said.

tj963

Share this post


Link to post
Share on other sites
well, if you have 1000000 possible hashkey-values, that doesn't mean that your hashtable has room for 1000000 elements. usually your hashtable is far smaller (i.e.1024), but each hashtable-element does not point directly to the indexed element, but to a "bucket" which contains all elements of this index.

i.e.
element a = hashkey 1234001 will be inserted in bucket 1 (1234001 mod 1000)
element b = hashkey 1234011 will be inserted in bucket 11
element c = hashkey 9934001 will be inserted in bucket 1, too

a bucket is usually just a linked list, which will then be searched linearly, or a bst.

hth
Chris

Share this post


Link to post
Share on other sites
O(1) lookup is best case. Poor key selection will degrade performance, obviously. But a BST tree isn't too terrible either, with an average performance of O(log n) when accessing elements.

I suggest you don't change it from what you have unless there is a problem.

Share this post


Link to post
Share on other sites
Quote:
I have a very small amount of actual content that I'm using to test the engine, and I would like to know how it will operate under larger amounts.

Why not test it out, then? Generate a large amount of random entries and attach them all to the data structure, and see how it holds up. Then you'll be able to see for yourself.

Share this post


Link to post
Share on other sites

This topic is 4747 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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