Recently I read through this Developer Works Document.
The document is all about defining hashCode() and equals() effectively and correctly, however I am not able to figure out why we need to override these two methods.
How can I take the decision to implement these methods efficiently?
Joshua Bloch says on Effective Java
You must override hashCode() in every class that overrides equals(). Failure to do so will result in a violation of the general contract for Object.hashCode(), which will prevent your class from functioning properly in conjunction with all hash-based collections, including HashMap, HashSet, and Hashtable.
Let's try to understand it with an example of what would happen if we override equals() without overriding hashCode() and attempt to use a Map.
Say we have a class like this and that two objects of MyClass are equal if their importantField is equal (with hashCode() and equals() generated by eclipse)
public class MyClass {
private final String importantField;
private final String anotherField;
public MyClass(final String equalField, final String anotherField) {
this.importantField = equalField;
this.anotherField = anotherField;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((importantField == null) ? 0 : importantField.hashCode());
return result;
}
@Override
public boolean equals(final Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final MyClass other = (MyClass) obj;
if (importantField == null) {
if (other.importantField != null)
return false;
} else if (!importantField.equals(other.importantField))
return false;
return true;
}
}
Imagine you have this
MyClass first = new MyClass("a","first");
MyClass second = new MyClass("a","second");
Override only equals
If only equals is overriden, then when you call myMap.put(first,someValue) first will hash to some bucket and when you call myMap.put(second,someOtherValue) it will hash to some other bucket (as they have a different hashCode). So, although they are equal, as they don't hash to the same bucket, the map can't realize it and both of them stay in the map.
Although it is not necessary to override equals() if we override hashCode(), let's see what would happen in this particular case where we know that two objects of MyClass are equal if their importantField is equal but we do not override equals().
Override only hashCode
If you only override hashCode then when you call myMap.put(first,someValue) it takes first, calculates its hashCode and stores it in a given bucket. Then when you call myMap.put(second,someOtherValue) it should replace first with second as per the Map Documentation because they are equal (according to the business requirement).
But the problem is that equals was not redefined, so when the map hashes second and iterates through the bucket looking if there is an object k such that second.equals(k) is true it won't find any as second.equals(first) will be false.
Hope it was clear
You must override hashCode() in every class that overrides equals(). Failure to do so will result in a violation of the general contract for Object.hashCode(), which will prevent your class from functioning properly in conjunction with all hash-based collections, including HashMap, HashSet, and Hashtable.
from Effective Java, by Joshua Bloch
By defining equals() and hashCode() consistently, you can improve the usability of your classes as keys in hash-based collections. As the API doc for hashCode explains: "This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable."
The best answer to your question about how to implement these methods efficiently is suggesting you to read Chapter 3 of Effective Java.
Why we override equals() method
In Java we can not overload how operators like ==, +=, -+ behave. They are behaving a certain way. So let's focus on the operator == for our case here.
How operator == works.
It checks if 2 references that we compare point to the same instance in memory. Operator == will resolve to true only if those 2 references represent the same instance in memory.
So now let's consider the following example
public class Person {
private Integer age;
private String name;
..getters, setters, constructors
}
So let's say that in your program you have built 2 Person objects on different places and you wish to compare them.
Person person1 = new Person("Mike", 34);
Person person2 = new Person("Mike", 34);
System.out.println ( person1 == person2 ); --> will print false!
Those 2 objects from business perspective look the same right? For JVM they are not the same. Since they are both created with new keyword those instances are located in different segments in memory. Therefore the operator == will return false
But if we can not override the == operator how can we say to JVM that we want those 2 objects to be treated as same. There comes the .equals() method in play.
You can override equals() to check if some objects have same values for specific fields to be considered equal.
You can select which fields you want to be compared. If we say that 2 Person objects will be the same if and only if they have the same age and same name, then the IDE will create something like the following for automatic generation of equals()
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age &&
name.equals(person.name);
}
Let's go back to our previous example
Person person1 = new Person("Mike", 34);
Person person2 = new Person("Mike", 34);
System.out.println ( person1 == person2 ); --> will print false!
System.out.println ( person1.equals(person2) ); --> will print true!
So we can not overload == operator to compare objects the way we want but Java gave us another way, the equals() method, which we can override as we want.
Keep in mind however, if we don't provide our custom version of .equals() (aka override) in our class then the predefined .equals() from Object class and == operator will behave exactly the same.
Default equals() method which is inherited from Object will check whether both compared instances are the same in memory!
Why we override hashCode() method
Some Data Structures in java like HashSet, HashMap store their elements based on a hash function which is applied on those elements. The hashing function is the hashCode()
If we have a choice of overriding .equals() method then we must also have a choice of overriding hashCode() method. There is a reason for that.
Default implementation of hashCode() which is inherited from Object considers all objects in memory unique!
Let's get back to those hash data structures. There is a rule for those data structures.
HashSet can not contain duplicate values and HashMap can not contain duplicate keys
HashSet is implemented with a HashMap behind the scenes where each value of a HashSet is stored as a key in a HashMap.
So we have to understand how a HashMap works.
In a simple way a HashMap is a native array that has some buckets. Each bucket has a linkedList. In that linkedList our keys are stored. HashMap locates the correct linkedList for each key by applying hashCode() method and after that it iterates through all elements of that linkedList and applies equals() method on each of these elements to check if that element is already contained there. No duplicate keys are allowed.
When we put something inside a HashMap, the key is stored in one of those linkedLists. In which linkedList that key will be stored is shown by the result of hashCode() method on that key. So if key1.hashCode() has as a result 4, then that key1 will be stored on the 4th bucket of the array, in the linkedList that exists there.
By default hashCode() method returns a different result for each different instance. If we have the default equals() which behaves like == which considers all instances in memory as different objects we don't have any problem.
But in our previous example we said we want Person instances to be considered equal if their ages and names match.
Person person1 = new Person("Mike", 34);
Person person2 = new Person("Mike", 34);
System.out.println ( person1.equals(person2) ); --> will print true!
Now let's create a map to store those instances as keys with some string as pair value
Map<Person, String> map = new HashMap();
map.put(person1, "1");
map.put(person2, "2");
In Person class we have not overridden the hashCode method but we have overridden equals method. Since the default hashCode provides different results for different java instances person1.hashCode() and person2.hashCode() have big chances of having different results.
Our map might end with those persons in different linkedLists.
This is against the logic of a HashMap
A HashMap is not allowed to have multiple equal keys!
But ours now has and the reason is that the default hashCode() which was inherited from Object Class was not enough. Not after we have overridden the equals() method on Person Class.
That is the reason why we must override hashCode() method after we have overridden equals method.
Now let's fix that. Let's override our hashCode() method to consider the same fields that equals() considers, namely age, name
public class Person {
private Integer age;
private String name;
..getters, setters, constructors
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age &&
name.equals(person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}
Now let's try again to save those keys in our HashMap
Map<Person, String> map = new HashMap();
map.put(person1, "1");
map.put(person2, "2");
person1.hashCode() and person2.hashCode() will definitely be the same. Let's say it is 0.
HashMap will go to bucket 0 and in that LinkedList will save the person1 as key with the value "1". For the second put HashMap is intelligent enough and when it goes again to bucket 0 to save person2 key with value "2" it will see that another equal key already exists there. So it will overwrite the previous key. So in the end only person2 key will exist in our HashMap.
Now we are aligned with the rule of Hash Map that says no multiple equal keys are allowed!
Simply put, the equals-method in Object check for reference equality, where as two instances of your class could still be semantically equal when the properties are equal. This is for instance important when putting your objects into a container that utilizes equals and hashcode, like HashMap and Set. Let's say we have a class like:
public class Foo {
String id;
String whatevs;
Foo(String id, String whatevs) {
this.id = id;
this.whatevs = whatevs;
}
}
We create two instances with the same id:
Foo a = new Foo("id", "something");
Foo b = new Foo("id", "something else");
Without overriding equals we are getting:
Correct? Well maybe, if this is what you want. But let's say we want objects with the same id to be the same object, regardless if it's two different instances. We override the equals (and hashcode):
public class Foo {
String id;
String whatevs;
Foo(String id, String whatevs) {
this.id = id;
this.whatevs = whatevs;
}
@Override
public boolean equals(Object other) {
if (other instanceof Foo) {
return ((Foo)other).id.equals(this.id);
}
}
@Override
public int hashCode() {
return this.id.hashCode();
}
}
As for implementing equals and hashcode I can recommend using Guava's helper methods
Because if you do not override them you will be use the default implentation in Object.
Given that instance equality and hascode values generally require knowledge of what makes up an object they generally will need to be redefined in your class to have any tangible meaning.
It is useful when using Value Objects. The following is an excerpt from the Portland Pattern Repository:
Examples of value objects are things like numbers, dates, monies and strings. Usually, they are small objects which are used quite widely. Their identity is based on their state rather than on their object identity. This way, you can have multiple copies of the same conceptual value object.
So I can have multiple copies of an object that represents the date 16 Jan 1998. Any of these copies will be equal to each other. For a small object such as this, it is often easier to create new ones and move them around rather than rely on a single object to represent the date.
A value object should always override .equals() in Java (or = in Smalltalk). (Remember to override .hashCode() as well.)
Assume you have class (A) that aggregates two other (B) (C), and you need to store instances of (A) inside hashtable. Default implementation only allows distinguishing of instances, but not by (B) and (C). So two instances of A could be equal, but default wouldn't allow you to compare them in correct way.
If you override equals() and not hashcode(), you will not find any problem unless you or someone else uses that class type in a hashed collection like HashSet.
People before me have clearly explained the documented theory multiple times, I am just here to provide a very simple example.
Consider a class whose equals() need to mean something customized :-
public class Rishav {
private String rshv;
public Rishav(String rshv) {
this.rshv = rshv;
}
/**
* @return the rshv
*/
public String getRshv() {
return rshv;
}
/**
* @param rshv the rshv to set
*/
public void setRshv(String rshv) {
this.rshv = rshv;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof Rishav) {
obj = (Rishav) obj;
if (this.rshv.equals(((Rishav) obj).getRshv())) {
return true;
} else {
return false;
}
} else {
return false;
}
}
@Override
public int hashCode() {
return rshv.hashCode();
}
}
Now consider this main class :-
import java.util.HashSet;
import java.util.Set;
public class TestRishav {
public static void main(String[] args) {
Rishav rA = new Rishav("rishav");
Rishav rB = new Rishav("rishav");
System.out.println(rA.equals(rB));
System.out.println("-----------------------------------");
Set<Rishav> hashed = new HashSet<>();
hashed.add(rA);
System.out.println(hashed.contains(rB));
System.out.println("-----------------------------------");
hashed.add(rB);
System.out.println(hashed.size());
}
}
This will yield the following output :-
true
-----------------------------------
true
-----------------------------------
1
I am happy with the results. But if I have not overridden hashCode(), it will cause nightmare as objects of Rishav with same member content will no longer be treated as unique as the hashCode will be different, as generated by default behavior, here's the would be output :-
true
-----------------------------------
false
-----------------------------------
2
When you want to store and retrieve your custom object as a key in Map, then you should always override equals and hashCode in your custom Object . Eg:
Person p1 = new Person("A",23);
Person p2 = new Person("A",23);
HashMap map = new HashMap();
map.put(p1,"value 1");
map.put(p2,"value 2");
Here p1 & p2 will consider as only one object and map size will be only 1 because they are equal.
public class Employee {
private int empId;
private String empName;
public Employee(int empId, String empName) {
super();
this.empId = empId;
this.empName = empName;
}
public int getEmpId() {
return empId;
}
public void setEmpId(int empId) {
this.empId = empId;
}
public String getEmpName() {
return empName;
}
public void setEmpName(String empName) {
this.empName = empName;
}
@Override
public String toString() {
return "Employee [empId=" + empId + ", empName=" + empName + "]";
}
@Override
public int hashCode() {
return empId + empName.hashCode();
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(this instanceof Employee)) {
return false;
}
Employee emp = (Employee) obj;
return this.getEmpId() == emp.getEmpId() && this.getEmpName().equals(emp.getEmpName());
}
}
Test Class
public class Test {
public static void main(String[] args) {
Employee emp1 = new Employee(101,"Manash");
Employee emp2 = new Employee(101,"Manash");
Employee emp3 = new Employee(103,"Ranjan");
System.out.println(emp1.hashCode());
System.out.println(emp2.hashCode());
System.out.println(emp1.equals(emp2));
System.out.println(emp1.equals(emp3));
}
}
In Object Class equals(Object obj) is used to compare address comparesion thats why when in Test class if you compare two objects then equals method giving false but when we override hashcode() the it can compare content and give proper result.
Both the methods are defined in Object class. And both are in its simplest implementation. So when you need you want add some more implementation to these methods then you have override in your class.
For Ex: equals() method in object only checks its equality on the reference. So if you need compare its state as well then you can override that as it is done in String class.
There's no mention in this answer of testing the equals/hashcode contract.
I've found the EqualsVerifier library to be very useful and comprehensive. It is also very easy to use.
Also, building equals() and hashCode() methods from scratch involves a lot of boilerplate code. The Apache Commons Lang library provides the EqualsBuilder and HashCodeBuilder classes. These classes greatly simplify implementing equals() and hashCode() methods for complex classes.
As an aside, it's worth considering overriding the toString() method to aid debugging. Apache Commons Lang library provides the ToStringBuilder class to help with this.