Java 8 hashmap implementation using TreeNode instead of linkedlist

Question

According to this post:

http://coding-geek.com/how-does-a-hashmap-work-in-java/

java 8 hashmaps use a treenode instead of a linkedlist (as in java 7) as elements of the array.

TreeNodes have the special property of acting as a linkedlist if the number of elements are small, and acting as a red black tree if there is a large number of elements. (Since operations involving a red black tree are log(n)).

However, doesn't this require the key to be Comparable or some ordering of the keys to exist?

Is this enforced in the java 8 hashmap? Will it only use red black trees if the keys are Comparable (ordering of keys exist)?

"However, doesn't this require the key to be Comparable or some ordering of the keys to exist?" no off course not — Shahzeb
– Shahzeb, Commented Jul 12, 2015 at 23:43
Tree bins (i.e., bins whose elements are all TreeNodes) are ordered primarily by hashCode, but in the case of ties, if two elements are of the same "class C implements Comparable<C>", type then their compareTo method is used for ordering. — Sotirios Delimanolis
– Sotirios Delimanolis, Commented Jul 12, 2015 at 23:47
Shahzeb, why not? @SotiriosDelimanolis, are you referring to the key as class C? what if it doesn't implement Comparable<C>? i understand that the tree bins are ordered by their hashcode, i'm talking about the searching within the TreeNodes — Anik Rahman
– Anik Rahman, Commented Jul 13, 2015 at 0:28
It looks like the algorithm uses System.identityHashCode to order the tree nodes. This is the hash code that's used by default if you don't supply your own hashCode(), and it's based on the reference (sort of like the "address"). All that matters is that some consistent value be used, and identityHashCode is good enough. — ajb
– ajb, Commented Jul 13, 2015 at 0:41
That isn't true. A hash table contains a limited number of buckets. To determine what bucket to put the object in, you typically compute hashCode() % bucketCount. If two objects are going into the same bucket, that means that hashCode() % bucketCount will be the same--but it does not mean that the hashCode() is the same. Therefore the hashCode() can still be used for comparison. And even if the hashCode() is the same, the System.identityHashCode will still most likely be different. — ajb
– ajb, Commented Jul 13, 2015 at 5:53

dantiston · Accepted Answer · 2017-12-23 22:36:38Z

3

Will it only use red black trees if the keys are Comparable (ordering of keys exist)?

No, when HashMap is small all collisions are resolved as LinkedList. Look at the source:

/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st, TREEIFY_THRESHOLD = 8
    treeifyBin(tab, hash);
    break;

treeifyBin() method will convert all collisions to treemap when threshold is reached.

However, doesn't this require the key to be Comparable or some ordering of the keys to exist?

You can put any keys to hashmap. According to the java doc, null is a valid key, and since null is not Comparable, keys do not have to be Comparable. If a key is not Comparable it will be put as LinkedList (through inner table if array already converted as tree).

edited Dec 23, 2017 at 22:36

dantiston

5,4312 gold badges28 silver badges30 bronze badges

answered Jul 1, 2016 at 10:01

Eugene Kirin

5783 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java 8 hashmap implementation using TreeNode instead of linkedlist

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related