Ответы пользователя по тегу Java
  • Как внутри устроена HashMap, она использует singly linked list или BTS?

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