HashMap implementation with List in Java

Filed Under: Java

HashMap is one of the most widely used implementations of Map to store key-value pairs. It has been introduced in Java 1.2 and here I am trying to implement HashMap with ArrayList.

HashMap Implementation

The below code will provide two of the basic HashMap functions i.e get(key) and put(key, value). The code also takes care of checking duplicate values while storing.

Please note that it’s just the basic implementation and should not be used as a replacement of HashMap. Also while testing the code, make sure that the Object used in the KEY has a proper implementation of equals() method.

MyHashMap.java


package com.journaldev.util;

import java.util.ArrayList;
import java.util.List;

public class MyHashMap {

	class Container{
		Object key;
		Object value;
		public void insert(Object k, Object v){
			this.key=k;
			this.value=v;
		}
	}
	
	private Container c;
	private List<Container> recordList;
	
	public MyHashMap(){
		
		this.recordList=new ArrayList<Container>();
	}
	
	public void put(Object k, Object v){
		this.c=new Container();
		c.insert(k, v);
		//check for the same key before adding
		for(int i=0; i<recordList.size(); i++){
			Container c1=recordList.get(i);
			if(c1.key.equals(k)){
				//remove the existing object
				recordList.remove(i);
				break;
			}
		}
		recordList.add(c);
	}
	
	public Object get(Object k){
		for(int i=0; i<this.recordList.size(); i++){
			Container con = recordList.get(i);
			//System.out.println("k.toString():"+k.toString()+"con.key.toString()"+con.key.toString());
			if (k.toString()==con.key.toString()) {
				
				return con.value;
			}
			
		}
		return null;
	}
	
	public static void main(String[] args) {
		MyHashMap hm = new MyHashMap();
		hm.put("1", "1");
		hm.put("2", "2");
		hm.put("3", "3");
		System.out.println(hm.get("3"));
		hm.put("3", "4");
		
		System.out.println(hm.get("1"));
		System.out.println(hm.get("3"));
		System.out.println(hm.get("8"));
	}

}

Output of the above program is:


3
1
4
null

Inspiration: I have been asked this question a lot in the interviews and I have also asked this question to a lot of developers in the interview. 🙂

Comments

  1. RAHUL SAXENA says:

    Hi Pankaj,

    You are not adding record in recordList in put method.I think that is missing within the program

  2. Anjith says:

    I agree with other folks.There must not be a term”hash” in the class name as there is no hashing at all.

  3. Chuni says:

    Hey, I have a few questions:
    1) Why do you use Container c as instance field and not as method-local in put method?
    2) Why do you complicate with an insert method for container, a simple constructor would do?
    3) What if multiple threads call put method, there needs to be some control on the way modifications happen to underlying List
    4) Why not to extend the Map interface ?

    Thanks in anticipation
    -Chuni

    1. Pankaj says:

      Hi Chunni,

      Good points made by you.

      1. Yes, we can create the Container object in put method itself.
      2. Yes we can remove insert and keep a constructor for container.
      3. We can use synchronization to avoid this scenario.
      4. I am trying to use List to create HashMap like data structure, note that HashMap uses hashing algorithm but I am not going into that much details.

      Here is the updated program.

      import java.util.ArrayList;
      import java.util.List;
      
      
      public class MyHashMap {
      
          private Object dummy = new Object();
      
      
          class Container {
              Object key;
              Object value;
      
      
              public Container(Object k, Object v) {
                  this.key = k;
                  this.value = v;
              }
          }
      
      
          private List<Container> recordList;
      
      
          public MyHashMap() {
      
              this.recordList = new ArrayList<Container>();
          }
      
      
          public void put(Object k, Object v) {
              Container c = new Container(k, v);
              synchronized (dummy) {
                  for (int i = 0; i < recordList.size(); i++) {
                      Container c1 = recordList.get(i);
                      if (c1.key.equals(k)) {
                          recordList.remove(i);
                          break;
                      }
                  }
                  recordList.add(c);
              }
      
          }
      
      
          public Object get(Object k) {
              for (int i = 0; i < this.recordList.size(); i++) {
                  Container con = recordList.get(i);
                  if (k.toString() == con.key.toString()) {
                      return con.value;
                  }
              }
              return null;
          }
      
      
          public static void main(String[] args) {
              MyHashMap hm = new MyHashMap();
              hm.put("1", "1");
              hm.put("2", "2");
              hm.put("3", "3");
              System.out.println(hm.get("3"));
              hm.put("3", "4");
              System.out.println(hm.get("1"));
              System.out.println(hm.get("3"));
              System.out.println(hm.get("8"));;
          }
      }
      
  4. Sivasubramaniam Arunachalam says:

    Please rename it to “MyMap”. There is no hashing here.

    1. Pankaj says:

      Its just the basic implementation of HashMap using List, should not be used instead of HashMap.

  5. anonymous says:

    Your use of the term “hash map” is very sloppy. You’ve made the distinction between Map and HashMap in your introduction, seemingly understanding the difference, but your implementation doesn’t attempt to use any concept of hashing. Makes one wonder if you (or your interviewers) understand the questions that you’re asking.

    Beginning developers need to know that communication is one of the most critical aspects of the field and this code is a good example of poor communication. Please correct the code or the submission (hopefully both).

    1. Pankaj says:

      Its just a simple implementation, I am not trying to provide complete implementation of HashMap. As you can see that in post, I have said that its basic implementation and should not be used instead of HashMap.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages