Sign in to follow this  
noNchaoTic

Obvious uses for Hash Tables

Recommended Posts

Is there any obvious instances where Hash tables would become useful for graphics/game engine programming, I only ask as I've read a few articles on data structures for graphics/game and they all seem to implement a class for hash tables, yet fail to identify an instance on which they would be useful. Cheers,

Share this post


Link to post
Share on other sites
Quote:
Original post by noNchaoTic
Is there any obvious instances where Hash tables would become useful for graphics/game engine programming, I only ask as I've read a few articles on data structures for graphics/game and they all seem to implement a class for hash tables, yet fail to identify an instance on which they would be useful.

Cheers,


The purpose of a hash table is efficent look ups, particularly when a large number of records are involved. That's not say they don't have problems.

As for examples, they're commonly use in computer chess games for the transposition table. They can also be used in caching algorithms.

Share this post


Link to post
Share on other sites
Quote:
Original post by noNchaoTic
Is there any obvious instances where Hash tables would become useful for graphics/game engine programming, I only ask as I've read a few articles on data structures for graphics/game and they all seem to implement a class for hash tables, yet fail to identify an instance on which they would be useful.

A simple example, Andrew Glassner's article in Graphics Gems IV. The hash table is used there in order to greatly limit the number of vertex comparisons while computing vertex normals from unstructured list of polygons. (the hash value is calculated from vertex coordinates)

Share this post


Link to post
Share on other sites
Let's say I create a class that handles the creation of textures from files - it loads a .TGA and produces a texture object of some kind, or a GL texnum or something. Now let's say I want to use that texture 50 times. How do I keep from loading the same texture 50 times when I only need it in memory once? A hash table can solve that problem nicely - you hash the filename and use that as the key to look up the texture* or texnum or whatnot.

Share this post


Link to post
Share on other sites
Quote:
Original post by noNchaoTic
With regard to Josh's last post couldn't you use a Set for that?

Set is sorted container and as such tends to be slower than hashed container, if i understand it right.

http://www.sgi.com/tech/stl/HashedAssociativeContainer.html

Share this post


Link to post
Share on other sites
Quote:
Original post by noNchaoTic
Cheers for that everyone appreciated...

With regard to Josh's last post couldn't you use a Set for that?

Yes, but that doesn't dictate the underlying data structure being used. Sets and maps can both be implemented effectively with many different underlying data structures (which data structure would be best will depend on the situation)

Edit: I'm slightly wrong here, depending on how you define 'set' and 'map'. If you're talking specifically about an implementation of a std::set or std::map, then the container must be ordered, so a real hash table couldn't be used.

The underlying data structure might be a tree of some type (likely some kind of balanced binary tree), it could be a hash table, it could be a sorted array, it could even be an unsorted array that must be searched linearly. Hash tables themselves have several variations (open scatter tables, chained hash tables, and so on.) It may even be implemented with a combination of data structures, or be implemented to switch to a different data structure given certain conditions (for example, a very small set might be best implemented as a sorted or unsorted array, but once it gets large enough, the implementation could switch to using a proper hash table)

John B

Share this post


Link to post
Share on other sites
They can be used in collision systems (Ericson, Real-Time Collision Detection). They can be used anywhere where you need fast lookups and fast deletes. Designing good hash algorithms is black magic. Most people just copy them from some place, and those are usually always bad. Classic example is the hash in the C programming language by K&R. A prime example of a terrible hash algorithm, and it is used everywhere because people copy it from the book (and K&R admit it is crap and was only meant to be an example..) If you are just going to copy someone elses hash algorithm I suggest use std::map it will probably be better.

Share this post


Link to post
Share on other sites
Quote:
Original post by noNchaoTic
Cheers for that everyone appreciated...
With regard to Josh's last post couldn't you use a Set for that?
Sure could. You could use std::map (what I generally use), std::list, std::set, std::vector, std::hash_map... or a hundred other ways. I was just trying to give an example where a hash table is very useful since I consider it to be a very efficient way to implement "named resource" lookups like the example I gave.

Share this post


Link to post
Share on other sites
Hash tables are an excellent way to search for duplicates. They can mean the difference between taking 20 minutes with the obvious algorithm, and a couple of seconds using hash tables on a large dataset. This is coming from personal experience.
They're pretty much the fastest way to do what they can do. If you're serious about performance I seriously suggest you learn to use them.

Share this post


Link to post
Share on other sites
Thanks so much for the wealth of information, i've learned the basically really and am just trying to come up with some decent hashing functions for various bits and bobs, it is in indeed black magic, lol

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