How to create or design your own HashMap in JAVA

One of my friends had recently faced this question during his interview with JP Morgan. You can expect this kind of questions in every product based company.

To design our own HashMap, we should know how java.util.HashMap internally works. HashMap has DEFAULT_SIZE of 16 that means DEFAULT capacity of HashMap is 16 buckets and load factor is 0.75.

Internally HashMap has Entry class, which contains Key and Value.

Every time when we put some value into the HashMap, internally it will calculate the hashCode() of the given key to find out the correct bucketId to place that object inside that index.

Every time when we get() some value based on key, it will calculate the hashCode of that key and go to the correct basketId and returns the  object.

Here is the implementation of Entry class:

package design.own.hashmap;

public class Entry<K,V> {
K key;
V value;
Entry<K,V> next;
public Entry(K key, V value)
{
this.key=key;
this.value=value;
next=null;
}

public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public Entry<K, V> getNext() {
return next;
}
public void setNext(Entry<K, V> next) {
this.next = next;
}
}

**********Implementation of complete HashMap***********

package design.own.hashmap;

public class HashMap<K,V> {
private int DEFAULT_SIZE=16;
private Entry<K,V>[] entryBucket;
public HashMap(){
entryBucket=new Entry[DEFAULT_SIZE];
}
public HashMap(int capacity){
entryBucket=new Entry[capacity];
}
public void put(K key, V value)
{
int bucketIndex=getBucketindex(key);
Entry<K,V> entry=entryBucket[bucketIndex];
if(entry!=null){
boolean done=false;
while(!done)
if(key.equals(entry.getKey())){
entry.setValue(value);
done=true;
}else if(entry.getNext()==null)
{
entry.setNext(new Entry<K,V>(key, value));
}
entry=entry.getNext();

}else{
entryBucket[bucketIndex]=new Entry<K,V>(key, value);
}
}
/**
* this method returns the basketId based on applying hashCode on given key
* @param key
* @return
*/
public int getBucketindex(K key)
{
int val=key.hashCode()%10;
return val;
}
public V get(K key) {
Entry<K, V> entry = entryBucket[getBucketindex(key)];
while (entry != null && !key.equals(entry.getKey()))
entry = entry.getNext();
return entry != null ? entry.getValue() : null;
}

}


**************************Test Class************************

package design.own.hashmap;

public class HashMapTest {
public static void main(String[] args) {
HashMap<Integer,Integer> map=new HashMap<>();
map.put(1,10);
map.put(2,20);
map.put(11,30);
System.out.println("Val is: "+ map.get(1));
}

}

*****************End of Custome HashMap Implementation***************

So as per our above implementation, when we put key as 1, it will calculate its hashCode and return bucketIndex as 1 so 10 will be kept inside 1 bucketIndex.

Next time we put 2 as key, so it will calculate its bucket index and put 20 inside 2 bucketIndex.

Now we put 11 as key and its bucket index is 1, but 10 is already there inside bucketIndex 1, so this time it will create one more Entry node which will be next to node 10.

Please see the below Image, we assumed we have 16 buckets and based on our above main class, it will be like:

You may also like:

Singleton Design pattern, a complete guide
Determine if a String has all unique character or not in JAVA
Converting String to Integer without using any Standard Library in JAVA