Выбор ответа Middle Коллекции изнутри спрашивают часто обновлено
Деревья в корзинах HashMap
Вопрос
Что происходит в Java 8+, когда в одной корзине HashMap накопилось много коллизий?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: При 8 узлах в цепочке и таблице от 64 цепочка станет деревом. Порог TREEIFYTHRESHOLD = 8: если таблица не меньше MINTREEIFYCAPACITY = 64, цепочка становится красно-чёрным деревом с поиском O(log n).
Варианты ответа
- Корзина делится на две половины по старшему биту хеша ключей
- При 8 узлах в цепочке и таблице от 64 цепочка станет деревомправильный ответ
- HashMap бросает исключение о плохом
hashCodeу класса ключа - Цепочка сортируется по
hashCode, и поиск в ней становится бинарным
Разбор
Порог TREEIFY_THRESHOLD = 8: если таблица не меньше MIN_TREEIFY_CAPACITY = 64, цепочка становится красно-чёрным деревом с поиском O(log n). Если таблица меньше 64, вместо дерева она расширяется. При уменьшении до 6 узлов дерево снова превращается в список. Деление по старшему биту происходит при resize всей таблицы, а не одной корзины. Исключений HashMap не бросает, массива с бинарным поиском нет.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.