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

Singleton Design Pattern, a complete guide

In this blog, we are going to discuss all about Singleton Design Pattern which is one of the popular topic during Java Interview.

You can see a lot of discussion on this topic on various  blogs or sites in google but what I personally feel none of them have covered the entire design. So here I am going to share the complete design step by step.

What is Singleton pattern?

Singleton pattern ensures that class has only one instance and it provides a global point to access it.
Real time example of Singleton pattern is JDBC  getConnection() method.
Below one is the sample implementation of Singleton class:

public class SingleTon {
private static SingleTon singletonObj;
//constructor should be always private ,else somebody can easily     //creates its object.
private SingleTon()
{

}
public static SingleTon getInstance()
{
if(singletonObj==null)
singletonObj=new SingleTon();

return singletonObj;

}

}

/****End of code****/

So here we have created the Singleton class which restricts creation object using new operator as we made the constructor as private. So we have ensured that at any point time there would be only one instance of Singleton Class. We can write the code in main() method as below:

public static void main(String args[]){
  SingleTon singleton=SingleTon.getInstance();
}

Congratulation!!! We have created the SingleTon instance which can be accessed globally.

Wait!!!!!, this code can be cracked using Reflection in java that means even though we made Constructor as private but still during run time any body can create its instance using Reflection, here is the code snippet.

public class SingleTontest {

public static void main(String[] args) throws                               InstantiationException, IllegalAccessException,                     IllegalArgumentException, InvocationTargetException {
 /**
  * getDeclaredConstructors() method returns the number of            *   constructor present in the class,
  * default constructor always comes in 0th index 
  */
Constructor[] cons =                                                 SingleTon.class.getDeclaredConstructors();
cons [0].setAccessible(true); 

// get the instance of the class, initially it was                   // null,

SingleTon s2=(SingleTon)cons[0].newInstance();

System.out.println("hashcode after creating new                             Intance--> "+s2.getInstance().hashCode());

// get all the declared fields, in our class we                     // have only one declared field as singletonObj

Field [] f1=s2.getClass().getDeclaredFields();

f1[0].setAccessible(true);

//setting the singletonObj as NULL during runtime                   //using Reflection

f1[0].set(f1[0].getName(), null);

System.out.println("after setting null to                             singletonObj--> "+s2.getInstance().hashCode()); 

   }

}

Output:

hashcode after creating new Intance--> 366712642

after setting null to singletonObj--> 1311053135

So here we can conclude that using reflection we can create a new instance even though contructor is private and we can change its state to null as well.


So the Question here is how we can come out of this problem. Here is the solution, we have to throw UnsupportedOperationException() from the constructor which can ensure if anybody try to create an instance, it will throw this exception.

Code Snippet:

public class SingleTon {
private static SingleTon singletonObj;
//constructor should be always private, else somebody can //easily creates its object.

private SingleTon()
{
     throw new UnsupportedOperationException();
}

public static  SingleTon getInstance()
{
if(singletonObj==null)
singletonObj=new SingleTon();

return singletonObj;

}

}


But We are not yet done!!, what will happen if multiple threads like Thread 1, Thread 2, Thread 3 will try access getInstance() method, will it creates three different singletonObj for three threads, well quite possible as per our above class design.

To resolve this issue, we should use synchronized keyword to make the getInstance method as Thread safe which ensures, at a time only one thread will be executed.

Lets imagine the scenario like Thread 1 access the getInstance() method so Thread 2 and Thread 3 will have to wait unless Thread 1 come out of getInstance() method. Next time when Thread2 or Thread 3 will access the getInstance() method, it will see that singleton instance has already been created so they wont create any other singleTon object. 

Well but it will impact the performance because every thread has to wait at the method level, to resolve this issue, we can synchronized only the condition where it check the instance value, which can improve the performance.

Here is the complete Singleton class:

public class SingleTon {
private static SingleTon singletonObj;
//constructor should be always private ,else                //somebody can easily creates its object.
private SingleTon()
{
throw new UnsupportedOperationException();
}
public static  SingleTon getInstance()
{

if(singletonObj==null)
synchronized (SingleTon.class) {
if(singletonObj==null)
singletonObj=new                                                    SingleTon();
}

return singletonObj;

}

}


/***************End of SingleTon design pattern**************/

You may also Like:

Design your custom or own HashMap implementation in JAVA