Collections

The interfaces

• List: ordered, allows duplicates, index access.
• Set: no duplicates.
• Queue / Deque: FIFO, or both ends.
• Map: key → value (not a Collection).

Which implementation

Need	Use	Cost
Index access, mostly appends	ArrayList	get O(1), add amortised O(1), insert/remove in the middle O(n)
Stack or queue	ArrayDeque	push/pop/offer/poll O(1), faster than Stack and LinkedList
Fast lookup	HashSet / HashMap	O(1) average
Insertion order	LinkedHashMap / LinkedHashSet	O(1); accessOrder=true + removeEldestEntry = LRU cache
Sorted / range queries	TreeMap / TreeSet	O(log n); floorKey, ceilingKey, subMap
Smallest/largest first	PriorityQueue	offer/poll O(log n), peek O(1)

How HashMap works

• An array of buckets. Index = hash(key) & (n - 1), where hash mixes the high bits of hashCode() into the low ones.
• Collisions go into a linked list in the bucket; when one bucket holds 8+ entries (and the table has 64+ buckets) it becomes a red-black tree, so the worst case is O(log n), not O(n).
• Resizes (doubles) when size > capacity × load factor (default 16 × 0.75).
• Keys need consistent equals() and hashCode(); never mutate a key while it’s in the map.
• One null key is allowed. Not thread-safe → use ConcurrentHashMap.

Fail-fast iterators

Changing a collection structurally while iterating it (other than via iterator.remove()) throws ConcurrentModificationException. Concurrent collections (ConcurrentHashMap, CopyOnWriteArrayList) iterate over a weakly consistent view instead.

Interview angles

• HashMap vs ConcurrentHashMap vs Hashtable: unsynchronised; fine-grained (CAS + per-bin locks); one lock for everything (legacy).
• Comparable (natural order, inside the class) vs Comparator (external, many orders).
• Why is ArrayDeque preferred to Stack? Stack extends Vector, so every call is synchronised.