До скольки элементов в Java HashMap используется LinkedList

Что проверяют

Знаете ли вы устройство HashMap после Java 8 точнее, чем «там список, потом дерево». Следом обычно спрашивают, зачем нужно второе условие про 64 и когда дерево превращается обратно в список.

Как отвечать

Сначала уточнение: java.util.LinkedList в HashMap не используется. Корзина хранит собственный односвязный список узлов Node с полем next или дерево из узлов TreeNode.

Дальше три константы из исходников:

• TREEIFY_THRESHOLD = 8: когда после вставки цепочка в корзине перерастает восемь узлов, вызывается treeifyBin();
• MIN_TREEIFY_CAPACITY = 64: treeifyBin() строит дерево, только если длина массива корзин не меньше 64. При меньшей ёмкости вместо дерева делается resize(), и длинная цепочка раскладывается по вдвое большему массиву;
• UNTREEIFY_THRESHOLD = 6: если при ресайзе после разделения корзины в ней осталось шесть узлов или меньше, дерево снова становится списком. При удалениях слишком маленькое дерево тоже распадается. Разрыв между 8 и 6 нужен, чтобы корзина не переключалась туда и обратно на каждой операции.

Дерево красно-чёрное, поиск в нём O(log n) вместо O(n). Порядок задаётся хэшем, при равных хэшах используется compareTo, если ключи реализуют Comparable и относятся к одному классу, иначе порядок разрешает служебный tieBreakOrder().

Почему именно 8: при нормальной хэш-функции длина цепочки подчиняется распределению Пуассона, и в комментарии к исходникам вероятность восьми элементов в одной корзине оценена примерно в 0.00000006. Дерево это защита от плохого hashCode() или атаки подбором коллизий, а не штатный режим. Узел дерева примерно вдвое тяжелее обычного.

Где спотыкаются

Говорят, что условие про 64 касается threshold. threshold это порог ресайза, ёмкость, умноженная на load factor, а проверяется именно длина массива корзин.

Считают, что дерево появляется всегда, как только в корзине стало много элементов. Без ёмкости от 64 карта сначала растёт, и дерево может не появиться вовсе.

Думают, что дерево спасает всегда. Если hashCode() у всех ключей одинаковый, а ключи не Comparable, дереву нечем их сравнить, и поиск снова деградирует до перебора.