Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8181579

Inconsistency between API documentation and TreeSet.add(...) behaviour

    XMLWordPrintable

    Details

      Description

      FULL PRODUCT VERSION :
      java version "1.8.0_121"
      Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
      Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)


      ADDITIONAL OS VERSION INFORMATION :
      Windows 10 x64

      A DESCRIPTION OF THE PROBLEM :
      A DESCRIPTION OF THE PROBLEM :
      API documentation for TreeSet.add(E e) is not consistent with class behaviour.

      The documentation states that: "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))."

      However, the implementation does not actually use equals, it uses compareTo; an equivalent statement of the actual behaviour would be as follows: "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.compareTo(e2)==0)."

      These two are NOT equivalent, since there is no strict requirement on compareTo to be consistent with equals (see documentation for interface Comparable).

      Although this behaviour means that TreeSet and other set implementations (e.g. HashSet) have different mechanisms for detecting equality of members, a fix for this might not be considered backwards compatible (despite being consistent with existing documentation), so my request is simply for a change to the documentation as suggested above.

      There may be other methods (addAll?) which display the same mismatch between advertised and actual behaviour, but I've not checked them.

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      Create a class which implements Comparable, and override Object.equals such that e1.compareTo(e2)==0 and e1.equals(e2)==true are not synonymous. For a quick test, make equals always return false and compareTo always return zero.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      Expected behaviour (to be consistent with the documentation) is that insertion of multiple such objects into either a TreeSet or a HashSet will succeed, since both claim reliance on equals to determine uniqueness.

      ACTUAL -
      Iow, inserting multiple such objects into a TreeSet will fail (contrary to the documentation), while inserting them into a HashSet will succeed.

      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      import java.util.HashSet;
      import java.util.TreeSet;

      public class TreeSetTest {

      /*
      * This inner class deliberately has a compareTo method that is not consistent with equals
      */
      static class TestObject implements Comparable<TestObject> {
      @Override
      public int compareTo(TestObject arg0) {
      // No two of these objects can be ordered
      return 0;
      }

      @Override
      public boolean equals(Object arg0) {
      // No two of these objects are ever equal to each other
      return false;
      }
      }

      public static void printSuccess(boolean success) {
      if (success) System.out.println(" Success");
      else System.out.println(" Failure");
      }

      public static void main(String[] args) {
      TreeSet<TestObject> testTreeSet = new TreeSet<TestObject>();
      HashSet<TestObject> testHashSet = new HashSet<TestObject>();

      System.out.println("Adding to the HashSet:");
      printSuccess(testHashSet.add(new TestObject()));
      printSuccess(testHashSet.add(new TestObject()));
      printSuccess(testHashSet.add(new TestObject()));

      System.out.println("Copying to the TreeSet:");
      for (TestObject to : testHashSet) {
      printSuccess(testTreeSet.add(to));
      }
      }
      }

      ---------- END SOURCE ----------

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              smarks Stuart Marks
              Reporter:
              webbuggrp Webbug Group
              Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

                Dates

                Created:
                Updated: