Java Collections Framework & HashMap Internals

🗄️ Java Collections Framework Architecture

The Java Collections Framework provides standardized interfaces and data structures for storing and manipulating groups of objects:

• Analogy: Smart Warehouse Sorting Bins & Automated Mail Cubbies.
  • ArrayList: An expandable row of contiguous lockers. Fast random access by locker index number ($O(1)$), but inserting an item into Locker #2 requires sliding all subsequent lockers to the right ($O(N)$).
  • LinkedList: A chain of treasure hunt clues. Locker A holds a key pointing to Locker B. Easy to insert items anywhere, but finding Locker #500 requires following 500 clue cards ($O(N)$).
  • HashMap: An automated mailroom cubby system. You run a key through a barcode scanner (hashCode()), which immediately points to Cubby #7 ($O(1)$ lookup)!

                             Java Collections Hierarchy
                                         │
        ┌────────────────────────────────┴────────────────────────────────┐
        ▼                                                                 ▼
    Collection                                                           Map
    ├── List (ArrayList, LinkedList)                                     ├── HashMap
    ├── Set (HashSet, TreeSet)                                           ├── ConcurrentHashMap
    └── Queue / Deque (ArrayDeque, PriorityQueue)                        └── TreeMap

⚡ ArrayList vs. LinkedList Internals

ArrayList Dynamic Resizing Formula

ArrayList is backed by an internal Object[] elementData array. When the array capacity is exceeded, it automatically resizes by allocating a new array using the 50% expansion formula:

int newCapacity = oldCapacity + (oldCapacity >> 1); // Grows by 1.5x (50%)

🗺️ HashMap Deep Dive Internals

HashMap stores key-value pairs using Separate Chaining Hash Buckets:

                       HashMap Bucket Array & Treeification
                                        │
    Hash Index = (n - 1) & hash(key)
    
    Bucket 0 ──► [Node A] ──► [Node B] (Singly Linked List)
    Bucket 1 ──► NULL
    Bucket 2 ──► [Red-Black Tree Root] (Treeified because count > 8!)

1. Hash Bucket Index Calculation

// Step 1: Compute Bit-Spread Hash
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// Step 2: Calculate Bucket Array Index via Bitwise AND
int index = (tableLength - 1) & hash(key);

2. Collision Resolution & Treeification (Java 8+)

• Initial Bucket Chaining: Colliding keys are stored in a Singly Linked List inside the bucket.
• Treeification Threshold: If a single bucket's collision chain exceeds 8 entries (and total table capacity $\ge 64$), the bucket's linked list is transformed (treeified) into a Red-Black Tree!
• Performance Impact: Worst-case search complexity drops from $O(N)$ down to $O(\log N)$, protecting applications against Hash Collision Denial-of-Service (DoS) attacks.
• Re-binning Threshold: If tree elements drop below 6 entries during deletion, the tree is untreeified back into a linked list.

🔒 ConcurrentHashMap Concurrency Mechanics

Unlike legacy Hashtable or Collections.synchronizedMap() (which acquire a global table lock), ConcurrentHashMap uses fine-grained locking:

1. CAS (Compare-And-Swap): Inserting into an empty hash bucket uses non-blocking atomic CPU CAS operations.
2. Synchronized Bucket Node Locks: When a collision occurs, it locks only the head node of that specific bucket, allowing concurrent threads to read and write to other buckets simultaneously without contention!

❓ Conceptual Quizzes

💻 Practice Problems