HashMap

A HashMap is a hash table based implementation of the Map interface. It stores data using a bucket array, handling hash collisions through linked lists that treeify into Red-Black trees when thresholds are met.

Internal Bucketing & Java 8 Treeification

HashMap resolves collisions dynamically using a two-stage structure:

• Linked List Stage: Initially, colliding keys are appended to a singly-linked list in the bucket. Lookup takes O(K) time, where K is the list size.
• Red-Black Tree Stage: If collision chains grow to 8 elements, lookup performance is improved from O(K) linear time to O(log K) logarithmic time by converting the list to a Red-Black tree.
• Untreeification: During resizing or deletion, if a bucket's elements drop to 6 or fewer, the tree is converted back to a linked list to reduce tree balance overhead.

Common Pitfalls

• Concurrently Mutating HashMap: Modifying a HashMap from multiple threads during resizing, which can cause data loss, infinite loops, or garbage collector loops.
• Poor Hash Distribution: Storing keys with identical or poorly written hashcode methods, which groups all elements into a single bucket and degrades performance to O(N) or O(log N).

Best Practices

• Estimate initial capacity: Calculate the required capacity as expectedSize / loadFactor + 1 to prevent performance-intensive rehash cycles.
• Use immutable keys: Always use immutable objects (like String or Integer) as keys to prevent hashcode modifications.

Interview-Relevant Information