Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

Java HashMap

Posted on Sept. 16, 2018
java-hashmap

In this article, I will explain how java hashmap works and how to create your own Generic Java HashMap from scratch with all possible functionalities like search, exist, delete etc.

Let's consider a class, Song. The Song class will have an attribute title. There will be one method to get the title of the song. And the Song class will override the methods hashCode() and equals() inherited from the Object class.

Following lines of code defines the class Song.

class Song{
String title;
public Song(String title){
this.title = title;
}
public int hashCode(){
return title.hashCode();
}
public String getTitle(){
return title;
}
public boolean equals(Object o){
Song s = (Song)o;
return title.equals(s.getTitle());
}
}

Generics provides a facility to create Typed collection. Say - I have to create a hash map having Song object as key and song Type which is String object as value. With Java generic we can create the hash map using the following code.

HashMap<Song,String> myMap  = new HashMap<Song,String>();
//We can put key value pair into the hash map as below
myMap.put(new Song("Dummy Song Title"),"Dummy Singer");
//We can retrieve the value for a key as below
myMap.get(new Song("Dummy Song Title"));

How this works -


  • When the hash map object is created using new HashMap<Song,String>(); it actually creates an Array of lists. Each list can hold (key,value) pairs. The key should be of Type Song and the value should be of Type String.

  • Whenever we put a (key,value) pair into the hash map, it evaluates the key object using it's hasCode() method to get an index ( hash code) in the array.It then puts the (key,value) pair in the List corresponding to that index.

  • Whenever we try to get a value for a given key object, it again evaluates the index (hash code) and go to the List corresponding to that index and search for the key object using the equals() method in that list. If it finds the key object, it returns the corresponding value. Otherwise it returns null.

Note:


  • The logic defined in the hashCode() method plays the most important role to equally distribute the (key,value) pairs among the slots/buckets of the array.

  • If the hashCode() implementation is not good, it may happen that all the (key,value) pairs end up in the same slot/List of the array and when you try to search for a value using it's key, it will take a very long time to scan the List as it will contain all the pairs. You can read more about how to write good hash function.

Java Generic hash map does all the steps for us and gives us the put() and get() methods to use. Here we will create this Generic hash map on our own and will add some additional functionalities using the following code.

import java.util.*;
class MyMap<K,V>{
class Node{
K key; V val;
private Node(K key,V val){
this.key = key; this.val = val;
}
}
int size;
List<Node> [] arr;
public MyMap(int size) throws IllegalArgumentException{
if(size == 0)
throw new IllegalArgumentException();
this.size = size;
//creating an array of List
this.arr = new List[this.size];
for(int i=0;i<size;i++)
arr[i] = new ArrayList<Node>();
}
public MyMap(){
this.size = 50;
//creating an array of List
this.arr = new List[this.size];
for(int i=0;i<size;i++)
arr[i] = new ArrayList<Node>();
}
// put method to put a (key,value) pair
public synchronized void put(K key,V val) throws IllegalArgumentException{
if (key == null)
throw new IllegalArgumentException();
int index = Math.abs(key.hashCode())%this.size;
List<Node> list = arr[index];
for(Node n : list){
if(n.key.equals(key)){
n.val = val;
return;
}
}
list.add(new Node(key,val));
}
// get method to get the value for a corresponding key
public synchronized V get(K key) throws IllegalArgumentException{
if (key == null)
throw new IllegalArgumentException();
int index = Math.abs(key.hashCode())%this.size;
List<Node> list = arr[index];
for(Node n : list){
if(n.key.equals(key)){
return n.val;
}
}
return null;
}
//delete method to delete a (key,value) pair from the map
public synchronized void delete(K key) throws IllegalArgumentException{
if (key == null)
throw new IllegalArgumentException();
int index = Math.abs(key.hashCode())%this.size;
List<Node> list = arr[index];
for(Node n : list){
if(n.key.equals(key)){
list.remove(n);
return;
}
}
System.out.println("Key not found");
}
// exist method to check if a key exists in the map or not
public synchronized boolean exist(K key) throws IllegalArgumentException{
if (key == null)
throw new IllegalArgumentException();
int index = Math.abs(key.hashCode())%this.size;
List<Node> list = arr[index];
for(Node n : list){
if(n.key.equals(key)){
return true;
}
}
return false;
}
public static void main(String [] args) throws IllegalArgumentException{
//check the exception thrown
//MyMap<String,String> map = new MyMap<String,String>(0);
MyMap<String,String> map = new MyMap<String,String>();
map.put("dummy key","dummy value");
//Test get
System.out.println(map.get("dummy key"));
System.out.println(map.get("non existent key"));
//Test exist
System.out.println(map.exist("dummy key"));
System.out.println(map.exist("does not exist"));
//Test delete
map.delete("dummy key");
System.out.println(map.get("dummy key"));
}
}

The code is pretty self explanatory. I have defined two constructors. One which accepts an input size and other which assumes the default size of the array as 50. While testing, I have created a MyMap object using both Key and Value as String objects. You can use the Song class that I explained above as Key and see how it works. This is just an implementation of a simple generic hash map which you can use for the purpose of the interview.

If you have doubt in the code or in the concept explained above, please leave your queries in the comment section.

Sharing is Caring!

Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

GET FREE UPDATES


RECOMMENDED POSTS FOR YOU


profile image

Kaushik Baruah


ABOUT

My name is Kaushik Baruah and I am the chief blogger on this Blog. I have developed this Blog from scratch using Django as the backend and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects. You can follow me on Twitter, Facebook and Google+

GET FREE UPDATES

POPULAR POSTS

Copyright © 2018
About Us

My name is Kaushik Baruah and I am the chief blogger on this Blog. I have developed this Blog from scratch using Django as the backend and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects.

Get Free Updates