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 <e...@zusammenkunft.net>
wrote:
> Am Sat, 10 Jan 2015 17:00:58 -0800
> schrieb Martin Buchholz <marti...@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;
>
>
