Archived

This topic is now archived and is closed to further replies.

_johan

hash tables

Recommended Posts

Im having some trouble figuring out how hash tables work. Are the elements of the hash table array supposed to be nodes themselves? or should just HashTable[index] point to one? Code for my question: HashTable[index] = pNode OR HashTable[index]->next = pNode Maybe theyre both wrong... heh

Share this post


Link to post
Share on other sites
How you do it is up to you. A hash table is an abstract concept and there are 101 ways to implement it. The only real constant is that a hash function operates on your data in order to find a space to store and retrieve the data quickly. Some implementations don''t need nodes, so it''s not a question that can be easily answered

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]

Share this post


Link to post
Share on other sites
Just to confuse you even further (sorry) Hash tables might not always be the best course of action because processors are becomming faster the hit taken when retrieving the Hash table entry from RAM to cache can be greater than actually working out the value at run time.

If you only use one or 2 accesses from the table every program loop then you might be better off just calculating the var instead.

Just some food for thought.

/* Ignorance is bliss, then you go and spoil it by learning stuff */

Share this post


Link to post
Share on other sites
Typically you use a Hash table to store data structures that are indexed by a unique key value thats used as its hash code. A lot of times, the information can''t be determined by a simple calculation. If you have a string table, knowing the name of the string won''t tell you its value.

You can implement a hash table using an array. Google will probably offer better information on how to implement it.


University is a fountain of knowledge, and students go there to drink.

Share this post


Link to post
Share on other sites