Set
s 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, Set
s determine duplicity through the Object.equals
method.
A collection that contains no duplicate elements. More formally, sets contain no pair of elements
e1
ande2
such thate1.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 Bloop
s 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 Bloop
s 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 Bloop
s 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.