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

Need better testing for IdentityHashMap

    XMLWordPrintable

Details

    • Bug
    • Resolution: Fixed
    • P4
    • 19
    • None
    • core-libs
    • None

    Description

      Unlike for other collections, there don't seem to be any fundamental tests for IdentityHashMap. Most basically, there should be tests to ensure that membership in the map is identity-based and not value-based.

      For example, consider what should happen if the following (erroneous!) patch is applied to IdentityHashMap.

      --- a/src/java.base/share/classes/java/util/IdentityHashMap.java
      +++ b/src/java.base/share/classes/java/util/IdentityHashMap.java
      @@ -296,7 +296,7 @@ public class IdentityHashMap<K,V>
            * Returns index for Object x.
            */
           private static int hash(Object x, int length) {
      - int h = System.identityHashCode(x);
      + int h = x.hashCode();
               // Multiply by -254 to use the hash LSB and to ensure index is even
               return ((h << 1) - (h << 8)) & (length - 1);
           }
      @@ -333,10 +333,10 @@ public class IdentityHashMap<K,V>
               int i = hash(k, len);
               while (true) {
                   Object item = tab[i];
      - if (item == k)
      - return (V) tab[i + 1];
                   if (item == null)
                       return null;
      + if (item.equals(k))
      + return (V) tab[i + 1];
                   i = nextKeyIndex(i, len);
               }
           }

      This patch essentially changes the get() method to look up by value instead of by identity. Normally IDHM works like this:

          jshell> record Box(int i) {}
          jshell> var box1 = new Box(0)
          box1 ==> Box[i=0]
          jshell> var box2 = new Box(0)
          box2 ==> Box[i=0]
          jshell> box1 == box2
          $79 ==> false
          jshell> box1.equals(box2)
          $80 ==> true
          jshell> var map = new IdentityHashMap<Box, String>()
          map ==> {}
          jshell> map.put(box1, "a")
          jshell> map.put(box2, "b")
          jshell> map
          map ==> {Box[i=0]=b, Box[i=0]=a}
          jshell> map.get(box1)
          $86 ==> "a"
          jshell> map.get(box2)
          $87 ==> "b"
          jshell> map.get(new Box(0))
          $88 ==> null
          
      However, with this patch in place, the behavior is as follows:

          jshell> record Box(int i) {}
          jshell> var box1 = new Box(0)
          box1 ==> Box[i=0]
          jshell> var box2 = new Box(0)
          box2 ==> Box[i=0]
          jshell> box1 == box2
          $4 ==> false
          jshell> box1.equals(box2)
          $5 ==> true
          jshell> var map = new IdentityHashMap<Box, String>()
          map ==> {}
          jshell> map.put(box1, "a")
          jshell> map.put(box2, "b")
          jshell> map
          map ==> {Box[i=0]=a, Box[i=0]=b}
          jshell> map.get(box1)
          $10 ==> "a"
          jshell> map.get(box2)
          $11 ==> "a"
          jshell> map.get(new Box(0))
          $12 ==> "a"

      This is of course completely incorrect. However, with this patch applied, tiers 1, 2, and 3 of the regression suite don't report any failures at all! Failures do occur in a variety of java/beans/XMLEncoder tests (tier 4) because they apparently do rely on the identity semantics of IdentityHashMap.

      Some fundamental tests for IdentityHashMap should be added to test/jdk/java/util/IdentityHashMap, which will put them into the jdk_collections_core test group, which is in tier 1.

      Attachments

        Issue Links

          Activity

            People

              smarks Stuart Marks
              smarks Stuart Marks
              Votes:
              1 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: