Collections Terminology — Interview Reference

Why this matters in interviews

Collections questions are the most frequent warm-up topic at every seniority level. Interviewers expect exact vocabulary: saying "HashMap uses buckets and a linked list for collisions, tree-binned at threshold 8" is far stronger than "it uses hashing." This lesson is a reference dictionary — read it before your interview.

Concept

Core Interfaces & Hierarchy

---

Internal Data Structures

---

Hashing Concepts

---

Ordering & Sorting

---

Iteration

---

Complexity & Sizing

---

Key Class Characteristics

† amortised

---

Utility & Factory

Key rules / gotchas

• Never put mutable objects as HashMap keys — if you mutate a key after insertion, its hashCode changes and you can no longer find the entry.
• TreeSet silently drops elements when compareTo returns 0 even if equals returns false — your Comparator must be consistent with equals.
• PriorityQueue is not sorted — iterator() traversal order is undefined. Only poll() gives elements in priority order.
• LinkedList is rarely the right choice — pointer overhead makes it slower than ArrayList in practice for most workloads despite O(1) head insert.
• List.of rejects null — use ArrayList or Arrays.asList if you need to store nulls.
• HashMap allows one null key; Hashtable and TreeMap do not — TreeMap would throw NullPointerException when calling compareTo(null).
• equals/hashCode must use the same fields — include a field in equals but not hashCode and collisions skyrocket; include in hashCode but not equals and lookups silently fail.

Code example

import java.util.*;

public class JavaLabRunner {
    record Point(int x, int y) {} // records auto-generate equals/hashCode/toString

    public static void main(String[] args) {
        // Fail-fast iterator — correct removal pattern
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            if (it.next() % 2 == 0) it.remove(); // safe; list.remove() would throw
        }
        System.out.println("After removal: " + list); // [1, 3, 5]

        // HashMap pre-sizing to avoid rehash
        int expected = 1000;
        Map<String, Integer> map = new HashMap<>((int)(expected / 0.75) + 1);
        map.put("key", 42);
        System.out.println("Pre-sized map, no resize needed for 1000 entries");

        // TreeMap: sorted, no null keys, natural order
        TreeMap<String, Integer> tree = new TreeMap<>();
        tree.put("banana", 2); tree.put("apple", 1); tree.put("cherry", 3);
        System.out.println("TreeMap (sorted): " + tree);
        System.out.println("Floor of 'avocado': " + tree.floorKey("avocado")); // null
        System.out.println("Ceiling of 'avocado': " + tree.ceilingKey("avocado")); // banana

        // equals/hashCode contract with records
        Set<Point> points = new HashSet<>();
        points.add(new Point(1, 2));
        points.add(new Point(1, 2)); // duplicate — records compare by value
        System.out.println("Set size (should be 1): " + points.size());

        // List.of — truly immutable
        List<String> immutable = List.of("a", "b", "c");
        try {
            immutable.add("d");
        } catch (UnsupportedOperationException e) {
            System.out.println("List.of is immutable: " + e.getClass().getSimpleName());
        }

        // PriorityQueue — only poll() gives priority order
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.addAll(List.of(5, 1, 3, 2, 4));
        System.out.print("PriorityQueue poll order: ");
        while (!pq.isEmpty()) System.out.print(pq.poll() + " "); // 1 2 3 4 5
        System.out.println();
    }
}

Interview questions you should be able to answer

• Q: Why does HashMap apply hash ^ (hash >>> 16) instead of using hashCode() directly?

  Bucket index is hash & (n-1), so only the lower bits matter. Objects whose hashCode differs only in high bits would all collide in the same bucket. XOR-ing with the upper half spreads those bits into the lower range, reducing collisions.

• Q: What is the difference between Collections.unmodifiableList and List.of?

  unmodifiableList is a view — the underlying list can still be mutated by whoever holds the original reference. List.of produces a truly immutable list with no backing mutable reference; it also rejects null elements and has a more compact internal representation.

• Q: When would you use LinkedHashMap over HashMap?

  When iteration order matters. LinkedHashMap preserves insertion order (or access order if constructed with accessOrder=true). The classic use case is an LRU cache — override removeEldestEntry to evict the least-recently-used entry when size exceeds the limit.

• Q: Why is TreeSet inconsistent with equals a problem?

  TreeSet uses compareTo (or Comparator) for all operations — it never calls equals. If compareTo returns 0 for two objects that equals says are different, the set treats them as duplicates and silently drops one, violating the Set contract.

• Q: What is the modCount mechanism and why does it exist?

  ArrayList (and most AbstractList subclasses) maintains a modCount counter incremented on every structural modification. The iterator captures modCount at creation; on each next() call it checks for a mismatch. If the list was modified outside the iterator, it throws ConcurrentModificationException immediately rather than returning corrupt data silently.

• Q: Why is LinkedList usually slower than ArrayList in practice despite having O(1) head/tail operations?

  Each LinkedList node allocates a separate heap object with two pointer fields, causing pointer-chasing on traversal and high GC pressure. ArrayList's contiguous backing array has excellent CPU cache locality. In benchmarks, ArrayList beats LinkedList even for prepend-heavy workloads until lists are very large, because cache misses dominate.

Further reading

• OpenJDK ArrayList source
• OpenJDK HashMap source
• Baeldung: Java Collections Interview Questions