Sets in Java are a great way of automatically preventing duplicates. By offloading the overhead to a standard library, you save time by not having to remove duplicates on your own or calling a removeDuplicates() method.

The problem

In a current project, I am using the LinkedHashSet implementation so that 1) elements are sorted in insertion order and 2) the nature of the LinkedHashSet prevents duplicates. However, I wanted to implement my own way of determining if two arbitrary objects e1 and e2 are duplicates.

According to the documentation for the Set interface, Sets determine duplicity through the Object.equals method.

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.

All we need to do is override the equals() method for our class type. Or so it seems. Let’s consider a class Bloop, where all Bloops are “equal” to each other.

class Bloop {
	@Override
	public boolean equals(Object b) {
		// All Bloops were created equal
		return true;
	}
}

According to the Set documentation, this is sufficient to ensure that no more than one Bloop is inserted into a LinkedHashSet<Bloop<.

However, running the test code below fails.

@Test
public void test() {
	Set<Bloop> s = new LinkedHashSet<Bloop>();
	Bloop b1 = new Bloop();
	Bloop b2 = new Bloop();
	assertTrue(b1.equals(b2)); // this passes...
	s.add(b1);
	s.add(b2);
	assertEquals("Size not matching", 1, s.size()); // but this fails!
}

As the test reveals, the size of the Set after the calls to add is 2, not 1. This indicates that both Bloop objects were added.

The solution

It turns out, that the LinkedHashSet requires more than just the two Bloops to be equal. Since the LinkedHashSet uses a hash table into which entries are inserted, it also needs to compare the hash codes of the object to be inserted against the objects already in its internal hash table. Does this ring a bell? We need to override Object.hashCode() for our Bloop as well. Let’s keep the specification that all Bloops are created equal.

@Override
public int hashCode() {
	return 0;
}

Now, for any Bloop b1, b2, b1.equals(b2) == true and b1.hashCode() == b2.hashCode(). Now our test passes:

public class BloopTest {
	@Test
	public void test() {
		Set<Bloop> s = new LinkedHashSet<Bloop>();
		Bloop b1 = new Bloop();
		Bloop b2 = new Bloop();
		s.add(b1);
		s.add(b2);
		assertEquals("Size not matching", 1, s.size()); // passes
	}
}
class Bloop {
	@Override
	public boolean equals(Object b) {
		return true;
	}
	@Override
	public int hashCode() {
		return 0;
	}
}

Footnotes

The assertEquals() method is from the JUnit testing library (org.junit.Test), namely the org.junit.Assert.* packages.

Published by Geoffrey Liu

A software engineer by trade and a classical musician at heart. Currently a software engineer at Groupon getting into iOS mobile development. Recently graduated from the University of Washington, with a degree in Computer Science and a minor in Music. Web development has been my passion for many years. I am also greatly interested in UI/UX design, teaching, cooking, biking, and collecting posters.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.