Какова роль массива или массива внутри структуры HashMap?

В реализации HashMap в Java массив служит базовой структурой для хранения ссылок на «бакеты» (корзины), в которых хранятся элементы с одинаковым хеш-кодом (коллизии). Каждый элемент массива — это либо null, либо ссылка на связанный список или дерево (в новых версиях Java) элементов, которые имеют одинаковый индекс, вычисленный из хеш-кода ключа.

Таким образом, массив обеспечивает быстрый доступ к бакету по индексу, а внутри бакета уже происходит поиск нужного элемента по ключу. Это позволяет эффективно реализовать операции вставки, поиска и удаления с амортизированной сложностью близкой к O(1).

Пример упрощённой структуры:

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // конструктор и методы
}

Node<K,V>[] table; // массив бакетов

Каждый индекс массива соответствует определённому диапазону хешей, а внутри бакета элементы связаны списком или деревом.