Home » Articles » Technical Articles

 Search   Site Map  

Implementing hashCode()

written by Tim

Introduction

The public int hashCode() method in java.lang.Object is implemented to return a unique value for each newly created instance of an object. One of the most important usages of this method is for the java.util.Map subclasses to be able to find a specific key or value in the Map. As we will see in the article, your application can have great performance benefits by implementing the mehod.

Example

We will be using the class throughout the whole article.

public class Person {

   private String lastName;
   private String firstName;
   private int hashcode;

   public Person(String lastName, String firstName) {
     this.lastName = lastName;
     this.firstName = firstName;
   }

   public boolean equals(Object o) {
     Person person = (Person)o;
     return (person.firstName.equals(this.firstName)
       && person.lastName.equals(this.lastName));
   }

}

Now, if we were to use this class in a Map (Hashmap in this example) :

package net.javacoding;

import java.util.Map;
import java.util.HashMap;

public class PersonFinder {

   private void findPersons() throws Exception {
   Map hashMap = new HashMap();

   Person person1 = new Person("Homer", "Simpson");
   Person person2 = new Person("Homer", "Simpson");

   hashMap.put(person1, "person1 address");
   assert hashMap.containsKey(person2);
   System.out.println("Homer was found");
}

public static void main(String[] args) throws Exception {
   new PersonFinder().findPersons();
}
}

The output will be (Be sure to run this using the -ea parameter to enable assertions on your VM) :

Exception in thread "main" java.lang.AssertionError: DOH !
at net.javacoding.PersonFinder.findPersons(PersonFinder.java:20)
at net.javacoding.PersonFinder.main(PersonFinder.java:25)

So, the hashMap could not find Homer Simpson even if you implemented the equals() method and this is where the hashCode() method comes in. The map considers two objects as being equal if their hashcode is the same, if this is the case, it will verify this using the equals() method. So, the easiest way of dealing with this is adding the hashCode() method in the Person class.

public int hashCode() {
   return 0;
}

Then the output is:

Homer was found

This is a satisfying result, but it uses more system resources than nessesary.

overriding the hashCode() method

The idea is to generate a code (as integer) for a unique name/firstname and return it in the hashCode() method. This will increase performance dramatically when searching in large data maps. Using the formula:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

where s[i] is the ith character of the string,
n is the length of the string,
and ^ indicates exponentiation.
(The hash value of the empty string is zero.)

Implementing this in java makes the Person class look like this :

package net.javacoding;

/**
* @author Tim Goffings
*/
public class Person {

     private String lastName;
     private String firstName;

   private int hashcode;

   public Person(String lastName, String firstName) {
     this.lastName = lastName;
     this.firstName = firstName;

     generateHashCode(lastName + firstName);
}

/**
* makes a close-to-unique hashcode for extra performance
* @param hash the string on which to perform the hashing function
*/
   private void generateHashCode(String hash) {
     char[] chars = hash.toCharArray();
     for (int i = 0; i < chars.length; i++) {
     char aChar = chars[i];
     hashcode += aChar*31^(hash.length() - (i+1));
   }
}

   public int hashCode() {
     return hashcode;
   }

   public boolean equals(Object o) {
     Person person = (Person)o;
     return (person.firstName.equals(this.firstName)
       && person.lastName.equals(this.lastName));
   }
}

Running the person class will not throw an assertion error but find that the two Homer Simpsons are the same.

Clever people will remark that using this code :

Person person1 = new Person("Homer", "Simpson");
Person person2 = new Person("Hom", "erSimpson");

will generate two equal hashCodes but this is not a concern since the Map will use the equals() method to compare the objects if both hashcodes are the same. Should you be concerned that this will occur alot, you can write

generateHashCode(lastName + "_" + firstName);

in the Person constructor.

Trap

An important remark to make sure you don't step into any traps.

As you can see, the Person class is immutable; after it is created, you can't change the first or last name, so the hashcode stays intact. Should you make Person mutable (for example if you provide setter methods for the first and lastname) and change its values after it is put in the Map, when you ask the map to retrieve this object as a key, the map will ask the object for its hash code which will now be different (field values changed). Map will go to the location indicated by the hash code and will not find any object which equals your object. (The object was originally stored at a completely different location as indicated by the hash code from the old data field values). So, the Map will return null. The object as a key is now hopelessly lost in the map. You can still get to it if you get all the keys from the map and iterate over them, calling objectInHand.equals(eachKey), but that's a manual process that you will need to implement. You cannot say hashtable.get(objectInHand) and hope to get back the object. A map with "lost" data will have "dangling" references to objects. Java cannot garbage-collect these objects because your map is holding references to them. And you cannot directly access those objects in the hashtable because the hash code has changed!

From JDK documentation: "Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on a such a map."

New site design

Hope you like our new, more readable site design.

2004-03-07

JSpider project

We are officially announcing our newest project, JSpider!

2003-01-17   more ...

Articles section online

Our articles section is there! Subjects of all kind are covered.

2002-10-01   more ...

Please visit
WHIZlabs Software

they've got very good Certification test simulators!

BEA WebLogic & MySQL

Learn how to configure a MySQL datasource in BEA WebLogic in this article ...

Java WebServices

Read our book review of Beginning Java Webservices, and download a sample chapter!

Bruce Eckel e-books

We're mirroring some of Bruce Eckel's free e-books on Java and design patterns here!

http://www.javacoding.net