Archived

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

Hash tables

This topic is 6392 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

If you need to have one thing lookup another use hash tables (maps). They are really fast, and only take up a little more memory than linked lists. An example of where to use them is having to find a phone number by someone''s name. You could use a binary search or you could use a map.

Basically a map works by allocating a big buffer. There should be about the number of items you want to put in the map +- 100 or so. Then you have a function that takes whatever kind of data you want to put in, and have it give you a number less than the number of slots in the buffer. Then you put a pointer to that node in the right slot. When you want to look something up just use the same algorithm.

There are different ways to handle 2 strings or whatever that give the same number when you put them through your algorithm. My personal favorit is chaining. That''s where each slot actually has a linked list of all the nodes that have that hash value.

I hope that helps. I may have made the explaination a little brief

Share this post


Link to post
Share on other sites
Blue-lightning sketched out the theory very well, I''ll just give you a real example.

Using the telephone book mentioned above :

You take a table of e.g. 1000 slots and number them 0 to 999.
Every telephone number that ends (or starts, which comes down to the same) with 147 would go in slot 147 and so on. That way you can place all telephone numbers in a table with 1000 slots.
The function that blue lightning mentions is in this case y = x mod 1000
Whenever say 125 478 and 126 478 would be added to the same table, you get a collision. You can resolve collisions by just selecting the next available slot, that way, 126478 would go in 479 if you go by the last numbers.
Or you could provide room for more than one member per slot which is called a bucket.
Or you could link them with pointers in a linked list which is called chaining.

Just to give you a wider picture of what''s possible.


******************************
Stefan Baert

On the day we create intelligence and consciousness, mankind becomes God.
On the day we create intelligence and consciousness, mankind becomes obsolete...
******************************

Share this post


Link to post
Share on other sites