Java 8 hash map implementation using TreeNode instead of linked list

Question

According to this post:

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

java 8 hashmaps use treenode instead of a linked list (as in java 7) as elements of an array.

TreeNodes have the special property of acting as a linked list if the number of elements is small and acts like a red ebony if there are a large number of elements. (Since operations with red ebony are log (n)).

However, this does not require the key to be comparable, or does any order of keys exist?

Is this mandatory in a java 8 hash map? Does it use only red black trees if the keys are comparable (there is an order of keys)?

Answer 1

Will only red black trees be used if the keys are comparable (key ordering exists)?

No, when the HashMap small, all conflicts are resolved as a 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 converts all conflicts into a treemap when the threshold is reached.

However, this does not require the key to be comparable or does any order of keys exist?

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