GamifiedGamified challengesPracticeRaceLeaderboardPricing

Learn data structures by watching them move, then doing it yourself. Press M anytime to toggle sound.

A product of Amypo Technologies, Coimbatore.

Learn

  • All topics
  • Learning path
  • How it works
  • About dotprep

Practice

  • Practice arena
  • Daily challenge
  • Gamified challenges
  • Race mode
  • Leaderboard

Interview prep

  • Java interview
  • Coding questions
  • Company questions
  • System design
  • Jobs & careers

You

  • Dashboard
  • Settings
  • Pricing
  • Create account

© 2026 dotprep

Content last updated 20 November 2026

GamifiedGamified challengesPracticeRaceLeaderboardPricing
Java interviewCollections framework

Collections framework

List, Set, Map and Queue: which to pick, how HashMap works inside, and the questions every Java interview asks.

intermediate 22 min read 9 interview questions

On this page

1/7
  1. 01The big picture
  2. 02How HashMap works
  3. 03ArrayList vs LinkedList
  4. 04Comparable vs Comparator
  5. 05Fail-fast iterators and concurrent collections
  6. 06Interview questions
  7. 07Quick check
Back to top

The big picture

InterfaceOrder / ruleMain classes
ListOrdered by index, duplicates allowedArrayList, LinkedList
SetNo duplicatesHashSet, LinkedHashSet (insertion order), TreeSet (sorted)
Queue / DequeFIFO, or both endsArrayDeque, PriorityQueue, LinkedList
MapKey → value, unique keys (not a Collection)HashMap, LinkedHashMap, TreeMap
Classget / containsadd / putBacked by
ArrayListO(1) by index, O(n) searchO(1) amortized at the endDynamic array
LinkedListO(n)O(1) at the endsDoubly linked list
HashMap / HashSetO(1) averageO(1) averageHash table with buckets
TreeMap / TreeSetO(log n)O(log n)Red-black tree
PriorityQueueO(1) peekO(log n) offer/pollBinary heap

How HashMap works

  • The map keeps an array of buckets (16 by default).
  • put(k, v): compute k.hashCode(), spread its bits (h ^ (h >>> 16)), and pick bucket hash & (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.
java
Map<String, Integer> ages = new HashMap<>();
ages.put("ada", 36);
ages.put("alan", 41);
ages.getOrDefault("grace", 0); // 0
ages.merge("ada", 1, Integer::sum); // 37: add to the existing value
ages.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.

java
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.

java
List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer n : nums) if (n % 2 == 0) nums.remove(n); // ConcurrentModificationException
nums.removeIf(n -> n % 2 == 0); // safe
Iterator<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

Dynamic arrayDoubly linked listSeparate chainingLoad factor and rehashingRed-black treeBinary heapLRU cache

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
java
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

Question 1

1.Which keeps keys sorted?

Question 2

2.HashMap's default load factor is…

Question 3

3.Removing items inside a for-each over an ArrayList usually throws…

Question 4

4.get(i) on a LinkedList is…

0 of 4 answered

Exception handlingGenerics
Log inStart free