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 a HashMap works?”. Let’s make reasoning around a user-defined class as a key in hashmap in Java.
1. The Key should Honor 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 “how HashMap works?“. I will leave, how hashmap works, part to you to read from the linked post, but in summary, it works on the principle of Hashing.
In HashMap, the key’s hashcode() is used primarily in conjunction with the equals() method, for putting a key in the map and then getting it back from the map. So, our only focus point is on these two methods.
equals()– verifies the equality of two objects, the keys in our case. Override to provide the logic to compare two keys.hashcode()
Overriding the the hashCode() is generally necessary whenever equals() is overridden to maintain the general contract for the hashCode() method, which states that equal objects must have equal hash codes.
2. What if Changing the Key’s HashCode is Allowed?
As stated above, the hashcode helps in calculating the bucket position for storing the key-value pair in the Map. Different hashcode values may be referring to the different bucket locations.
If, accidentally, the hashcode of the key object changes after we have put a key-value pair in the map, then it’s almost impossible to fetch the value object back from the map because we don’t know in which bucket we had put the key-value in past. The old key-value pair is not reachable, and so It is a case of a memory leak.
On runtime, JVM computes hashcode for each object and provides it on demand. When we modify an object’s state, JVM set a flag that the object is modified and hashcode must be AGAIN computed. So, next time you call the object’s hashCode() method, JVM recalculates the hashcode for that object.
3. We should Make the HashMap’s Key Immutable
For the above basic reasoning, key objects are suggested to be immutable. Immutability ensures that we will get the same hashcode every time, for a key object. So it actually solves almost all the problems in one go. But, again, such a 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 the question of why string is a popular hashmap key in java?
But remember that immutability is recommended and not mandatory. If you want to make a mutable object as a key in the hashmap, then you have to make sure that the state change for the key object does not change the hashcode of the object. This can be done by overriding the hashCode() method. But, you must make sure you are honoring the contract with equals() also.
4. HashMap Custom Key Example
An example is always better for demonstration, right? Then let’s 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.
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 honors 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().
5. Demo
Let us test our Account class for the above analysis.
//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_ONEProgram Output.
A_ONE
A_TWO
A_ONE6. Conclusion
In this tutorial, we learned to design a class that can be used as the Key in the Map instances for storing the key-value pairs.
As the best practice:
- a key class should be made immutable.
- in most situations, default hashCode() and equals() methods are good enough, but if we override one method then we should override another method as well, to make sure they follow the contract between them.
This is my understanding of designing a custom key object for HashMap.
Happy Learning !!
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 ..
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?
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
Hi Lokesh,
Can you can explain hashmap get(), with example , i tried so many time times but i have some little bit confusion,
Have you gone through how hashmap works?
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?
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 :
To avoid any unforced error as reassigning value to accountNumber, It’s better if we make the field “accountNumber” final.
To avoid any unforced error as reassigning accountNumber a new value,It would be better if you make “accountNumber” final
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.
Absolutely true. Agree “that neither equals nor hashcode should change when changing the state of object.”
can you please elaborate?.. Dint get it..
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.
I had run your sample programme but it will not correctly run
Any particular problem you see?
Very good one.Thanks Lokesh
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
Typo corrected. Yes, you are right.
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.
apologies… i made a mistake. yes u are right.
Never mind.
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; } }Just to help others reading this: Output of above program is –
World
Hello
In your first part of program, you created an instance of
Testand 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
StringBufferand set value to “Hello”. BUT, now you created another instance ofStringBufferand assigned the reference to variablesb. Please note that after changing the reference,sbdoes not point to firstStringBufferinstance, rather it points to second instance. So any operation you does usingsbnow, 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
StringBuffertosb, rather simply usesb.append()method.Now output will be:
World
HelloWorld
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 ?
Please read the linked post: https://howtodoinjava.com/java/basics/how-to-make-a-java-class-immutable/
Is the last println line correct in TestMutableKey??
we have not added a3 obj into map, so how can we retrieve it?
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.
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?
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
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.
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?
You can use StringVar.hashCode() in your hashCode implementation.
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]
Can u explain more why it becomes null if we don’t override hashcode and equals
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.
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?
No, both account objects are separate.
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.
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/
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.
Fair enough.
I get the same value even if I don’t override hashcode or equals? WHY
If you do not override the hashcode and equals function, output will be:
A_ONE
A_TWO
null
Which is different from above program.
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 ?
That’s before modifying the keys. After modifying, it’s null.
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)