[15] RFR (xs) 8046362 IdentityHashMap.hash comments should be clarified

[Stuart Marks]

Hi all,

I was looking through the bug database and I got nerd-sniped this bug report, 
which requests clarifying a comment in IdentityHashMap. Once I figured out what 
was going on, I decided I might as well just go ahead and fix it.

This changeset improves (I hope) the comment in the IdentityHashSet.hash() 
method. In addition, I've also clarified the note in the class documentation to 
make the keys/values at even/odd indexes arrangement in the array more explicit, 
which has also been a source of some confusion.

This changes only non-normative portions of the specification, so I don't 
believe a CSR is necessary.

As an aside, I don't know whether the linear-probing (open addressed) 
arrangement of IdentityHashMap is in fact faster than the separate chaining 
approach of HashMap. Perhaps investigating that could be a side project for someone.

Changeset appended below.

Bug: https://bugs.openjdk.java.net/browse/JDK-8046362

Thanks,

s'marks



# HG changeset patch
# User smarks
# Date 1580167577 28800
#      Mon Jan 27 15:26:17 2020 -0800
# Node ID 0e08ce23484ca42597105225ffa3dd0827cb4b60
# Parent  981f6982717a7df4a2a43dd0ae6b2c2389e683f9
8046362: IdentityHashMap.hash comments should be clarified
Reviewed-by: XXX

diff -r 981f6982717a -r 0e08ce23484c 
src/java.base/share/classes/java/util/IdentityHashMap.java
--- a/src/java.base/share/classes/java/util/IdentityHashMap.java	Mon Jan 27 
14:03:58 2020 -0800
+++ b/src/java.base/share/classes/java/util/IdentityHashMap.java	Mon Jan 27 
15:26:17 2020 -0800
@@ -1,5 +1,5 @@
  /*
- * Copyright (c) 2000, 2019, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2000, 2020, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
@@ -115,17 +115,19 @@
   * exception for its correctness: <i>fail-fast iterators should be used only
   * to detect bugs.</i>
   *
- * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
- * as described for example in texts by Sedgewick and Knuth.  The array
- * alternates holding keys and values.  (This has better locality for large
- * tables than does using separate arrays.)  For many JRE implementations
- * and operation mixes, this class will yield better performance than
- * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).
- *
   * <p>This class is a member of the
   * <a 
href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
   * Java Collections Framework</a>.
   *
+ * @implNote
+ * <p>This is a simple <i>linear-probe</i> hash table,
+ * as described for example in texts by Sedgewick and Knuth.  The array
+ * contains alternating keys and values, with keys at even indexes and values
+ * at odd indexes. (This arrangement has better locality for large
+ * tables than does using separate arrays.)  For many JRE implementations
+ * and operation mixes, this class will yield better performance than
+ * {@link HashMap}, which uses <i>chaining</i> rather than linear-probing.
+ *
   * @see     System#identityHashCode(Object)
   * @see     Object#hashCode()
   * @see     Collection
@@ -293,7 +295,7 @@
       */
      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
+        // Multiply by -254 to use the hash LSB and to ensure index is even
          return ((h << 1) - (h << 8)) & (length - 1);
      }