Top 10 Must‑Know Java Collection Interview Questions (Part 2)

1. ArrayList vs LinkedList

Underlying structure: ArrayList uses a dynamic array, LinkedList a doubly‑linked list. Random access (get/set) is O(1) for ArrayList and O(n) for LinkedList. Insertion/deletion at the tail is O(1) for both; insertion/deletion in the middle is O(n) for ArrayList and O(1) (but requires traversal) for LinkedList. Memory: ArrayList stores elements in contiguous space with reserved capacity; LinkedList stores an extra forward and backward pointer per node. Suitable scenarios: ArrayList for many reads and few writes; LinkedList for many writes and few reads.

2. HashMap internal structure (JDK 7 vs JDK 8)

JDK 7: array + linked list, head‑insertion. JDK 8: array + linked list + red‑black tree (treeification when bucket length ≥ 8 and array length ≥ 64). Insertion changes from head‑insertion to tail‑insertion. Default capacity 16, load factor 0.75, threshold 12.

JDK 8 new features: bucket treeification, de‑treeification when tree size ≤ 6, improved hash function to reduce collisions.

Additional note: JDK 7 head‑insertion could cause an infinite loop during concurrent resize; JDK 8 fixes this with tail‑insertion.

3. HashMap put process

1. Compute key hash.
2. If table is null → initialize (resize).
3. Locate bucket index: (n‑1) & hash.
4. If bucket empty → insert directly.
5. If bucket not empty:
   ├─ key equal → overwrite value.
   ├─ bucket is a red‑black tree → tree insertion.
   └─ bucket is a linked list → traverse:
        ├─ key found → overwrite.
        └─ not found → tail‑insert.
6. After insertion, check if resize needed (size > threshold).

The expression (n‑1) & hash replaces hash % n for faster bucket calculation; the hash method also perturbs the original hashCode to lower collision probability.

4. HashMap resizing mechanism

// Trigger: size > threshold (capacity × load factor)
// Default: capacity 16, load factor 0.75, threshold 12
// JDK 8 resize steps:
1. newCapacity = oldCapacity * 2
2. create new array
3. recompute each element's position:
   - old bucket index: (n‑1) & hash
   - new bucket index: either same as old or old + oldCapacity
4. migrate elements using tail‑insertion (no infinite loop)

Resize is the most time‑consuming operation; estimating capacity beforehand reduces the number of resizes. During resize, an element stays in its original bucket or moves to bucket+oldCapacity because the array length is always a power of two.

5. ConcurrentHashMap implementation

JDK 7 (segment lock): a Segment[] array (default 16), each Segment is a ReentrantLock. put locks the corresponding Segment, allowing different Segments to be updated concurrently.

JDK 8 (CAS + synchronized): removes Segments, uses a Node[] array. The first node of each bucket acts as a lock (synchronized). CAS is used for lock‑free updates. Bucket structure (linked list + red‑black tree) is the same as HashMap. Multithreaded resize is supported. Lock granularity is finer (node‑level), giving higher concurrency; reads are completely lock‑free.

6. HashSet implementation

HashSet is a thin wrapper around HashMap; elements are stored as keys with a shared placeholder object PRESENT as the value.

public class HashSet<E> {
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();
    public boolean add(E e) { return map.put(e, PRESENT) == null; }
}

7. Why HashMap could dead‑loop in JDK 7

When two threads trigger resize simultaneously, thread A may be paused after creating new nodes, thread B completes resize and builds a new linked list, then thread A resumes and continues migration using head‑insertion, producing a circular list. Subsequent get operations loop forever.

JDK 8 switched to tail‑insertion, preserving element order and eliminating the circular‑list bug. Nevertheless, HashMap is not thread‑safe; production code should use ConcurrentHashMap.

8. LinkedHashMap LRU implementation

// Construct with accessOrder = true
LinkedHashMap<Integer,String> lru = new LinkedHashMap<>(16,0.75f,true);

@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > 100; // evict oldest when size exceeds 100
}

LinkedHashMap combines a hash table with a doubly linked list. When accessOrder=true, each access moves the entry to the tail; the head therefore holds the least‑recently used entry, enabling LRU eviction.

9. Fail‑fast vs fail‑safe iterators

Fail‑fast (e.g., ArrayList, HashMap) checks the internal modCount during iteration and throws ConcurrentModificationException as soon as a structural modification is detected. It helps discover concurrent‑modification bugs early but may abort the program.

Fail‑safe (e.g., CopyOnWriteArrayList, ConcurrentHashMap) iterates over a snapshot or copy; modifications do not throw, allowing the program to continue, but at the cost of higher memory usage because the entire collection is copied on each write.

10. Collection vs Collections

Collection

is the root interface of the collection framework (sub‑interfaces: List, Set, Queue). Collections is a utility class that provides static methods such as sort, reverse, synchronized wrappers ( synchronizedList), and unmodifiable views.

Summary

These ten topics constitute the most frequently asked Java collection interview questions, covering performance trade‑offs, internal data‑structure changes across JDK versions, core algorithms for put and resize, concurrency mechanisms in ConcurrentHashMap, the relationship between HashSet and HashMap, iterator safety models, and the distinction between the Collection interface and the Collections utility class—knowledge every Java developer should master for interviews.