In Java 8, the HashMap implementation was enhanced to use balanced trees (specifically, red-black trees) instead of linked lists in certain situations to improve performance. Here's a detailed explanation of how and why this change was made: Background In a typical HashMap , each bucket (or bin) in the underlying array is a linked list that holds all the entries with the same hash code. This means that if many keys hash to the same bucket (i.e., there are hash collisions), the time complexity for operations like get , put , and remove degrades from O(1) to O(n) in the worst case, where n is the number of elements in the bucket. Changes in Java 8 To address this performance degradation, Java 8 introduced the use of balanced trees (red-black trees) for bins with a high number of collisions. The basic idea is to use a linked list for buckets with a small number of entries and switch to a red-black tree once the number of entries in a bucket exceeds a certain threshold (specificall...