How to create your own HashMap?

java-hashmapYesterday, while teaching java’s collections framework, One of my student ask me this question “How to create own Hashmap? ”. I answer him verbally about the code and concept, but could not make any example because of insufficient time. Today after finding some spare time, I started writing my own hashmap. Let’s see how we can write own own hashmap?

First, let’s take an overview of how hashtable works. Every entry has a key that has a hash code and a value. Keys must be comparable in some fashion. Many different keys can have the same hash code, though in practice we want this to tend to be true only of keys that are also considered equivalent.

Internally a hashtable stores a set of buckets, typically in a simple array. Each bucket contains 0..N entries, each of which has a key and a value. To find what bucket an entry goes into we generate a numeric hashcode for the key, and determine what bucket index from hashcode mod the number of buckets.

Let’s create an Entry class. We need a key, which can’t change, a value, which can change, and a pointer to next so we can make our array that has 0..N entries in each spot. Something like this should do it:

Now let’s create a HashMap class. The first operation we’ll implement is get. We’ll need to identify what bucket to use, then cycle through the 0..N entries for that bucket to see if any of them have the exact key we are interested in.

If there is nothing at all in the bucket we can just create a new entry and shove it in. If there is already 1..N things there we need to search through them all. If we find one with the exact same key we’ll update it, otherwise we’ll just shove a new entry on the end.
Putting it all together our final hashmap looks like this:

Following is a JUnit test case to verify the functianality.

About the Author

has written 69 posts.

I Love Coding, Analyzing, Designing and doing it the right way. I am obsessed about learn anything new daily and sharing what I have learn each Day. This Blog is journey of my Zeal, going through step by step to the mountain of desire to become prefect. Google Wanna Hire me ?

Copyright © 2019 All rights reserved.
Proudly powered by WordPress. Developed by 7Tech Solutions