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 |
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 8+ ConcurrentHashMap uses CAS (Compare-And-Swap) operations instead of segment locking — much better performance under contention.
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?