HashMap collision speed (regression 7->8)

[Bernd Eckenfels]

Am Sat, 10 Jan 2015 17:00:58 -0800
schrieb Martin Buchholz <martinrb at google.com>:

> Why not treeify only when trying to insert an element that is
> instanceof Comparable?  That way, we will not attempt to use less
> efficient treebins when there will be no benefit.

This is my thinking as well, one thing which was unclear to me: when
the keys are not Comparable but their instance is reused for put/get,
will the system hashcode method allow to do a proper tree lookup
anyway (or actually will the code do a tree lookup).

In my Bench equal key objects with different instances are used, and
this is quite common. But in some scenarios it might be likely that the
actual instance of a put key will also be get.

Gruss
Bernd



> 
> Something like:
> 
> diff --git a/src/java.base/share/classes/java/util/HashMap.java
> b/src/java.base/share/classes/java/util/HashMap.java
> --- a/src/java.base/share/classes/java/util/HashMap.java
> +++ b/src/java.base/share/classes/java/util/HashMap.java
> @@ -639,7 +639,8 @@
>                  for (int binCount = 0; ; ++binCount) {
>                      if ((e = p.next) == null) {
>                          p.next = newNode(hash, key, value, null);
> -                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1
> for 1st
> +                        if (binCount >= TREEIFY_THRESHOLD - 1 // -1
> for 1st
> +                            && key instanceof Comparable)
>                              treeifyBin(tab, hash);
>                          break;
>                      }
> @@ -1127,7 +1128,8 @@
>              t.putTreeVal(this, tab, hash, key, v);
>          else {
>              tab[i] = newNode(hash, key, v, first);
> -            if (binCount >= TREEIFY_THRESHOLD - 1)
> +            if (binCount >= TREEIFY_THRESHOLD - 1
> +                && key instanceof Comparable)
>                  treeifyBin(tab, hash);
>          }
>          ++modCount;
> @@ -1199,7 +1201,8 @@
>                  t.putTreeVal(this, tab, hash, key, v);
>              else {
>                  tab[i] = newNode(hash, key, v, first);
> -                if (binCount >= TREEIFY_THRESHOLD - 1)
> +                if (binCount >= TREEIFY_THRESHOLD - 1
> +                    && key instanceof Comparable)
>                      treeifyBin(tab, hash);
>              }
>              ++modCount;
> @@ -1258,7 +1261,8 @@
>                  t.putTreeVal(this, tab, hash, key, value);
>              else {
>                  tab[i] = newNode(hash, key, value, first);
> -                if (binCount >= TREEIFY_THRESHOLD - 1)
> +                if (binCount >= TREEIFY_THRESHOLD - 1
> +                    && key instanceof Comparable)
>                      treeifyBin(tab, hash);
>              }
>              ++modCount;