Zum Hauptinhalt springen

Week 6 Review — Collections

Goal​

This review checks whether I can pick a collection by contract and draw a HashMap bucket without hand-waving.

Week 6 topics:

  1. Collection vs Collections vs Map
  2. List / ArrayList / LinkedList
  3. Set and Map implementations
  4. HashMap hash, bins, resize, mutable keys
  5. Fail-fast iterators
  6. Comparable vs Comparator, TreeSet uniqueness

1. Week 6 big picture​


Need order + duplicates?     List  → ArrayList (default)
Need unique?                 Set   → HashSet
  + insertion order          LinkedHashSet
  + sorted                   TreeSet  (compareTo, not equals)
Need lookup by key?          Map   → HashMap
  + iteration order          LinkedHashMap
  + sorted keys              TreeMap
  + many threads             ConcurrentHashMap (Week 8)

put(k,v): hash → bucket → equals
mutate k after put: lookup misses
for-each + list.remove: ConcurrentModificationException

2. Core memory sentences​

Collection is the interface. Collections is the helper. Map is not a Collection.

Default to ArrayList; linked lists rarely win in real JVMs.

Set is uniqueness. Map is lookup.

HashSet is a HashMap with a dummy value.

Hash picks the bucket; equals confirms the key; collisions list, then tree.

A mutated key stays in the old bucket.

Fail-fast means modCount changed; CME is a detector, not a lock.

Remove with iterator.remove or removeIf.

Comparable is natural order. Comparator is an external strategy.

HashSet uses equals. TreeSet uses compareTo.

3. Speak these without notes​

  1. Draw HashMap.put from hashCode to equals.
  2. Why a mutable key disappears.
  3. Why for-each + remove throws, and the legal alternative.
  4. HashSet vs TreeSet uniqueness.
  5. ArrayList vs LinkedList without saying “LinkedList is faster for inserts.”

4. Tiny code proofs​

Proof A — mutated key​

Put a mutable object in a HashMap, change a field used by hashCode, get with the same reference. Confirm a miss. Then iterate entrySet and see the entry still there.

Proof B — CME​

For-each an ArrayList and remove inside the loop. Catch ConcurrentModificationException. Repeat with removeIf.

Proof C — TreeSet vs equals​

Two objects with equals false and compareTo 0. Add both to HashSet and to TreeSet. Compare sizes.

5. Common mix-ups from this week​

Mix-upClear line
Map is-a CollectionSeparate interface; use views
LinkedList for insertsOnly if I already have the node
HashMap always O(1)Expected, given a good hash
TreeSet is a sorted HashSetComparison defines uniqueness
CME means two threadsOne thread + for-each remove is enough
Hashtable for concurrencyConcurrentHashMap

6. Interview drill​

Open Collections and streams:

  • ArrayList vs LinkedList vs array
  • How HashMap works internally
  • HashSet vs LinkedHashSet vs TreeSet
  • Fail-fast vs fail-safe
  • Why changing a key after insert breaks a HashMap
  • equals/hashCode for a HashSet of entities

And Java fundamentals: Comparable vs Comparator; equals/hashCode.

7. Ready for Week 7?​

I am ready if I can draw the bucket picture and remove from a list without CME.

Week 7 is streams: laziness, map/flatMap, and when a loop is clearer.

Next: Week 7 Day 1 — Functional Interfaces and Lambdas