On a bug in Java’s TreeSet and TreeMap

Recursive pondering

I’m fairly confident that I found a bug, or at least a violation of contract, in Java’s TreeSet and TreeMap – TreeSet, at least currently, is mostly a wrapper around TreeMap.

The documentation for TreeSet gives a contract:

returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).

I created a TreeSet, but gave it a custom comparator that sorted it by ascending String length.

I had 3 items in it, like these:

« BO », « BOB », « ROBERT »

treeSet.contains(« FR ») returned true! After digging through the Java code a little, I realized that the TreeMap contains was not using o.equals(e), but comparator.compare(e, o) ! Therefore, contains would return true whenever the TreeSet contained any item the same length as e.

This could certainly be as designed, but it still breaks the contract.

View original post

Par défaut