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

Stuart Marks stuart.marks at oracle.com
Tue Feb 11 00:09:41 UTC 2020



On 2/10/20 7:52 AM, Martin Buchholz wrote:
> On Fri, Feb 7, 2020 at 2:47 PM David Holmes <david.holmes at oracle.com> wrote:
> 
>> Hi Martin,
>>
>> On 8/02/2020 3:10 am, Martin Buchholz wrote:
>>> I explored System.identityHashCode (see below).
>>
>> System.identityHashCode is a VM call that is potentially very expensive.
>> In the worst-case it triggers monitor inflation.
>>
> 
> I can believe that.  The VM can't simply return the address of an object
> because ... the object might move and an address is a poor hash code
> because low bits will tend to be zero.
> 
> But  IdentityHashMap already calls System.identityHashCode - that price
> must be paid.
> 
> My proposal is still "Let's trust System.identityHashCode to produce
> acceptable hash codes"

OK... I appreciate that there are a bunch of subtle issues here, from whether 
it's necessary to do mixing of the identity hash code to whether an 
open-addressed table really is faster than separate chaining in this case. 
Before we go on too long, though, I'd like to ask what to do about my proposed 
comments changes.

Should I proceed with pushing my comments changes (which I've appended below for 
convenience)? Or is somebody going to dive in right away and make changes that 
will invalidate my proposed comments changes, and thus I should hold off pushing 
them?

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);
      }



More information about the core-libs-dev mailing list