Thunderboltz Thunderboltz - 23 days ago 6
C Question

Implementing a HashMap

How to go about creating a Hashmap in C from scratch ?
What would be the parameters taken into consideration and what how would you test the hashmap as to how good it is ? As in what would be benchmark test cases which you require to run before you say that your hash map is complete.

Answer

Well if you know the basics behind them, it shouldn't be too hard.

Generally you create an array called "buckets" that contain the key and value, with an optional pointer to create a linked list.

When you access the hash table with a key, you process the key with a custom hash function which will return an integer. You then take the modulus of the result and that is the location of your array index or "bucket". Then you check the unhashed key with the stored key, and if it matches, then you found the right place.

Otherwise, you've had a "collision" and must crawl through the linked list and compare keys until you match. (note some implementations use a binary tree instead of linked list for collisions).

Check out this fast hash table implementation:

http://attractivechaos.awardspace.com/khash.h.html

Comments