Как хранятся элементы внутри бакета Map в Java: сортированы или в связном списке

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

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

Как отвечать

Короткий ответ: в обычной корзине элементы лежат в односвязном списке без сортировки, а при сильной коллизии корзина становится красно-чёрным деревом.

• индекс корзины: hashCode() ключа перемешивается как h ^ (h >>> 16), затем берётся (n-1) & hash. Размер таблицы всегда степень двойки, по умолчанию 16, loadFactor 0.75;
• список: узлы Node с полем next. С Java 8 новый элемент добавляется в хвост, в Java 7 вставка шла в голову. Внутри корзины это порядок вставки, но гарантий на порядок обхода всей мапы нет;
• дерево: когда в корзине становится больше восьми элементов (TREEIFY_THRESHOLD = 8), список превращается в дерево из TreeNode. Но только если в таблице уже не меньше 64 корзин (MIN_TREEIFY_CAPACITY), иначе HashMap просто удваивает таблицу;
• обратно в список: при resize дерево, в котором осталось 6 узлов и меньше (UNTREEIFY_THRESHOLD), снова становится списком;
• порядок в дереве: по хешу, при равных хешах по compareTo, если ключи Comparable одного класса, а иначе по System.identityHashCode. То есть дерево сортирует не ключи, а хеши.

При resize хеши не пересчитываются: каждая корзина делится на две, «младшую» и «старшую», по одному биту хеша. В нормальных условиях дерево почти не встречается: в комментариях к исходнику HashMap вероятность восьми элементов в корзине при хорошем hashCode() оценена в шесть стомиллионных.

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

Говорят, что элементы в корзине отсортированы по ключу. Это путаница с TreeMap, где красно-чёрным деревом является вся структура.

Забывают про порог 64 и отвечают, что на девятом элементе дерево появляется всегда.

Не могут объяснить, зачем дерево вообще нужно: оно защищает от плохого hashCode() и от атак подбором коллизий, превращая поиск в корзине из O(n) в O(log n).