Java Interview: Collections, equals/hashCode & API Traps

"Explain HashMap internals" is asked in a majority of Java interviews. Here is the answer, at the depth expected.

Structure. A HashMap holds an array of buckets. On put(key, value):

1. Compute key.hashCode().
2. Apply an internal spread function (h ^ (h >>> 16)) so that high bits influence the low-bit index. This reduces collisions from poorly distributed hash codes.
3. Index the bucket: hash & (capacity - 1) — which is why capacity is always a power of two.
4. Walk the bucket comparing with equals(). Replace on match, otherwise append.

Collisions. Entries in the same bucket form a linked list. Since Java 8, once a bucket exceeds 8 entries (and capacity is at least 64) it converts to a red-black tree, taking worst-case lookup from O(n) to O(log n).

Resizing. Default capacity 16, load factor 0.75. When size > capacity * loadFactor, capacity doubles and entries are rehashed. If you know the final size, pre-size it: new HashMap<>(expectedSize / 0.75f + 1).

Complexity. O(1) average; O(log n) worst case with treeified bins.

Follow-ups you should be ready for:

• Why is null allowed as a key? HashMap special-cases null into bucket 0. Hashtable and ConcurrentHashMap reject null keys and values.
• Is HashMap thread-safe? No. Concurrent writes can corrupt it. Use ConcurrentHashMap, which locks per-bin rather than the whole map (Collections.synchronizedMap locks globally and is much slower under contention).
• HashMap vs LinkedHashMap vs TreeMap? Undefined order / insertion (or access) order / sorted by key at O(log n).

This is the question behind the question. Breaking the contract quietly breaks every hash-based collection.

The contract:

1. If a.equals(b) then a.hashCode() == b.hashCode(). Mandatory.
2. Equal hash codes do not imply equality — collisions are legal.
3. Both must be consistent: same object, same inputs, same answer.

What goes wrong if you override only equals:

Set<Point> set = new HashSet<>();
set.add(new Point(1, 2));
set.contains(new Point(1, 2));   // false! Different hashCode -> different bucket

The lookup never reaches your equals because it searches the wrong bucket. Always override both, together.

Correct implementation:

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Point p)) return false;   // handles null too
    return x == p.x && y == p.y;
}

@Override
public int hashCode() {
    return Objects.hash(x, y);
}

The mutable-key trap: if you mutate a field used in hashCode() after inserting the object into a HashSet, the object is stranded in the old bucket — contains() returns false even though the object is physically in the set. Rule: hash keys should be immutable.

Records give you both for free:

record Point(int x, int y) {}   // equals, hashCode, toString generated

Mentioning records here is a cheap way to show you know modern Java.

Interviewers often skip the algorithm and just ask "which collection would you use, and why?"

Need	Choice	Why
Indexed access, mostly appends	ArrayList	O(1) get, cache-friendly
Heavy insert/remove at the head	ArrayDeque	O(1) both ends; beats LinkedList in practice
Unique elements, fast membership	HashSet	O(1) contains
Unique + insertion order	LinkedHashSet	order without sorting cost
Unique + sorted	TreeSet	O(log n), gives first(), ceiling(), headSet()
Key → value, no order	HashMap	O(1) average
Key → value, sorted keys / range queries	TreeMap	floorKey, subMap
LRU cache	LinkedHashMap	access-order mode + removeEldestEntry
Top-K / scheduling	PriorityQueue	O(log n) insert, O(1) peek min
Stack	ArrayDeque	Stack is legacy and synchronised
Concurrent map	ConcurrentHashMap	per-bin locking

Top-K with a heap — a very common follow-up:

// Keep a MIN-heap of size k to find the k LARGEST elements
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int n : nums) {
    heap.offer(n);
    if (heap.size() > k) heap.poll();   // evict the smallest
}
// heap now holds the k largest; O(n log k) time, O(k) space

Being able to explain why a min-heap finds the maximum is the whole point of the question.

LinkedList warning: its get(i) is O(n). It is almost never the right answer; if you say it, be ready to defend it.

Comparator chaining — expect to write this live:

employees.sort(
    Comparator.comparing(Employee::getDepartment)
              .thenComparing(Employee::getSalary, Comparator.reverseOrder())
              .thenComparing(Employee::getName)
);

Watch the null handling: Comparator.nullsFirst(Comparator.naturalOrder()) wraps a comparator to tolerate nulls.

Comparable vs Comparator: Comparable is the class's own natural order (compareTo, one per class); Comparator is an external strategy (many per class). If you cannot modify the class, or need several orderings, use Comparator.

Never subtract to compare ints — a - b overflows for large values. Use Integer.compare(a, b).

Stream operations worth memorising:

Map<String, List<Employee>> byDept = employees.stream()
    .collect(Collectors.groupingBy(Employee::getDepartment));

Map<String, Long> countByDept = employees.stream()
    .collect(Collectors.groupingBy(Employee::getDepartment, Collectors.counting()));

double avg = employees.stream().mapToInt(Employee::getSalary).average().orElse(0);

String names = employees.stream().map(Employee::getName)
    .collect(Collectors.joining(", "));

Optional<Employee> top = employees.stream()
    .max(Comparator.comparingInt(Employee::getSalary));

List<Employee> senior = employees.stream()
    .filter(e -> e.getYears() > 5)
    .sorted(Comparator.comparing(Employee::getName))
    .toList();                       // Java 16+; immutable result

Stream facts interviewers test:

• Streams are lazy — nothing runs until a terminal operation (collect, forEach, reduce, count).
• A stream is single-use; reusing one throws IllegalStateException.
• map transforms 1→1; flatMap flattens 1→many.
• Don't mutate external state inside a stream — that is what collect is for.
• parallelStream() is not free: it helps only for large, CPU-bound, stateless work.

Optional — use it as a return type for "might be absent". Not for fields, not for parameters.

Optional<User> found = repo.findByEmail(email);

String name = found.map(User::getName).orElse("Anonymous");
found.ifPresent(this::sendWelcome);
User user = found.orElseThrow(() -> new NotFoundException(email));

Calling .get() without checking defeats the purpose — say orElseThrow instead.

Checked vs unchecked exceptions: checked (IOException) must be declared or caught; unchecked (RuntimeException, NullPointerException) need not be. Modern practice leans on unchecked exceptions for programming errors and reserves checked ones for genuinely recoverable conditions.

try (BufferedReader r = Files.newBufferedReader(path)) {   // try-with-resources
    return r.readLine();
}                                    // close() runs automatically, even on throw

finally trap: a return inside finally swallows an in-flight exception. Never return from finally.

The gotchas that separate candidates:

Integer a = 127, b = 127;
a == b;                 // true  — Integer cache covers -128..127
Integer c = 128, d = 128;
c == d;                 // false — different objects; always use .equals()

List<String> fixed = Arrays.asList("a", "b");
fixed.add("c");         // UnsupportedOperationException — fixed-size view

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3));
for (Integer n : nums) {
    if (n == 2) nums.remove(n);      // ConcurrentModificationException
}
nums.removeIf(n -> n == 2);          // correct

Map<String,Integer> m = new HashMap<>();
int v = m.get("missing");            // NPE — unboxing a null Integer
int safe = m.getOrDefault("missing", 0);

0.1 + 0.2 == 0.3;                    // false — use BigDecimal for money

Each of these has been a real interview question. Knowing why — not just that — is what gets scored.