HashMap implementation is one of the most important question for Java interviews. In this blog, i have written detailed implementation. and various counter questions that arise as part of this HashMap implementaion.

HashMap Implementation

When we create HashMap in Java. JVM will allocate 16 buckets of memory with a load factor of 0.75.if we try to insert by using put method in hashmap following things will occur

1. First JVM will calculate hashcode of the key (hashMap.put("key",x)) i e by using the hashcode method eg: key.hashCode()

2. From the hash code JVM will calculate the bucket index using hashcode ie (HashCode & (length-1)) where length is the capacity of hash map

3. if there is no Hash Collison then JVM simply adds to Linked list as the first node

4. if there is a hash collision then JVM will check whether the key is existing or not. will check by using equals method "key".equals("existing key")

   • if the key is already present. JVM will add to the LinkedList by replacing the existing equal node

   • if the key is not present. then JVM will add to the Linked list as next Node

Implementation of HashMap in Diagrammatic form

Time Complexity analysis

The best time complexity of put and get methods is O(1) and the worst time complexity is O(n) till java 7. from Java 8 in the worst case at a particular index if the number of nodes crosses a particular threshold limit then the Singly Linked List becomes a Binary search tree. Hence the worst time complexity is 0(log n).

The contract between equals and Hash code method

The basic principle of hashmap is it doesn't allow duplicate keys. but it doesnt holds good for customized objects as key so if the key is a customized object. then we override equals and hashcode method. we override in such a way that equivalent objects must have the same hash code

Example 1 :

import java.util.*;
class Student
{
    int id;
    int age;
    String name;
    Student(int id,int age,String name){
        this.id=id;
        this.age=age;
        this.name=name;
    }
    public int hashCode(){
        return this.id+this.age+this.name.hashCode();
    }
    public boolean equals(Object s1){
        return this.id==((Student)s1).id && 
        this.age==((Student)s1).age && 
        this.name.hashCode()==((Student)s1).name.hashCode();
    }
}
public class Main
{
    public static void main(String[] args) {

        HashMap<Student,Integer> hm=new HashMap<>();
        hm.put(new Student(101,23,"Sunil"),1);
        hm.put(new Student(101,23,"Sunil"),2);
        hm.put(new Student(101,23,"Sunil"),3);
        hm.put(new Student(101,23,"Sunil"),4);

        System.out.println("The final values in the map is");
        for(Map.Entry<Student,Integer> me: hm.entrySet()){
            System.out.println(me.getKey().name+" "+me.getKey().age+" "+ me.getKey().id+" "+me.getValue());
        }
        System.out.println("The final size of the map is");
        System.out.println(hm.size());
    }
}

Output

Example 2:

this one of the famous interview in this concept. ie what if the hashCode and equals methods returns same constant value. in this example hashCode returns 999 and equals returns true.

• as hashCode returns same value then every key points to same bucket

• as equals method returns true . then every time it will overide previous key value

  • if it returns false it keep on appending to linked list

import java.util.*;
class Student
{
    int id;
    int age;
    String name;
    Student(int id,int age,String name){
        this.id=id;
        this.age=age;
        this.name=name;
    }
    public int hashCode(){
        return 999;
    }
    public boolean equals(Object s1){
        return true;
    }
}
public class Main
{
    public static void main(String[] args) {

        HashMap<Student,Integer> hm=new HashMap<>();
        hm.put(new Student(101,23,"Sunil"),1);
        hm.put(new Student(101,23,"Sunil"),2);
        hm.put(new Student(101,23,"Sunil"),3);
        hm.put(new Student(101,23,"Sunil"),4);

        System.out.println("The final values in the map are");
        for(Map.Entry<Student,Integer> me: hm.entrySet()){
            System.out.println(me.getKey().name+" "+me.getKey().age+" "+ me.getKey().id+" "+me.getValue());
        }
        System.out.println("The final size of the map is....");
        System.out.println(hm.size());
    }
}

Output

Design of a HashMap

For Low Level Design one of the famous interview question is Design Hash Map by using data structures

class MyHashMap {

    LinkedList<Entry>[] map;
    public static int SIZE=769;
    public MyHashMap() {
      map=new LinkedList[769];
    }

    public void put(int key, int value) {
        Entry obj=new Entry(key,value);
        int bucket=key%SIZE;
        if(map[bucket]==null){
            map[bucket]=new LinkedList<Entry>();
            map[bucket].add(new Entry(key,value));
        }else{
            for(Entry entry:map[bucket]){
                if(entry.key==key)
                {
                    entry.value=value;
                    return;
                }
            }
            map[bucket].add(new Entry(key,value));
        }

    }

    public int get(int key) {
        int bucket=key%SIZE;
        LinkedList<Entry> entries=map[bucket];
        if(entries==null)
            return -1;
        for(Entry entry:entries){
            if(entry.key==key)
                return entry.value;
        }
        return -1;

    }

    public void remove(int key) {
       int bucket=key%SIZE;
        Entry toRemove=null;
       if(map[bucket]==null)
           return;
        for(Entry entries:map[bucket]){
            if(entries.key==key)
                toRemove=entries;
        }
        if(toRemove==null){
            return;
        }
        map[bucket].remove(toRemove);
    }
}


class Entry{
    public int key;
    public int value;
    Entry(int key,int value){
        this.key=key;
        this.value=value;
    }
}