Method putTreeVal() in HashMap JDK8

Question

When is it usually method putTreeVal() used in HashMap?

When does this case, after invoking put(K key, V value):

else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

usually take place?

Answer 1

The usual way a hash map works is to have a number of bins (or buckets), where you select the bin for the new key based on its hash code.

The problem is that several keys may get to the same bin, as there is a limited number of bins. The bin is a list. So you can get to the bin in O(1) time, but then you have to search linearly in the list. If that list becomes long, it deteriorates the performance of the hash table.

So the current implementation of HashMap ameliorates this problem by changing the bin structure if the bin gets too long. If the bin has more than 8 entries already, and the number of bins is more than 64, the bin is converted from a list to a red-black tree. A red-black tree is a balanced search tree. This means searching it is going to be O(log n), which is preferable to O(n).

So now, when you put a value in a bin, you have to check which bin it is. If it's a plain list, add to the list, and if it's a tree, add to the tree and balance it.