Какая структура данных в HashMap

HashMap в Java использует комбинацию массива и связанных списков (или деревьев в Java 8+). Основные элементы:

1. Массив бакетов - каждый элемент массива называется бакетом (bucket), хранит Entry (Node в Java 8+)
2. Entry/Node - содержит key, value, hash и ссылку на следующий Node (для разрешения коллизий)
3. При коллизиях - элементы с одинаковым хешем попадают в один бакет, образуя связанный список. В Java 8 при большом кол-ве элементов (>8) список преобразуется в красно-черное дерево.

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 1); // key хешируется, определяется бакет
map.get("key");    // по хешу key находится нужный бакет

При достижении load factor (по умолчанию 0.75) происходит rehashing - увеличение массива бакетов в 2 раза.