Advertisement

Hash tables

Started by June 17, 2000 03:49 AM
1 comment, last by Mr Cucumber 24 years, 6 months ago
Could anyone please explain hash tables to me. Pros and cons and if it''s no to much how to implement and use them.
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
For a good time hit Alt-F4! Go ahead try it, all the cool people are doing it.
Advertisement
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...
******************************
******************************StrategicAllianceOn the day we create intelligence and consciousness, mankind becomes God.On the day we create intelligence and consciousness, mankind becomes obsolete...******************************

This topic is closed to new replies.

Advertisement