hashCode() Method in Java

Hashing is the technique of generating a unique value for a given key. Hashing is used to implement Hash Tables and these data structures provide a faster and more efficient way to lookup data. Hashing is used by a lot of different collections like the HashMap and the HashSet. The hashCode() method returns an integer value(also called the hash or hash value) for a given key.

Java equals() Method

Before moving on, we must know about the equals() method. The equals() method is a simple method that returns true if the two objects being compared are equal, otherwise, it returns false.

• The equals() method is mostly used by data structures to check whether a value is present in the data structure. This is done by comparing the key with all the elements present in the data structure.
• The HashCode() method is usually an addition to a class having the equals() method. The hashCode() method is added to reduce the number of comparisons done by the equals() method.
• If the equals() method is changed then the corresponding hashCode() method should also change.
• For example, consider a student class with student name and the GPA. If we say that two students are equal if just their names are the same, then the HashCode() method should also be written in such a way that it focuses on only the student's name.
• Basically the hashCode() should not take into consideration any fields that are not used by the equals() method for the equality check.

An example of the equals() method is shown below.

public class HashDemo
{
	public static void main(String args[])
	{
		String str1 = "String 1";
		String str2 = "String 2";
		String str3 = "String 1";
		System.out.println("String 1 is equal to String 2: " + str1.equals(str2));
		System.out.println("String 1 is equal to String 1: " + str1.equals(str3));
	}
}

String 1 is equal to String 2: false
String 1 is equal to String 1: true

hashCode() Method

As discussed above, the hashCode() method returns an integer value for the given input. Different IDEs have their own implementations of the hashCode() method and we can directly use them or override them. Any hashCode() method should satisfy the following three conditions. These conditions together are also known as the hashCode Contract.

• The hashCode() method must return the same value for a particular object every time, given that we are not changing the implementation of the hashCode() method or the equals() method, and the object is not modified in any way.
• If the equals() method returns true for two objects, then the hashCode() method must return the same hash value for both the objects.
• The hashCode() can return the same hash value for two objects that are not equal according to the equals() method.

Even though a hashCode() method is completely valid if it returns the same hash value for different inputs, but this method will lead to a lot of collisions when used in the implementation of a Hash Table. The lookup time of the Hash Table will not be constant(O(1)) in that case. There are ways of handling these collisions like probing and chaining but avoiding them is a better option. The best way to avoid collisions is to write a strong hashCode() method.

Example of the inbuilt hashCode() method

The following code demonstrates the working of the inbuilt hashCode() method of the Eclipse IDE.

public class HashDemo
{
	public static void main(String args[])
	{
		String str1 = "String 1";
		String str2 = "String 1";
		String str3 = "String 3";
		
		System.out.println("Hash of Str1: " + str1.hashCode());
		System.out.println("Hash of Str2: " + str2.hashCode());
		System.out.println("String 1 is equal to String 1: " + str1.equals(str2));
		System.out.println("Hash of Str3: " + str3.hashCode());
		System.out.println("String 1 is equal to String 3: " + str1.equals(str3));
	}
}

Hash of Str1: 1859651586
Hash of Str2: 1859651586
String 1 is equal to String 1: true
Hash of Str3: 1859651588
String 1 is equal to String 3: false

Working of Hash Tables

Hash Tables are a type of data structure that store data in different buckets based on the hash value of the data. This way when we need to search for an element, we can directly go to that particular bucket without the need of searching each bucket. The basic working of Hash Tables is summarised below.

• When an element is added, its hash value is generated by using the hashCode() function.
• This hash value determines the bucket where the element should be added. If the hashCode() method is not very strong and generates duplicate values for different elements, then more than one element will be present in a single bucket.
• When searching for an element, first the hashCode() is generated for the element and we directly search in the bucket where it should be present. If more than one object is present in the bucket then we can use the equals() method to search for the correct element in the bucket.

Example: Implementing hashCode() methods

Let's try to create a student class and implement our own hashCode() and equals() methods. First, we will implement a basic hashCode() method that just returns an integer based on the first letter of the student's name.

class Student
{
	String name;
	int regNo;
	double gpa;
	
	Student(String name, int regNo, double gpa)
	{
		this.name = name;
		this.regNo = regNo;
		this.gpa = gpa;
	}
	
	@Override
	public int hashCode()
	{
		return (int)this.name.charAt(0) - 64;
	}
	
	@Override
	public boolean equals(Object obj)
	{
		if(obj == null)
			return false;
		if(this == obj)
			return true;
		if(obj.getClass() != this.getClass())
			return false;
		Student s = (Student)obj;
		return this.name == s.name &&
			   this.regNo == s.regNo && 
			   this.gpa == s.gpa;
	}
}

public class HashDemo
{
	public static void main(String args[])
	{
		Student s1 = new Student("Justin", 59, 7.6);
		Student s2 = new Student("Jessica", 21, 8.0);
		Student s3 = new Student("Paul", 20, 5.5);
		Student s4 = new Student("Justin", 59, 7.6);
		
		System.out.println("Hash of s1: " + s1.hashCode());
		System.out.println("Hash of s2: " + s2.hashCode());
		System.out.println("Hash of s3: " + s3.hashCode());
		
		System.out.println("s1 is the same as s2: " + s1.equals(s2));
		System.out.println("s1 is the same as s4: " + s1.equals(s4));
		
	}
}

Hash of s1: 10
Hash of s2: 10
Hash of s3: 16
s1 is the same as s2: false
s1 is the same as s4: true

The above hashCode() method is completely valid as it satisfies all the conditions of the contract but it is not very strong as different students with the same first letter of the name will be assigned the same hash value. Let's use the other fields of the class to write a stronger hashCode() method.

class Student
{
	String name;
	int regNo;
	double gpa;
	
	Student(String name, int regNo, double gpa)
	{
		this.name = name;
		this.regNo = regNo;
		this.gpa = gpa;
	}
	
	@Override
	public int hashCode()
	{
		return ((int)this.name.charAt(0) - 64) * this.regNo * (int)this.gpa;
	}
	
	@Override
	public boolean equals(Object obj)
	{
		if(obj == null)
			return false;
		if(this == obj)
			return true;
		if(obj.getClass() != this.getClass())
			return false;
		Student s = (Student)obj;
		return this.name == s.name &&
			   this.regNo == s.regNo && 
			   this.gpa == s.gpa;
	}
}


public class HashDemo
{
	public static void main(String args[])
	{
		Student s1 = new Student("Justin", 59, 7.6);
		Student s2 = new Student("Jessica", 21, 8.0);
		Student s3 = new Student("Paul", 20, 5.5);
		Student s4 = new Student("Justin", 59, 7.6);
		
		System.out.println("Hash of s1: " + s1.hashCode());
		System.out.println("Hash of s2: " + s2.hashCode());
		System.out.println("Hash of s3: " + s3.hashCode());
		System.out.println("Hash of s4: " + s4.hashCode());
		
		System.out.println("s1 is the same as s2: " + s1.equals(s2));
		System.out.println("s1 is the same as s4: " + s1.equals(s4));
		
	}
}

Hash of s1: 4130
Hash of s2: 1680
Hash of s3: 1600
Hash of s4: 4130
s1 is the same as s2: false
s1 is the same as s4: true

Example: Using inbuilt hashCode() method in our implementation

The above hashCode() method is better than the previous one. Let's now use the inbuilt hashCode() method in our implementation of the hashCode() method.

@Override
public int hashCode()
{
	return this.name.hashCode() * this.regNo * (int)this.gpa;
}

Frequently Asked Questions

Q. Why is the number 31 used in some hashCode() methods?

31 is an odd prime number. If an even number is used then it would lead to overflow as multiplication by 2 is the same as shifting. Modern virtual machines are replacing the use of 31 by shift and subtraction.

Q. Can we get the original key back if we know its hash value?

No, any hash function should not be reversible. Hashing is performed to convert large data into a fixed set of integers. Multiple keys can get the same hash value and so it is not possible to get the original key back.

Q. What will happen if we override or change the equals() method but not the hashCode() method?

If we override the equals() method but the hashCode() method is not changed then the parameters that the equals() method uses to check for equality of two objects may not be used by the hashCode() method. This can lead to two equal objects having different hash values, and this violates the conditions of the hashCode contract.

Summary

Hashing is an important technique that is used in a lot of different collections to improve the look-up time. hashCode() method is used to generate the hash value required by these data structures. A hashCode() method must satisfy the three conditions of the contract. However, a strong hashCode() method should not return the same value for different objects as it leads to collisions.