HashMap O(n) Bug — Java Collections Interview Questions

Every Java backend role — from fintech startups to FAANG-scale companies — will grill you on Collections. Not because interviewers enjoy trivia, but because how you choose and use data structures reveals whether you actually understand the trade-offs of your code. A developer who reaches for an ArrayList when they need a HashSet is a developer who will accidentally write O(n) lookups in production hot paths.

The Collections Hierarchy — Why It Exists and How It Flows

The Java Collections Framework (JCF) was introduced in Java 1.2 to replace a mess of unrelated classes — Vector, Hashtable, Stack — that had no common interface and couldn't be swapped out without rewriting calling code. The designers solved this with a clean interface hierarchy.

At the top sits Iterable, which just means 'you can loop over me'. Below it is Collection, which adds size(), add(), remove(), and contains(). From Collection, three main branches split off: List (ordered, index-based), Set (no duplicates), and Queue (designed for hold-and-process workflows). Map sits separately because it stores key-value pairs rather than individual elements — it's not technically a Collection, which catches a lot of people out in interviews.

Understanding WHY the hierarchy is designed this way lets you write code to interfaces (List instead of ArrayList), making it trivially easy to swap implementations later without breaking callers. That's the entire point of the abstraction.

package io.thecodeforge.collections;

import java.util.*;

public class HierarchyDemo {
    public static void main(String[] args) {
        // Programming to the interface (List) is the golden rule.
        List<String> festivalLineup = new ArrayList<>();
        festivalLineup.add("Arctic Monkeys");
        festivalLineup.add("Kendrick Lamar");
        festivalLineup.add("Arctic Monkeys"); // Duplicates allowed

        // Sets enforce uniqueness at the structural level.
        Set<String> uniqueArtists = new HashSet<>(festivalLineup);

        // Map is an outlier — it doesn't extend the Collection interface.
        Map<String, String> wristbandAccess = new HashMap<>();
        wristbandAccess.put("RED", "Backstage");

        boolean isCollection = wristbandAccess instanceof Collection;
        System.out.println("Is HashMap a Collection? " + isCollection);
    }
}

ArrayList vs LinkedList vs HashMap — Choosing the Right Tool

The single most common Collections interview question is: 'When would you use ArrayList over LinkedList?' Most candidates recite 'ArrayList is fast for random access, LinkedList is fast for insertion'. That answer is technically correct but dangerously incomplete.

In practice, LinkedList is almost never the right choice. Its nodes are scattered across heap memory, so traversal hammers the CPU cache — ArrayList's contiguous memory block is cache-friendly and wins in benchmarks even for middle-of-list insertions once lists exceed a few hundred elements. The real alternative to ArrayList for frequent insertions is ArrayDeque or a different algorithm entirely.

HashMap is the workhorse for O(1) average get/put. But 'average' hides a secret: if your keys have poor hashCode() implementations, HashMap degrades to O(n) because all keys land in the same bucket. Java 8 fixed the worst case by converting buckets into balanced trees (O(log n)) when a bucket exceeds 8 entries — but the best fix is always writing good hashCode() methods.

package io.thecodeforge.collections;

import java.util.HashMap;
import java.util.Map;

public class LoadFactorDemo {
    public static void main(String[] args) {
        // Production tip: If you know you need to store 1000 items,
        // initialize with capacity to avoid expensive resizing (rehashing).
        // formula: initialCapacity = expectedSize / loadFactor + 1
        int expectedSize = 1000;
        Map<Integer, String> optimizedMap = new HashMap<>((int) (expectedSize / 0.75f) + 1);

        for (int i = 0; i < expectedSize; i++) {
            optimizedMap.put(i, "Value " + i);
        }
        System.out.println("Map size: " + optimizedMap.size());
    }
}

Fail-Fast vs Fail-Safe Iterators — The Concurrency Trap Everyone Falls Into

Here's a scenario that trips up mid-level developers all the time: you're iterating over a List and removing elements that match a condition. You write a for-each loop, call list.remove() inside it, and boom — ConcurrentModificationException. This isn't a threading bug. It happens on a single thread. Why?

ArrayList's iterator is fail-fast. It tracks a modCount counter that increments on every structural modification. When the iterator's next() checks its expected count against the list's current count and finds a mismatch, it throws immediately — not silently corrupt data. This is a deliberate design choice: fail loudly rather than return unpredictable results.

The fix is to use Iterator.remove() directly, or the removeIf() method (Java 8+), or collect elements to remove into a separate list first.

package io.thecodeforge.collections;

import java.util.*;
import java.util.stream.Collectors;

public class SafeRemoval {
    public static void main(String[] args) {
        List<String> logs = new ArrayList<>(List.of("INFO", "DEBUG", "ERROR", "WARN"));

        // The modern, production-standard way to remove items safely
        logs.removeIf(log -> log.equals("DEBUG"));

        // Alternative: Using streams to create a new immutable collection
        List<String> criticalLogs = logs.stream()
            .filter(log -> !log.equals("INFO"))
            .collect(Collectors.toUnmodifiableList());

        System.out.println("Cleaned Logs: " + criticalLogs);
    }
}

HashMap Internals — hashCode(), equals(), and Java 8's Tree Buckets

If there's one Collections topic that separates candidates who've read books from candidates who've debugged production systems, it's HashMap internals. You need to know this cold.

When you call map.put(key, value), Java computes key.hashCode(), applies a supplemental hash function to spread bits, then uses (n-1) & hash to find a bucket index. If the bucket is empty, your entry goes in. If it's occupied, Java calls equals() to check if it's the same key (update) or a different key (collision, add to the bucket chain).

Java 8 made a critical improvement: when a bucket chain exceeds 8 entries AND the table has at least 64 buckets, the chain converts to a balanced Red-Black tree. This caps worst-case lookup at O(log n) instead of O(n). The practical lesson: if your key class overrides equals() but NOT hashCode(), all instances will hash to the same bucket, causing HashMap to behave like a linked list. Always override both, always together.

package io.thecodeforge.collections;

import java.util.Objects;

/**
 * A production-grade immutable key for use in HashMaps.
 */
public final class ProperKey {
    private final String id;
    private final int version;

    public ProperKey(String id, int version) {
        this.id = id;
        this.version = version;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        ProperKey that = (ProperKey) o;
        return version == that.version && Objects.equals(id, that.id);
    }

    @Override
    public int hashCode() {
        // Uses a high-quality hash multiplier (31) internally
        return Objects.hash(id, version);
    }
}

ConcurrentHashMap: The Thread-Safe HashMap Every Senior Engineer Must Understand

When interviewers ask 'How would you handle concurrent access to a Map?', the correct answer is never Hashtable. Hashtable is legacy — it adds synchronized to every method, serialising all access, killing throughput. The modern answer is ConcurrentHashMap.

ConcurrentHashMap in Java 8+ uses a completely different approach: it partitions the map into a set of buckets (the same as HashMap) but uses Compare-And-Swap (CAS) for lock-free reads, and synchronizes only on the first node of a bucket for writes. This allows multiple threads to read and write different buckets simultaneously. The internal structure is a Node array where each node is either a linked list node or a tree node (same as HashMap).

Key interview points: ConcurrentHashMap does NOT lock the entire map for reads. It uses volatile reads on the table reference and per-bucket CAS for insertion. The size() method is not a constant-time operation in Java 8+ — it requires summing per-bucket counts. Also, ConcurrentHashMap does not allow null keys or null values (to avoid ambiguity between 'key missing' and 'key mapped to null').

package io.thecodeforge.collections;

import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;

public class ConcurrentHashMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> hitCount = new ConcurrentHashMap<>();

        // Thread-safe, lock-free read path
        // Multiple threads can call merge() concurrently without corruption
        for (int i = 0; i < 10; i++) {
            int threadId = i;
            new Thread(() -> {
                for (int j = 0; j < 1000; j++) {
                    hitCount.merge("/api/checkout", 1, Integer::sum);
                }
            }).start();
        }

        // Let threads finish (naive join, better use CountDownLatch in production)
        try { Thread.sleep(2000); } catch (InterruptedException e) { }

        System.out.println("Final count: " + hitCount.get("/api/checkout"));
    }
}