I came across a blog where changes and performance improvements of hashmap were given in JDK8.
From JDK 1.8 onwards HashMap has introduced an improved strategy to deal with high collision rate. Since a poor hash function e.g. which always return location of same bucket, can turn a HashMap into linked list, i.e. converting get() method to perform in O(n) instead of O(1) and someone can take advantage of this fact, Java now internally replace linked list to a binary true once certain threshold is breached. This ensures performance or order O(log(n)) even in the worst case where a hash function is not distributing keys properly.
In JDK 8, we all know that whenever a threshold value is reached, the linked list re-sizes itself to a binary tree. I wanted to know whether the binary tree will re-size itself into a linked list, again when nodes become less than the threshold number.?
It was asked to me in an interview to which I said, no, as it will not keep re-sizing itself every time there is a change in number. Am I right?
Blogs for reference:
Aucun commentaire:
Enregistrer un commentaire