What data structure underlies the implementation of HashMap and how does it work?

HashMap in Java is implemented based on an array of buckets (bucket array) and linked lists or balanced trees (TreeNodes) within each bucket.

Main components and working principle:

• Bucket array: Each element of the array is a bucket that stores elements with the same hash code modulo the size of the array.

• Hash function: For a key, a hash code is computed, which is then transformed into an array index (bucket) using a modulo operation.

• Collision resolution: If multiple keys fall into the same bucket (collision), they are stored in a linked list or, when the number of elements is large, in a balanced tree (starting from Java 8).

• Search: When searching for a key, the bucket index is calculated, and then the elements within the bucket are iterated to find a match using equals().

• Addition: A new element is added to the corresponding bucket. If the size of the bucket exceeds a threshold, the linked list is transformed into a tree to improve performance.

• Rehashing: When a certain load factor is reached, the array is enlarged, and all elements are redistributed across new buckets.

Example of a simplified structure:

class HashMap<K, V> {
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;
        // ...
    }

    Node<K, V>[] table;
    int size;
    // ...
}

Thus, HashMap provides quick access to elements with amortized time O(1) under good hash functions and low collision counts.