Obvious uses for Hash Tables
Author
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,
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.
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)
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.
Author
Cheers for that everyone appreciated...
With regard to Josh's last post couldn't you use a Set for that?
With regard to Josh's last post couldn't you use a Set for that?
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
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
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.
Quote:Original post by noNchaoTicSure 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.
Cheers for that everyone appreciated...
With regard to Josh's last post couldn't you use a Set for that?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
