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

IdentityHashMap.hash comments should be clarified

    XMLWordPrintable

    Details

      Description

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


      ADDITIONAL OS VERSION INFORMATION :
      RHEL 6.4 (but that's irrelevant)

      A DESCRIPTION OF THE PROBLEM :
      The code for the method hash() does not match the comment and contains a simple bug.

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      Look at the source code for the method hash() in class java.util.IdentityHashMap.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      Should calculate (-127*hashCode)&(length-1)
      ACTUAL -
      Actually calculates (-254*hashCode)&(length-1)

      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      Here is the source for the method hash():


          private static int hash(Object x, int length) {
              int h = System.identityHashCode(x);
              // Multiply by -127, and left-shift to use least bit as part of hash
              return ((h << 1) - (h << 8)) & (length - 1);
          }


      Note that it says "multiply by -127", but the effect of the operation ((h<<1)-(h<<8)) is in fact "multiply by -254".

      This is significant because it means that odd-numbered buckets are simply never accessible, so average occupancy in buckets will be nearly 2 by the time of a resize.

      Also the implementation critically depends on the assumption that identityHashCode() produces a well-distributed range of values. I don't know that this is really the case.
      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      Try modifying the source to say (-127*h)&(length-1). This is correct, not obfuscated and will probably produce better code anyway as it allows the JIT to take a crack at the code.

        Attachments

          Issue Links

            Activity

              People

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

                Dates

                Created:
                Updated:
                Resolved: