Edd Edd - 2 months ago 11
Java Question

Why do I seem able to add two objects that are equal() to each other to a TreeSet

When adding objects to a

java.util.TreeSet
, you'd hope that two equal objects would only exist once when both have been added, and the following test passes as expected:

@Test
void canAddValueToTreeSetTwice_andSetWillContainOneValue() {
SortedSet<String> sortedSet = new TreeSet<>(Comparator.naturalOrder());

// String created in a silly way to hopefully create two equal Strings that aren't interned
String firstInstance = new String(new char[] {'H', 'e', 'l', 'l', 'o'});
String secondInstance = new String(new char[] {'H', 'e', 'l', 'l', 'o'});

assertThat(firstInstance).isEqualTo(secondInstance);
assertThat(sortedSet.add(firstInstance)).isTrue();
assertThat(sortedSet.add(secondInstance)).isFalse();
assertThat(sortedSet.size()).isEqualTo(1);
}


Wrap these Strings in a wrapper class, where the
equals()
and
hashCode()
are based solely on the wrapped class, though and the test fails:

@Test
void canAddWrappedValueToTreeSetTwice_andSetWillContainTwoValues() {
SortedSet<WrappedValue> sortedSet = new TreeSet<>(Comparator.comparing(WrappedValue::getValue).thenComparing(WrappedValue::getCreationTime));

WrappedValue firstInstance = new WrappedValue("Hello");
WrappedValue secondInstance = new WrappedValue("Hello");

assertThat(firstInstance).isEqualTo(secondInstance); // Passes
assertThat(sortedSet.add(firstInstance)).isTrue(); // Passes
assertThat(sortedSet.add(secondInstance)).isFalse(); // Actual: True
assertThat(sortedSet.size()).isEqualTo(1); // Actual: 2
}

private class WrappedValue {
private final String value;
private final long creationTime;

private WrappedValue(String value) {
this.value = value;
this.creationTime = System.nanoTime();
}

private String getValue() {
return value;
}

private long getCreationTime() {
return creationTime;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof WrappedValue)) return false;
WrappedValue that = (WrappedValue) o;
return Objects.equals(this.value, that.value);
}

@Override
public int hashCode() {
return Objects.hash(value);
}
}


The JavaDoc for
TreeSet.add()
states what we'd expect:


Adds the specified element to this set if it is not already present. More formally, adds the specified element
e
to this set if the set contains no element
e2
such that
(e==null ? e2==null : e.equals(e2))
. If this set already contains the element, the call leaves the set unchanged and returns
false
.


Given my assertion that the two objects are
equal()
, I'd expect this to pass. I'm working on the assumption that I'm missing something mindnumpingly obvious, unless
TreeSet
doesn't actually use
Object.equals()
, but uses something that's near enough the same in the vast majority of cases.

This was observed using JDK 1.8.0.60 - I've not had chance to test other JDKs yet, but I'm presuming there's some "Operator Error" somewhere...

Answer

The problem is that the comparator given to sort the set is incompatible with the equals method of WrappedValue. You are expecting the SortedSet to behave like a Set, but it doesn't do so in this case.

From SortedSet:

Note that the ordering maintained by a sorted set [...] must be consistent with equals if the sorted set is to correctly implement the Set interface. [...] This is so because the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal. The behavior of a sorted set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

Put another way, the SortedSet only uses the comparator you gave in order to determine if two elements are equal. The comparator in this case is

Comparator.comparing(WrappedValue::getValue).thenComparing(WrappedValue::getCreationTime)

which compares the value and then the creation time. But since the constructor of WrappedValue initializes an (effectively) unique creation time with System.nanoTime(), no two WrappedValue will be considered equal by this comparator. Therefore, as far as the sorted set is concerned

WrappedValue firstInstance = new WrappedValue("Hello");
WrappedValue secondInstance = new WrappedValue("Hello");

are two distinct objects. Indeed, if you modify a little the constructor to add a long creationTime parameter, and give the same time to both instances, you'll notice the "expected" result (i.e. the sorted set will only have a size of 1 after adding the two instances).

So there are 3 solutions here:

  1. Fix the equals and hashCode methods and let them compare both the value and the time.
  2. Only give a comparator comparing the value.
  3. Accept the fact that the SortedSet doesn't behave like a Set in this particular case.
Comments