Designing a Good Custom Key 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 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() – returns a unique integer value for the key in runtime. This value is used to locate the bucket location in the Map.

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.

1. Whenever a.equals(b) is true, then a.hashCode() must be same as b.hashCode().
2. 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_ONE

Program Output.

A_ONE
A_TWO
A_ONE

6. 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 !!