How does HashMap work: buckets, hash function, collisions, LinkedList, and red-black tree inside?

HashMap in Java is implemented as an array of buckets, each of which stores elements with the same hash code at an index computed by a hash function.

• Hash function converts a key into an integer value (hash code), which is then used to determine the bucket index.
• If multiple keys fall into the same bucket (collision), the elements in the bucket are stored as a linked list (LinkedList).
• When the number of elements in a bucket grows and exceeds a threshold, the LinkedList is converted into a red-black tree (TreeNode), which improves search performance from O(n) to O(log n).

Example of a simplified structure:

class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // for linked list
}

// On collision, elements are added to a linked list or tree within the bucket