HashMap collision speed (regression 7->8)

[Martin Buchholz]

On further reflection, treebins *can* help when elements are not mutually
comparable, *if* they have different hashcodes.  The treebin is sorted by
hashcode first, then by their Comparable relationship.

On Sat, Jan 10, 2015 at 5:22 PM, Bernd Eckenfels <ecki at zusammenkunft.net>
wrote:

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