Как внутри устроена HashMap, она использует singly linked list или BTS?

Question

[Biaci_Anj]

Не уверен, что правильно понимаю эти две цитаты

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

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

Поэтому вынужден попросить помощи, как же устроена внутри HashMap?

Answer 1

[temp_temp]

Бакеты хранят внутри себя ноды в форме односвязного списка, но как только количество нод достигает 8 (константа TREEIFY_THRESHOLD = 8) и количество бакетов достигает 64 (константа MIN_TREEIFY_CAPACITY = 64), произойдет переход к древовидной структуре в этом бакете. Но возможен и обратный переход из древовидной структуры в односвязный список. Это происходит, когда количество нод в этом бакете сокращается до 6 (константа UNTREEIFY_THRESHOLD = 6), например при увеличении ёмкости хэш-таблицы (количеста бакетов). В этот момент происходит перехеширование всех элементов. Но есть ещё один интересный момент. Допустим вы переопределили хэшкод, чтобы тот возвращал одно и то же значение. И как не трудно догадаться все элементы будут попадать в один бакет. Изначально 16 бакетов, если добавить 9 нод и все они попадут в один бакет, то мапа расширится до 32, если не произойдет распределение, то при добавлении 10 ноды - расширится до 64. И вот если снова не произошло распределения и 11 ноду добавить в тот же бакет, то этот бакет перестроится в дерево.