Menu
How to go about creating a Hashmap in C from scratch as is present in C++ STL?
What parameters would be taken into consideration and how would you test the hashmap? As in, what would the benchmark test cases be which you would run before you could say that your hashmap is complete?
361
There are two common styles of hashmap implementation: Separate chaining: one with an array of buckets (linked lists) Open addressing: a single array allocated with extra space so index collisions may be resolved by placing the entry in an adjacent slot.
hashmap. c source code is available under the MIT License.
Hashmap uses the array of Nodes(named as table), where Node has fields like the key, value (and much more). Here the Node is represented by class HashMapEntry. Basically, HashMap has an array where the key-value data is stored. It calculates the index in the array where the Node can be placed and it is placed there.
Whatever may be the size of the data, HashMap almost gives constant time performance for most frequent operations – insertion and retrieval. That's why HashMap is the first choice for the big sized data having requirement of faster retrieval and faster insertion operations.
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:
https://attractivechaos.wordpress.com/2009/09/29/khash-h/
115
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
