Как устроена HashMap внутри?

HashMap — массив бакетов (Node[] table), каждый бакет — односвязный список или красно-чёрное дерево (с Java 8). put: index = (n-1) & hash(key). При коллизии — обход списка; если ключ равен (== или equals) — заменить value, иначе добавить в конец.

// Схема бакета
// table[hash & (n-1)] -> Node(k1,v1) -> Node(k2,v2) -> ...  (или TreeBin)

// Treeify: длина цепочки >= 8 и capacity >= 64 → красно-чёрное дерево
// Цель: защита от collision-атак, O(1) → O(log n)
Map<String, Integer> m = new HashMap<>(16);   // capacity, loadFactor=0.75

• resize при size > capacity * loadFactor (0.75) — массив удваивается, rehash;
• Null-ключ разрешён (1, hash 0), null-значения разрешены;
• Не synchronized — для многопоточности ConcurrentHashMap;
• Treeify threshold = 8, untreeify = 6;
• Правильный hashCode/equals критичен для корректной работы.