Collections Framework

Java Collections Framework provides data structure implementations under java.util. Key interfaces: List (ArrayList, LinkedList), Set (HashSet, TreeSet), Map (HashMap, TreeMap, LinkedHashMap), Queue (PriorityQueue, ArrayDeque). Choose based on ordering, uniqueness, thread-safety, and performance needs.

Collection (interface)
├── List (ordered, allows duplicates)
│   ├── ArrayList (dynamic array, O(1) access, O(n) insert/delete)
│   ├── LinkedList (doubly-linked, O(n) access, O(1) insert/delete at ends)
│   └── Vector (synchronized ArrayList, legacy)
├── Set (no duplicates)
│   ├── HashSet (O(1) add/contains, no ordering)
│   ├── LinkedHashSet (HashSet + insertion order)
│   └── TreeSet (O(log n) add/contains, sorted)
└── Queue (FIFO or priority)
    ├── PriorityQueue (min-heap by default)
    ├── ArrayDeque (double-ended queue)
    └── LinkedList (also implements Queue)

Map (interface, not a Collection)
├── HashMap (O(1) get/put, no ordering)
├── LinkedHashMap (HashMap + insertion/access order)
├── TreeMap (O(log n) get/put, sorted by keys)
└── Hashtable (synchronized HashMap, legacy)

---

ArrayList vs LinkedList

ArrayList — backed by a dynamic array. O(1) random access, O(1) amortized add to end, O(n) insert/remove in middle. Default choice for most use cases. LinkedList — doubly-linked list. O(1) add/remove at ends, O(n) random access. Use only when you need frequent insertions/removals at both ends (deque).

Deep Dive: Comparison Table

Operation	ArrayList	LinkedList
get(index)	O(1)	O(n)
add(element)	O(1) amortized	O(1)
add(index, element)	O(n)	O(n) search + O(1) insert
remove(index)	O(n)	O(n) search + O(1) remove
Memory	Compact (contiguous)	Extra for node pointers

ArrayList resizing: When capacity is exceeded, creates a new array (1.5x size) and copies elements — O(n). Pre-size with new ArrayList<>(expectedSize) to avoid resizes.

---

HashSet vs TreeSet vs LinkedHashSet

HashSet — O(1) add/contains, no ordering (backed by HashMap). TreeSet — O(log n) operations, elements always sorted (backed by Red-Black Tree). LinkedHashSet — O(1) operations, maintains insertion order. Choose based on whether you need ordering, sorting, or just fast lookup.

Deep Dive: Comparison & Example

Feature	HashSet	TreeSet	LinkedHashSet
Ordering	None	Sorted	Insertion order
add/contains	O(1)	O(log n)	O(1)
Implementation	HashMap	Red-Black Tree	HashMap + LinkedList
Null elements	1 allowed	Not allowed	1 allowed

Set<Integer> hashSet = new HashSet<>(Arrays.asList(3, 1, 2));
// [1, 2, 3] or [2, 3, 1] — no guarantee

Set<Integer> treeSet = new TreeSet<>(Arrays.asList(3, 1, 2));
// [1, 2, 3] — always sorted

Set<Integer> linkedSet = new LinkedHashSet<>(Arrays.asList(3, 1, 2));
// [3, 1, 2] — insertion order preserved

---

HashMap vs TreeMap vs LinkedHashMap

HashMap — O(1) get/put, no ordering (most common). TreeMap — O(log n), keys always sorted (Red-Black Tree). LinkedHashMap — O(1), maintains insertion order (or access order for LRU cache). HashMap allows one null key; TreeMap doesn't.

Deep Dive: LinkedHashMap as LRU Cache

// LRU cache using access-order LinkedHashMap
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 3;  // Keep only 3 most recently accessed
    }
};

Feature	HashMap	TreeMap	LinkedHashMap
Key ordering	None	Sorted	Insertion/Access order
get/put	O(1)	O(log n)	O(1)
Null keys	1 allowed	Not allowed	1 allowed

---

HashMap Internals

HashMap uses an array of Node buckets. put(key, value): compute hash(key) % capacity → bucket index. If collision, store as linked list in that bucket (Java 7) or red-black tree when list ≥ 8 nodes (Java 8+ — treeification). get(key): same hash → find bucket → traverse list/tree using equals(). Default capacity 16, load factor 0.75 → resize (rehash) at 12 entries.

Deep Dive: How HashMap Works

put("A", 1):  hash("A") = 65 → bucket[65 % 16] = bucket[1]
put("B", 2):  hash("B") = 66 → bucket[66 % 16] = bucket[2]
put("Q", 3):  hash("Q") = 81 → bucket[81 % 16] = bucket[1]  ← collision with "A"!

Bucket Array:
[0] → null
[1] → Node("A",1) → Node("Q",3)    ← linked list (collision chain)
[2] → Node("B",2)
...
[15] → null

Key internals:

Concept	Detail
Index formula	(n - 1) & hash (bitwise AND, where n = capacity)
Hash spreading	hash = key.hashCode() ^ (key.hashCode() >>> 16) — XOR high bits into low to reduce collisions
Default capacity	16 (always a power of 2)
Load factor	0.75 — resize when size > capacity × loadFactor
Resize	Double capacity, rehash all entries (O(n))
Treeification	Linked list → Red-Black Tree when ≥ 8 nodes in one bucket
Untreeify	Tree → List when ≤ 6 nodes (after removal)

// What happens with bad hashCode?
class BadKey {
    @Override public int hashCode() { return 42; }  // All go to same bucket!
}
// All entries in one bucket → O(n) for linked list, O(log n) after treeification

hashCode/equals contract:

• If a.equals(b) → a.hashCode() == b.hashCode() (MUST)
• If hashCode differs → NOT equals (fast rejection)
• Override both or neither — breaking this causes lost entries!

Deep Dive: HashMap vs Hashtable

Feature	HashMap	Hashtable
Thread-safe	❌ No	✅ Yes (synchronized)
Null key	1 allowed	❌ Not allowed
Null values	Allowed	❌ Not allowed
Performance	Faster	Slower (lock on every op)
Iteration	fail-fast	fail-safe (enumerator)
Since	Java 1.2	Java 1.0 (legacy)
Replacement	Use ConcurrentHashMap for thread safety	← Same

Never use Hashtable — use ConcurrentHashMap for thread-safety or HashMap for single-threaded.

---

Iterators: fail-fast vs fail-safe

Fail-fast iterators throw ConcurrentModificationException if the collection is modified during iteration (except via the iterator's own remove()). Used by: ArrayList, HashMap. Fail-safe iterators work on a copy — no exception, but changes aren't reflected. Used by: CopyOnWriteArrayList, ConcurrentHashMap.

Deep Dive: Examples

// fail-fast — throws ConcurrentModificationException
List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
for (String s : list) {
    list.remove(s);  // ConcurrentModificationException!
}

// Correct way — use iterator's remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    it.remove();  // OK
}

// fail-safe — no exception
List<String> safeList = new CopyOnWriteArrayList<>(Arrays.asList("a", "b", "c"));
for (String s : safeList) {
    safeList.remove(s);  // No exception, iterates over snapshot
}

---

Comparable vs Comparator

Comparable — defines natural ordering in the class itself (compareTo()). Comparator — defines custom ordering externally. Use Comparable for one default sort order, Comparator for multiple or ad-hoc orderings. A class can implement Comparable once but have many Comparators.

Deep Dive: Examples

// Comparable — natural ordering, single sort
public class Person implements Comparable<Person> {
    private String name;
    private int age;

    @Override public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);
    }
}
Collections.sort(people);  // Uses Comparable

// Comparator — custom ordering, flexible
Comparator<Person> byName = Comparator.comparing(p -> p.name);
Comparator<Person> byAge = Comparator.comparingInt(p -> p.age);

Collections.sort(people, byName);
Collections.sort(people, byAge.reversed());

---

Thread-Safe Collections

Legacy approach: Collections.synchronizedList() wraps with coarse-grained locking (poor performance). Modern approach: java.util.concurrent classes — ConcurrentHashMap (segment/CAS-based locking, high concurrency), CopyOnWriteArrayList (copies on write, good for read-heavy), ConcurrentSkipListMap (concurrent sorted map).

Deep Dive: ConcurrentHashMap Internals

// Modern — fine-grained, high concurrency
Map<String, Integer> map = new ConcurrentHashMap<>();
map.put("a", 1);  // Thread-safe, no external synchronization needed

// Atomic compute operations
map.computeIfAbsent("key", k -> expensiveComputation());
map.merge("key", 1, Integer::sum);  // Atomic merge

Java 7 — Segment-based locking:

ConcurrentHashMap
├── Segment[0] (lock) → [bucket0, bucket1, ...]
├── Segment[1] (lock) → [bucket4, bucket5, ...]
└── Segment[15] (lock) → [...]

Default 16 segments → 16 threads can write concurrently (each locks one segment).

Java 8+ — Node-level locking (much better):

ConcurrentHashMap (single Node[] array)
├── bucket[0] → CAS for insert / synchronized(head) for update
├── bucket[1] → CAS for insert / synchronized(head) for update
└── bucket[n] → ...

• Empty bucket: use CAS to insert first node (lock-free)
• Non-empty bucket: synchronized on the head node of that bucket only
• Reads: completely lock-free (volatile reads)
• Treeification: same as HashMap (list → tree at ≥ 8 nodes)

Feature	Hashtable	synchronizedMap	ConcurrentHashMap
Lock granularity	Whole table	Whole map	Per-bucket (Java 8+)
Read locking	Yes	Yes	❌ No (lock-free)
Null key/value	❌	✅	❌
Performance	Poor	Poor	Excellent
Atomic ops	❌	❌	computeIfAbsent, merge

---

Common Interview Questions

Common Interview Questions

• What is the difference between ArrayList and LinkedList?
• When would you use a LinkedList over an ArrayList?
• What is the difference between HashSet and TreeSet?
• How does HashMap work internally? (See hash-maps.md for details)
• What is the difference between HashMap and Hashtable?
• What is the difference between fail-fast and fail-safe iterators?
• What is the difference between Comparable and Comparator?
• How do you make a collection thread-safe?
• What is ConcurrentHashMap? How is it different from Hashtable?
• Can you store null in HashMap? TreeMap? HashSet? TreeSet?