How does HashMap work internally, does it use a singly linked list or BTS?

Question

Java

Not sure if I understand these two quotes correctly

When the threshold for converting this linked list to a self-balancing binary search tree is used - O(logn).

Before java 8, single-linked lists were used for storing the nodes. But this implementation has changed to self-balancing BST after a thresold is crossed

Therefore, I have to ask for help, how is it arranged inside the HashMap?

Answer 1

Buckets store nodes internally in the form of a singly linked list, but as soon as the number of nodes reaches 8 (constant TREEIFY_THRESHOLD = 8) and the number of buckets reaches 64 (constant MIN_TREEIFY_CAPACITY = 64), a transition will occur to the tree structure in this bucket. But the reverse transition from a tree structure to a singly linked list is also possible. This happens when the number of nodes in this bucket is reduced to 6 (the constant UNTREEIFY_THRESHOLD = 6), for example, when the capacity of the hash table (number of buckets) increases. At this point, all elements are rehashed. But there is another interesting point. Let's say you redefined the hashcode to return the same value. And as it is not difficult to guess, all elements will fall into one bucket. Initially 16 buckets, if you add 9 nodes and they all fall into one bucket,