☕ Java Collections — Deep Dive Interview Prep

Focus: Internal workings, edge cases, comparisons, and follow-up traps. Answers are written for a 3+ year experienced Java developer.

1. ArrayList & HashMap Internals

🔷 ArrayList — Internal Working

Backing Structure: Object[] elementData

Default capacity: 10

Growth formula (Java 8+):

newCapacity = oldCapacity + (oldCapacity >> 1)   // i.e., 1.5x

Step-by-step on add():

1. Check if size == elementData.length
2. If yes → grow() is called → Arrays.copyOf(elementData, newCapacity) creates a new array
3. Element is placed at elementData[size] and size++

List<Integer> list = new ArrayList<>(); // capacity = 10
// Add 11 elements → capacity becomes 15 (10 + 10>>1)
// Add 16th → capacity becomes 22 (15 + 15>>1)

Key Points:

• trimToSize() shrinks backing array to actual size
• ensureCapacity(n) pre-allocates if you know the size upfront (avoids multiple copies)
• remove(int index) → System.arraycopy() shifts elements left — O(n)
• Random access get(i) → O(1)

🎯 Follow-up: What is the difference between size and capacity? Answer: size = number of actual elements; capacity = length of backing array. You can have capacity 15 with size 3.

🔷 HashMap — Internal Working (Java 8+)

Backing Structure: Node<K,V>[] table (array of buckets)

Default initial capacity: 16

Load factor: 0.75

Threshold = capacity × load factor → resize when exceeded