The big picture
| Interface | Order / rule | Main classes |
|---|---|---|
List | Ordered by index, duplicates allowed | ArrayList, LinkedList |
Set | No duplicates | HashSet, LinkedHashSet (insertion order), TreeSet (sorted) |
Queue / Deque | FIFO, or both ends | ArrayDeque, PriorityQueue, LinkedList |
Map | Key → value, unique keys (not a Collection) | HashMap, LinkedHashMap, TreeMap |
| Class | get / contains | add / put | Backed by |
|---|---|---|---|
ArrayList | O(1) by index, O(n) search | O(1) amortized at the end | Dynamic array |
LinkedList | O(n) | O(1) at the ends | Doubly linked list |
HashMap / HashSet | O(1) average | O(1) average | Hash table with buckets |
TreeMap / TreeSet | O(log n) | O(log n) | Red-black tree |
PriorityQueue | O(1) peek | O(log n) offer/poll | Binary heap |
How HashMap works
- The map keeps an array of buckets (16 by default).
put(k, v): computek.hashCode(), spread its bits (h ^ (h >>> 16)), and pick buckethash & (n - 1).- If the bucket is empty, store a node. Otherwise walk the bucket: if a key
equals()k, replace its value; else append a new node (a collision). - When a bucket's chain reaches 8 entries (and the table has at least 64 buckets) it turns into a red-black tree, so a bad hash costs O(log n) instead of O(n).
- When size exceeds capacity × load factor (0.75), the table doubles and entries are redistributed.
Map<String, Integer> ages = new HashMap<>();ages.put("ada", 36);ages.put("alan", 41);ages.getOrDefault("grace", 0); // 0ages.merge("ada", 1, Integer::sum); // 37: add to the existing valueages.computeIfAbsent("bob", k -> 0);
Mutating a key after putting it in a HashMap changes its hash code, so the map can no longer find it. Use immutable keys like String, Integer or records.
ArrayList vs LinkedList
ArrayList stores elements in one contiguous array: indexing is O(1) and iteration is cache-friendly; inserting in the middle shifts elements (O(n)), and growing copies the array (about 1.5× each time). LinkedList stores nodes with prev/next pointers: adding at the ends is O(1), but get(i) walks the list, and every node costs extra memory.
In practice ArrayList (or ArrayDeque for queues) wins almost always. LinkedList only helps when you insert or remove through an iterator in the middle of a long list.
Comparable vs Comparator
Comparable gives a class its natural order through compareTo (one ordering, inside the class). A Comparator is a separate object describing any order, so one class can be sorted many ways.
record Student(String name, int grade) implements Comparable<Student> {public int compareTo(Student o) { return name.compareTo(o.name); }}List<Student> list = new ArrayList<>(students);Collections.sort(list); // by name (natural order)list.sort(Comparator.comparingInt(Student::grade).reversed().thenComparing(Student::name)); // grade desc, then name
Fail-fast iterators and concurrent collections
Most collections count modifications. If the collection changes structurally while you iterate (other than through the iterator itself), the next next() throws ConcurrentModificationException.
List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4));for (Integer n : nums) if (n % 2 == 0) nums.remove(n); // ConcurrentModificationExceptionnums.removeIf(n -> n % 2 == 0); // safeIterator<Integer> it = nums.iterator();while (it.hasNext()) if (it.next() > 2) it.remove(); // also safe
ConcurrentHashMap: thread-safe map with fine-grained locking (CAS and per-bin locks), no lock on reads. Doesn't allow null keys or values.Collections.synchronizedMap: wraps every method in one lock. Simpler but slower under contention.CopyOnWriteArrayList: copies on every write; great for lists read far more than written (listeners).
See it animated
Interview questions
Try answering out loud first, then open the model answer.
Q1Explain the internal working of HashMap.intermediate
An array of buckets. put hashes the key, spreads the bits, and indexes hash & (n - 1). Collisions are chained in a linked list in that bucket; from Java 8 a long chain (8+, with capacity ≥ 64) becomes a red-black tree. get finds the bucket the same way, then compares with equals(). When size > capacity × 0.75 the array doubles and entries are rehashed.
Q2What happens when two keys have the same hashCode?intermediate
They land in the same bucket (a collision). The map compares keys with equals(): if equal, the value is replaced; otherwise both entries live in the bucket's list or tree. Lookups stay correct but get slower as buckets grow.
Q3HashMap vs Hashtable vs ConcurrentHashMap?intermediate
HashMap: not thread-safe, allows one null key and null values, fastest single-threaded.Hashtable: legacy, every method synchronized, no nulls.ConcurrentHashMap: thread-safe with fine-grained locking and lock-free reads, no nulls. The right choice for concurrent code.
Q4HashMap vs TreeMap vs LinkedHashMap?beginner
HashMap: no order, O(1) average. LinkedHashMap: remembers insertion (or access) order, still O(1), and can act as an LRU cache with removeEldestEntry. TreeMap: keys sorted, O(log n), with navigation like floorKey and headMap.
Q5Why does HashMap capacity stay a power of two?advanced
So the bucket index can be hash & (n - 1) instead of a slower %, and so that on doubling each entry either stays at index i or moves to i + oldCapacity, decided by one extra bit.
Q6What is ConcurrentModificationException and how do you avoid it?intermediate
Fail-fast iterators throw it when the collection is structurally modified during iteration by anything other than the iterator. Avoid it with Iterator.remove(), removeIf, collecting changes and applying them after the loop, or concurrent collections whose iterators are weakly consistent.
Q7Comparable vs Comparator?beginner
Comparable is implemented by the class itself (compareTo) and defines its single natural order. Comparator is a separate strategy object (compare), so you can define many orders without touching the class, and compose them with thenComparing, reversed.
Q8How does HashSet ensure uniqueness?beginner
A HashSet is backed by a HashMap: each element is stored as a key with a dummy value. Uniqueness therefore relies on the element's hashCode() and equals().
Q9How would you implement an LRU cache in Java?advanced
class Lru<K, V> extends LinkedHashMap<K, V> {private final int cap;Lru(int cap) { super(16, 0.75f, true); this.cap = cap; } // true = access order@Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > cap; }}
Without LinkedHashMap: a HashMap from key to node plus a doubly linked list ordered by recency, both O(1).
Quick check
0 of 4 answered