How to design good custom key object for HashMap

Can we use an object as a key for a hashmap in java? This is a very popular interview question indeed. It is asked immediately after “How HashMap works?”. Lets make a reasoning around user defined object as key in hashmap in java.

1. The contract between hashCode() and equals()

The very basic need for designing a good key is that “we should be able to retrieve the value object back from the map without failure“, otherwise no matter how fancy data structure you build, it will be of no use. To decide that we have created a good key, we MUST know that “how HashMap works?”. I will leave, how hashmap works, part on you to read from linked post, but in summary it works on principle of Hashing.

Learn how HashMap works in java

Key’s hash code is used primarily in conjunction to its equals() method, for putting a key in map and then getting it back from map. So, our only focus point is these two methods. So if hash code of key object changes after we have put a key value pair in map, then its almost impossible to fetch the value object back from map. It is a case of memory leak.

On runtime, JVM computes hash code for each object and provide it on demand. When we modify an object’s state, JVM set a flag that object is modified and hash code must be AGAIN computed. So, next time you call object’s hashCode() method, JVM recalculate the hash code for that object.

2. Make HashMap key object immutable

For above basic reasoning, key objects are suggested to be IMMUTABLE. Immutability allows you to get same hash code every time, for a key object. So it actually solves most of the problems in one go. Also, this class must honor the hashCode() and equals() methods contract.

This is the main reason why immutable classes like String, Integer or other wrapper classes are a good key object candidate. and it is the answer to question why string is popular hashmap key in java?

How to make a class immutable

But remember that immutability is recommended and not mandatory. If you want to make a mutable object as key in hashmap, then you have to make sure that state change for key object does not change the hash code of object. This can be done by overriding the hashCode() method. But, you must make sure you are honoring the contract with equals() also.

3. HashMap custom key object example

An example is always better for demonstration, right? Then lets have one.

In this example, I have created an Account class with only two fields for simplicity. I have overridden the hashcode and equals method such that it uses only account number to verify the uniqueness of Account object. All other possible attributes of Account class can be changed on runtime.

package com.howtodoinjava.demo.map;

public class Account 
{
	private int accountNumber;
	private String holderName;

	public Account(int accountNumber) {
		this.accountNumber = accountNumber;
	}

	public String getHolderName() {
		return holderName;
	}

	public void setHolderName(String holderName) {
		this.holderName = holderName;
	}

	public int getAccountNumber() {
		return accountNumber;
	}

	//Depends only on account number
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + accountNumber;  
		return result;
	}

	//Compare only account numbers
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Account other = (Account) obj;
		if (accountNumber != other.accountNumber)
			return false;
		return true;
	}

}

Will this cause any undesired behavior???

NO, it will not. The reason is that Account class’s implementation honor the contract that “Equal objects must produce the same hash code as long as they are equal, however unequal objects need not produce distinct hash codes.” i.e.

Whenever a.equals(b) is true, then a.hashCode() must be same as b.hashCode().
Whenever a.equals(b) is false, then a.hashCode() may/may not be same as b.hashCode().

4. Test the HashMap custom key object

Lets test our Account class for above analysis.

package com.howtodoinjava.demo.map;

import java.util.HashMap;

public class TestMutableKey
{
    public static void main(String[] args)
    {
        //Create a HashMap with mutable key
        HashMap<Account, String> map = new HashMap<Account, String>();
         
        //Create key 1
        Account a1 = new Account(1);
        a1.setHolderName("A_ONE");
        //Create key 2
        Account a2 = new Account(2);
        a2.setHolderName("A_TWO");
         
        //Put mutable key and value in map
        map.put(a1, a1.getHolderName());
        map.put(a2, a2.getHolderName());
         
        //Change the keys state so hash map should be calculated again
        a1.setHolderName("Defaulter");
        a2.setHolderName("Bankrupt");
         
        //Success !! We are able to get back the values
        System.out.println(map.get(a1)); //Prints A_ONE
        System.out.println(map.get(a2)); //Prints A_TWO
         
        //Try with newly created key with same account number
        Account a3 = new Account(1);
        a3.setHolderName("A_THREE");
         
        //Success !! We are still able to get back the value for account number 1
        System.out.println(map.get(a3)); //Prints A_ONE
    }
}

Program Output.

A_ONE
A_TWO
A_ONE

This is my understanding on designing custom key object for HashMap. If you disagree or feel otherwise, please drop me a comment.

Happy Learning !!

References:

Was this post helpful?

Let us know if you liked the post. That’s the only way we can improve.

Twitter Facebook LinkedIn Reddit Pocket

About Lokesh Gupta

A family guy with fun loving nature. Love computers, programming and solving everyday problems. Find me on Facebook and Twitter.

Feedback, Discussion and Comments

kjp

February 12, 2019

how to do hashmap value object (is my approach correct ), I have written this code, how to get the city details,

My csv file contains these data,

city,city_ascii,lat,lng,country,iso2,iso3,admin_name,capital,population,id
Malishevë,Malisheve,42.4822,20.7458,Kosovo,XK,XKS,Malishevë,admin,,1901597212
Prizren,Prizren,42.2139,20.7397,Kosovo,XK,XKS,Prizren,admin,,1901360309
Zubin Potok,Zubin Potok,42.9144,20.6897,Kosovo,XK,XKS,Zubin Potok,admin,,1901608808
Kamenicë,Kamenice,42.5781,21.5803,Kosovo,XK,XKS,Kamenicë,admin,,1901851592
Viti,Viti,42.3214,21.3583,Kosovo,XK,XKS,Viti,admin,,1901328795
Shtërpcë,Shterpce,42.2394,21.0272,Kosovo,XK,XKS,Shtërpcë,admin,,1901828239
________________________

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Scanner;

public class HashTable {

    String csvFile;
    HashMap<String, CM> cityMap;
    Scanner input = new Scanner(System.in);
    
    public static void main(String[] args) {   	
    	HashTable csvFileReaders = new HashTable();
    	csvFileReaders.createHashTable();
   		for(int i=0;i<5;i++){
   				csvFileReaders.searchFromHashTable();
   		}
    }
    
    public HashTable() {
    	while(true){
    		System.out.println("Enther the File Path");
    		String csvFileInput = input.nextLine();
    		File csv = new File(csvFileInput);
    		
       		if(csv.exists()){
       			this.csvFile= csvFileInput;
       			break;
       		}
       		else{
       			System.out.println(" The filename you entered doesnt exist please re-enter the correct filepath\n");
       		}
    	}	
     }
    
    public void createHashTable() {
        cityMap = new HashMap<>(); 
        CM CmHashMap = new CM();       
        try (Scanner scanFile= new Scanner(new File(csvFile), "UTF-8")) {        	
            while (scanFile.hasNextLine()) {
            	String name = scanFile.nextLine();
            	String[] line = name.split(",");
            	for (int i = 0; i < line.length; i++) {
            		CmHashMap.setCity(line[0]);
            		CmHashMap.setCity_ascii(line[1]);
            		CmHashMap.setLat(line[2]);
            		CmHashMap.setLng(line[3]);
            		CmHashMap.setCountry(line[4]);
            		CmHashMap.setIso2(line[5]);
            		CmHashMap.setIso3(line[6]);
            		CmHashMap.setAdmin_name(line[7]);
            		CmHashMap.setPopulation(line[8]);
            		CmHashMap.setId(line[9]);
            		cityMap.put(line[1], CmHashMap);
            	}
            }
            scanFile.close();
        }        
        catch (FileNotFoundException e) {
        	e.printStackTrace();
        }
    }

    public void searchFromHashTable() {
   		System.out.println(" \n Enter the City name to be Searched from HashTable :   \n -> ");      
		String searchTerm = input.nextLine().toLowerCase();        
        //Search the city        
        long start = System.currentTimeMillis();
        	if (cityMap.containsKey(searchTerm)) {
        		
        		System.out.println("City name is : " + searchTerm + "\nCity details are accordingly in the order :"
                                       + "\n[city , city_ascii , lat , lng , country , iso2 , iso3 , admin_name , capital"
                                       + " , population , id] \n"+ cityMap.get(searchTerm) + "");
        	} 
        	else {
            System.out.println("Enter the correct City name");
        	}
        	
        long end = System.currentTimeMillis();
        System.out.println(" \n It took " + (end - start) + " Milli Seconds to search the result \n");    	
    }
}

___________________________

public class CM {
	
    private  String city;
    private  String city_ascii;
    private  String lat;
    private  String lng;
    private  String country;
    private  String iso2;
    private  String iso3;
    private  String admin_name;
    private  String capital;
    private  String population;
    private  String id;
    
   public CM( String city, String city_ascii, String lat, String lng, String country, String iso2, String iso3, String admin_name, String capital, String population, String id){
	   this.city = city;
	   this.city_ascii = city_ascii;
	   this.lat = lat;
	   this.lng = lng;
	   this.country = country;
	   this.iso2 = iso2;
	   this.iso3 = iso3;
	   this.admin_name = admin_name;
	   this.capital = capital;
	   this.population = population;
	   this.id = id;	   
   }
	   public CM() {
	// TODO Auto-generated constructor stub
	   }
	public String getCity() {
			return city;
		}

		public void setCity(String city) {
			this.city = city;
		}

		public String getCity_ascii() {
			return city_ascii;
		}

		public void setCity_ascii(String city_ascii) {
			this.city_ascii = city_ascii;
		}

		public String getLat() {
			return lat;
		}

		public void setLat(String lat) {
			this.lat = lat;
		}

		public String getLng() {
			return lng;
		}

		public void setLng(String lng) {
			this.lng = lng;
		}

		public String getCountry() {
			return country;
		}

		public void setCountry(String country) {
			this.country = country;
		}

		public String getIso2() {
			return iso2;
		}

		public void setIso2(String iso2) {
			this.iso2 = iso2;
		}

		public String getIso3() {
			return iso3;
		}

		public void setIso3(String iso3) {
			this.iso3 = iso3;
		}

		public String getAdmin_name() {
			return admin_name;
		}

		public void setAdmin_name(String admin_name) {
			this.admin_name = admin_name;
		}

		public String getCapital() {
			return capital;
		}

		public void setCapital(String capital) {
			this.capital = capital;
		}

		public String getPopulation() {
			return population;
		}

		public void setPopulation(String population) {
			this.population = population;
		}

		public String getId() {
			return id;
		}

		public void setId(String id) {
			this.id = id;
		}
		public String toString() {
	        return "\n The following details are of city : " + city +"\n The Ascii string would be : "
					+ city_ascii +"\n Its having the lattitude around : "
					+ lat + "\n and Longitude of : "+ lng +"\n It is situated in : "
					+ country +"\n These have iso code like  : "+ iso2 +" and : "+ iso3 +"\n It comes under  : "
					+ admin_name +" State \n Capital of this city is : "+ capital +"\n The population is around : "
					+ population +"\n ZIP code is : "+id+"\n ";
			}
}

arun singh
May 1, 2018

pretty deep and difficult to understand in one go.
but great article, thanks for the information.
bala
January 25, 2018

Save my day! Thanks Lokesh!
Divya
August 31, 2017

How do you access values of a hashmap in a class from a different class in Java? please help!
Kd
August 23, 2017

Awesome..felling that I m learning hashmap now..
Subodh
August 5, 2017

Hi Lokesh,
One more point to add to the answer is not using the transient variables in hashCode()
If the object is serailized, it would get default value for transient variable instead of instance value , making it impossible to locate
jyotsna
April 18, 2017

Hi Lokesh,
could you plz explain me below doubts ?
if HashMap key is a String object/user defined class obj then how the hashcode generates ?
HashMap hm= new HashMap();
hm.put(21, 121);
normally hashcode calulates : key %capacity = 21%4= 1 // suppose my Initial capacity is 4 and it will tore @ index position 1
same way want to know how it calculates for a String and userdefined class as a key ..

Sandeep

February 13, 2017

Interview questions:

public class Employee {
    private int id;
    private String name;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {/*
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Employee employee = (Employee) o;

        if (id != employee.id) return false;
        return name != null ? name.equals(employee.name) : employee.name == null;*/
        return false;

    }

    @Override
    public int hashCode() {
        /*int result = id;
        result = 31 * result + (name != null ? name.hashCode() : 0);
        return result;*/
        return 1;
    }
}

what is the output

System.out.println(employeeObjectMap.size());
System.out.println(employeeObjectMap.get(employee3));

RAJIV SARKAR
June 28, 2019

MapSize :1 as every time it generates same hashcode so same bucket is use for out opeation.
As equals always returns false it wont be able to get the object from map.
- RAJIV SARKAR
  June 28, 2019
  
  MapSize will be number of put operations you do as every time it generates same hashcode so same bucket is use for out opeation but since equals method returns false every time it stores in different entry of map.
  As equals always returns false it wont be able to get the object from map.
  - RAJIV SARKAR
    June 28, 2019
    
    please ignore my first answer

GURDEEP SINGH SAINI
November 8, 2016

is equals methods compare each key on the same bucket and if keys are equal then replace the values to the recent keys value?
please explain how equal method works in hashmap?
- siddharhta
  July 11, 2017
  
  In Hash map equals method works on keys. Generally Hash code is may same or may not same for two different keys. if hash code is same and and the index is same but keys are different In this case hash map create a linked list and stores the values at the next node of present key value pair
Arun Vadivel
October 24, 2016

This article is very informative.. Thank you very much..
Sangram
April 1, 2015

above hashcode method :
final int prime = 31;
int result = 1;
result = prime * result + accountNumber;
return result;
is same as :
return 31 * accountNumber;
Any reason why you wrote those 4 lines?
- Lokesh Gupta
  April 1, 2015
  No. You are right that it could be one line code also. But if you have multiple fields in hashCode() calculation then It will be easy to change them method as below :
```
result = prime * result + accountNumber;
result = prime * result + field1;
result = prime * result + field2.hashCode();
result = prime * result + field3;
```
Ashish Thakur
August 13, 2014

To avoid any unforced error as reassigning value to accountNumber, It’s better if we make the field “accountNumber” final.
Ashish Thakur
August 13, 2014

To avoid any unforced error as reassigning accountNumber a new value,It would be better if you make “accountNumber” final
dob
August 5, 2014

i think it is important that neither equals nor hashcode should change when changing the state of object. In your example, if I have hashcode on the basis of account number and equals on the basis of account number and holder name, then neither property can be changed if you a reliable key is required for map.
- Lokesh Gupta
  August 5, 2014
  
  Absolutely true. Agree “that neither equals nor hashcode should change when changing the state of object.”
  - Priyanka
    June 23, 2016
    
    can you please elaborate?.. Dint get it..
    - Lokesh Gupta
      June 24, 2016
      
      If hashcode and equals will change after inserting the ‘key’ object in map, you will not get same ‘value’ object from map.. and even you may loose the value object all together thus causing memory leak.
Pravin
June 5, 2014

I had run your sample programme but it will not correctly run
- Lokesh Gupta
  June 5, 2014
  
  Any particular problem you see?
samba
May 29, 2014

Very good one.Thanks Lokesh
DreamUth
May 28, 2014

Nice post.
In #33, you are setting for value for a1 but I guess you might be interested in setting value for a3.
Assume that, I have included holdername in equals method and I put the a3 in the same map. Then the above code will return “A_THREE” because after matching the hashcode, it will use the equals to identify the correct key. Please correct me if I am not
- Lokesh Gupta
  May 28, 2014
  
  Typo corrected. Yes, you are right.
- Suraj
  January 3, 2016
  
  Hi.. I included holdername in equals method and then put a3 in the same map . I got null as output for a3 as key.
  If i include holdername in hash code as well then i get null for all the three keys. Can you please mention as to how will I get “A_THREE “as value for a3 as key.
  - Suraj
    January 3, 2016
    
    apologies… i made a mistake. yes u are right.
    - Lokesh Gupta
      January 3, 2016
      
      Never mind.
      - Suraj
        January 4, 2016
        
        Hi Lokesh, Can u help me in understanding the output following program. Why the output is different in the below two cases?
        import java.util.HashMap; public class HashMapValue { public static void main(String[] args) { Test objTest = new Test("Hello"); HashMap<Integer, Test> hm = new HashMap<Integer, Test>(); hm.put(1, objTest); objTest.setName("World"); Test secondObject = hm.get(1); System.out.println(secondObject.getName()); HashMap<Integer, StringBuffer> hm2 = new HashMap<Integer, StringBuffer>(); StringBuffer sb = new StringBuffer("Hello"); hm2.put(1, sb); sb = new StringBuffer("World"); System.out.println(hm2.get(1)); } } class Test { String name; Test(String name) { this.name = name; } public String getName() { return name; } public void setName(String name) { this.name = name; } }
        
        Lokesh Gupta
        January 5, 2016
        
        Just to help others reading this: Output of above program is –
        World
        Hello
        In your first part of program, you created an instance of Test and set it’s value to “Hello”. After inserting this instance in map, you used the same reference to change the value to “World”. So value got changed.
        In second part of program, you created instance of StringBuffer and set value to “Hello”. BUT, now you created another instance of StringBuffer and assigned the reference to variable sb. Please note that after changing the reference, sb does not point to first StringBuffer instance, rather it points to second instance. So any operation you does using sb now, does not affect the instance inside map. So when you fetch it from map, it’s unchanged.
        If you really want to change the value, then do not assign the reference of new StringBuffer to sb, rather simply use sb.append() method.
        //sb = new StringBuffer("World"); sb.append("World");
        Now output will be:
        World
        HelloWorld
Boutique
April 30, 2014

Hey well explained, but I am not clear about immutability. Since you told at the start how to create immutable class. I dont see it you above example. Am I missing anything here ?
- Lokesh Gupta
  April 30, 2014
  
  Please read the linked post: https://howtodoinjava.com/java/basics/how-to-make-a-java-class-immutable/
Ajay
April 13, 2014

Is the last println line correct in TestMutableKey??
we have not added a3 obj into map, so how can we retrieve it?
- Ajmal CH
  May 22, 2014
  
  Hi Ajay,
  As far I I understand, both a1 and a3 would produce same hascode and also equals method wouldl return true since both account numbers are same. That are the only two things HashMap will check before returning a value object from the map.
Nate
April 11, 2014

What if I would like both values in the account class to be immutable? Like the account number and the holder name would have to be equal for the objects to be equal? How does this change the hashcode and equals methods?
Shailesh
March 12, 2014

Nice Article
sagar
March 11, 2014

1.) when a hashcode value is calculated , this value happens to be some memory address on the heap. What is the guarantee OR how hashMap ensures that the hashcode that will be calculated will be a free mem area(the same mem area is not being used by some other program)
2.) Although internally objects will be stored in a transient Entry[]. Is it that this array which is a datastructure with contiguous mem locations will already claim its space on the heap, once declared and then the bucket allocation happens from within this transient array.
Kindly help on the above 2 questions
- Lokesh Gupta
  March 11, 2014
  
  1) NO, hashcode is not same as memory address. Rather it’s kind of representation of memory address. For default hashCode() method, JVM derives the value from the value of the reference to the object. So, first object is created in memory and then hashcode is calculated.
  2) Yes you are right.
Shaon
February 3, 2014

Can i do the same hascode implementation with String, as u did with integer value(Acc no)? If so how?what should be the code inside hashcode?
- Lokesh Gupta
  February 3, 2014
  
  You can use StringVar.hashCode() in your hashCode implementation.
Anurag
January 28, 2014

Very good post. It clearly explains
Maddy
January 9, 2014

Most important thing to know about HashMap is it’s data structures and algorithms used to write this class. As name of class(HashMap) is indicating that its works on hashing mechanism. This class basically uses two data structures, one is Array and other is Linked-List. HashMap internally create Array of Entry type objects. Entry is an inner class used by HashMap to stores Key and Value type’s objects. To place an Entry object in array, we need an index at which that object can store in array. This index is generated by hash code of key object provide by user. Hash code of key object can get by hashCode() method of key object. After knowing index, Entry object can place in array. These array indexes are known as bucket. Now if you want to retrieve any object from HashMap, you need to provide key for that. This is key object gives hash code, this hash code generates an index and now at this index you have your object.
If you want to read more about HashMap [Click Here]
amit
December 22, 2013

Can u explain more why it becomes null if we don’t override hashcode and equals
- Lokesh Gupta
  December 22, 2013
  
  In this case, Account a3 = new Account(1); creates an object whose hashcode will be different from a1. We have not put a3 in map, so it’s not available to matched with a1.
  If we override hashcode and equals then a3 is matched with a1 due to same account number, and a1 is returned.
Aruna
December 2, 2013

Hi, I have not implemented hashcode() and equals() methods and the output is:
A_ONE
A_TWO
null
I have changed the accountNumber field to String, still get the same output
A_ONE
A_TWO
null
String being immutable, should the output be different?
- Lokesh Gupta
  December 2, 2013
  
  No, both account objects are separate.
Arvind Prabhakar
November 30, 2013

Nice article .I really enjoyed all your articles.I have one request, could you please explain ThreadLocal .I tried understanding but not able to implement it practically. It will be very helpful.
- Lokesh Gupta
  November 30, 2013
  
  I will write a post soon. By the time, you would like to read a practical example of Thread local: https://howtodoinjava.com/resteasy/share-context-data-with-jax-rs-resteasyproviderfactory/
Jacob Zimmerman
October 27, 2013

This is only acceptable if you are okay with the mutable parts of the class being unimportant for seeing if two instances of the class are “equal”. Many people might be thrown off by the idea of them changing something and seeing that it is still considered equal to something that it was equal to before. This is not neccessarily a bad thing, but you should probably state in the documentation that certain parts aren’t factored into its equality.
- Lokesh Gupta
  October 27, 2013
  
  Fair enough.
patel
September 12, 2013

I get the same value even if I don’t override hashcode or equals? WHY
- Lokesh Gupta
  September 12, 2013
  
  If you do not override the hashcode and equals function, output will be:
  A_ONE
  A_TWO
  null
  Which is different from above program.
  - Anuj
    August 31, 2014
    
    Hi Lokesh,
    if in this case as we are not overriding the hashcode and equal method,and we are changing object state i.e.(mutable key) then how its is fetching the values A_ONE
    A_TWO ?
    - Lokesh Gupta
      September 1, 2014
      
      That’s before modifying the keys. After modifying, it’s null.
      - Anuj
        September 1, 2014
        
        here account a1 always returns same hashcode even after setting the name.
        Is that mean its not necessary that hashcode will change incase we are changing state of mutable class (Provided we are not override the method)
aavi
July 26, 2013

YOU ROCK MAN!
sandy
July 14, 2013

Very clearly explain.
aditya kumar
June 17, 2013

Best article i ever read on this topic…..
Nitin Madnani
June 12, 2013

Nice article man, keep up the good work !!!
- Malli
  September 7, 2016
  
  Hi Lokesh,
  Can you can explain hashmap get(), with example , i tried so many time times but i have some little bit confusion,
  - Lokesh Gupta
    September 7, 2016
    
    Have you gone through how hashmap works?

Comments are closed on this article!