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)?

Answer 1

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).