How to implement your own HashMap in java?

Introduction

In this post we will create our own custom HashMap as an exercise to reinforce the concepts used in java.util.HashMap. We will be using a simple implementation where the key will be a String object and value will be an Integer object. After that we will see why we picked String as a key? Is there something special about String class? What if we want to use our own custom Object’s instances as keys in our HashMap.

Underlying Data-Structures

We will be using a simple array as an underlying data structure, commonly known as buckets in Map context. Each index of the array will be a bucket and each buckets can hold one or more Key-Value Pairs, commonly knows as Entries.

In actual java.util.HashMap, Entry is an interface which is implemented by Static Node class but we don’t need to worry too much about Object Oriented Design here as our primary focus is to learn and implement the basics of HashMap. So, we will directly create an Entry class which is actually a Linked List node.

If you don’t know how a Linked List works, you must read Singly Linked List tutorial before continuing any further.

Entry<Key, Value>



API

Our intention here is not to replicate what java.util.HashMap does as that is already an excellent piece of work. What we are trying to achieve here to simplify the API enough, so that we could quickly get an idea about how it all works.

So, Our HashMap will allow two basic functions:

 

Implementation

The put(key, value) method

When we wish to insert a key value pair into our map, we create a Map instance and invoke its put method. Something like:

Once we invoke the put() method, what happens behind the scenes is:

  1.  The hashcode of the key is calculated.
  2.  Based on the hashcode, the destination bucket is decided for the key-value pair i.e, the Entry object.
  3.  Once the appropriate bucket is found:
    3 a. If the bucket is empty, we simply insert the Entry object.
    3 b. If the bucket is non-empty i.e, there are some Entry objects (key-value   pairs)  already present, we traverse the linked list of those entry objects and:                                        3 b. i. If a matching key is found we overwrite it. Else
    3 b. j. We add our Entry  object at the end of the list.

The get(key) method

get() method gets us the value stored against our specified key as parameter. When you invoke get() method:

  1.  The appropriate bucket is figured out, as shown in the put() method code above.
  2. Once the appropriate bucket is found:
    2 a. If the bucket is empty, null is returned as there is no Entry for the specified key.
    2 b. If the bucket is non-empty all the Entry object present in the bucket are checked for a matching key, using the equals method. We return the value associated with the key. If no matching key is found, we return null.

 

The remove(key) method

If you have understood the Linked List implementation and put() method above. The code for remove() should be self explanatory.

Full Source Code

The full source code for this example can be found at CodeCramp’s git repo here.

Bonus Tips

  1. In Java 8, to improve the performance of HashMap, put() method’s implementation has been updated to use a Red Black Tree if there are more than 8 Entries in the same bucket.
  2. Having more than one Entry in a bucket is called Hash Collision and the Linked list approach to contain Entries with same hash values in the same bucket is called chaining.