How is the bucket structure organized within the HashMap implementation?

In HashMap implementation, a bucket structure is a container that stores elements with the same hash code (or hash codes that map to the same index after hash calculation and modulo operation).

Previously in Java, HashMap buckets were implemented as linked lists of elements, each containing a key, value, and a link to the next element. In case of collisions (multiple keys in the same bucket), new elements were added to this list.

Since Java 8, if the number of elements in a bucket exceeds a certain threshold (usually 8), the linked list is converted into a balanced tree (TreeNode, based on red-black tree). This improves search performance from O(n) to O(log n) in case of many collisions.

Thus, the bucket structure in HashMap is:

• An array of buckets, where each bucket is either
  • a linked list of entries, or
  • a balanced tree (TreeNode) if many elements

Example of a simplified structure:

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

In case of collision, elements with the same index are stored in a chain via the next field or in a tree.