I am a software engineer at Google on the Android project and the creator of the Java testing framework TestNG. When I'm not updating this weblog with various software-related posts or speaking at conferences, I am busy snowboarding, playing squash, tennis, golf or volleyball or scuba diving. Cedric is a DZone MVB and is not an employee of DZone and has posted 90 posts at DZone. You can read more from them at their website. View Full User Profile

Answer to the "School" Challenge

02.22.2013
| 2795 views |
  • submit to reddit

I’m happy to see mostly correct answers to the School coding challenge.

To make things more interesting, let’s start by looking at a naïve (and wrong) solution:

@Override
public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + ((name == null) ? 0 : name.hashCode());
  result = prime * result + ((nickname == null) ? 0 : nickname.hashCode());
  return result;
}

@Override
public boolean equals(Object obj) {
  // ... details omitted
  return other.nickname.equals(nickname) || other.name.equals(name);
}

Let’s create two School objects, make sure they are equal, add them to a set and then display this set:

School school1 = new School("University of Pennsylvania", "upenn");
School school2 = new School("University of Pennsylvania", "Penn State");
System.out.println("Equals: " + school1.equals(school2));
Set<School> schools = Sets.newHashSet();
schools.add(school1);
schools.add(school2);
System.out.println("Set: " + schools);

The output:

Equals: true
Set: [com.beust.School@d8e612c6, com.beust.School@7086780a]

This is obviously wrong and caused by the fact that this implementation breaks several laws, among which: “if two objects are equal, their hashcode should be equal as well”. However, this is clearly not the case here since the two objects instantiated in the main method are equal but their hash code are different, since it’s calculated from both the name and nickname. The consequences of such an implementation are disastrous in more ways than one, starting with the fact that your objects cannot reliably be stored in nor retrieved from identity-based collections (e.g. sets and maps).

The only way out of this would be to return a variable hashcode, but this doesn’t make sense since we wouldn’t know what field to base that hash code on.

Most commenters came up with the idea of always returning the same value for hashCode(), regardless of the name and nickname values. This approach is actually correct but it comes at the cost of losing all running time benefits offered by sets and maps, such as constant time retrievals. Instead, Hashmap#get and Set#contains are now linear operations. That’s a pretty bad prank to pull on your coworkers when their collections can contain millions of objects.

So, what’s the best way to solve this problem?

I’m not quite sure. There are several approaches, all with their pros and cons.

The first idea would be to not override equals and hashCode, using their default implementation defined on Object. This implementation (simple reference equality test) is guaranteed to be wrong in most cases, but since you can’t write a correct one, maybe the best approach is to do nothing.

Another approach would be to throw an OperationNotSupportedException in equals/hashCode. The implementation is still wrong but at least, your program will crash loudly if someone attempts to put these objects in an identity-based collection.

Ultimately, you really want to get rid of the fuzzy matching performed in the equals method, so the best approach is probably to perform a first pass on all your School objects and unify all those that are equal under the same id. After this, you can implement equals/hashCode based on this id field.




 

Published at DZone with permission of Cedric Beust, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Nils Rudolph replied on Fri, 2013/02/22 - 5:07am

The problem is not the hashCode function the problem is the equals function which violates the transitive property, see http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#equals(java.lang.Object) and my reply on the challenge post.

If you start with a broken equals implementation you will end with a broken hashCode implementation. And you will never know if someone use some code which relies on the transitive property. Example:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;


public class School {
	private String name;
	private String nickname;
	
	public School(String name, String nickname) { 
		this.name = name;
		this.nickname = nickname;
	}
	
	public boolean equals(Object obj) {
		if (obj instanceof School) {
			School other = (School) obj;
			return (name != null && name.equals(other.name)) ||
					(nickname != null && nickname.equals(other.nickname));
		}
		
		return false;
	}
	
	public static boolean areAllEqual(List<School> schools) {
		Random rnd = new Random();
		School pivot = schools.get(rnd.nextInt(schools.size()));
		for (School school : schools) {
			if (pivot.equals(school) == false) {
				return false;
			}
		}
		
		return true;
	}
	
	public static void main(String[] args) {
		List<School> test = new ArrayList<School>();
		test.add(new School("A", null));
		test.add(new School("A", "B"));
		test.add(new School("D", "B"));
		
		System.out.println(areAllEqual(test));
	}
}

The outcome of areAllEqual is not deterministic, run it multiple times and you will get true and false values. With a correct equals implementation it will always be the same value. 

If you really need to match School objects based on your description, do not override equals and hashCode and move the matching code to a utility method. Eg. SchoolMatcher.matches(School first, School second)

But the best solution would be, that you fix the definition of equality for your domain objects. (If this is possible)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.