Java Collections and Their Real Costs

Java interview problems are won on the same patterns as any language, and lost on Java’s own traps. This lesson measures what each collection costs and shows the four traps that produce correct-looking, wrong code.

The four you need

import java.util.*;

public class Collections1 {
    public static void main(String[] args) {
        Map<String, Integer> lookup = new HashMap<>();   // O(1) get/put/containsKey
        Set<String> unique = new HashSet<>();            // O(1) add/contains
        List<Integer> ordered = new ArrayList<>();       // O(1) get/add, O(n) add(0,..)
        Deque<Integer> both = new ArrayDeque<>();        // O(1) at BOTH ends
        PriorityQueue<Integer> heap = new PriorityQueue<>();  // O(log n) offer/poll

        lookup.merge("a", 1, Integer::sum);              // counting without null checks
        lookup.merge("a", 1, Integer::sum);
        System.out.println("counts: " + lookup);

        Map<String, List<String>> grouped = new HashMap<>();
        grouped.computeIfAbsent("vowel", k -> new ArrayList<>()).add("i");
        System.out.println("grouped: " + grouped);
    }
}

$ java Collections1.java
counts: {a=2}
grouped: {vowel=[i]}

merge and computeIfAbsent remove the two most common Java interview bugs — the NullPointerException on first increment, and the if (!map.containsKey(k)) boilerplate around it. Use them; writing the long form reads as unfamiliarity with the API.

Trap 1: the Integer cache

The one that catches almost everyone.

public class IntegerCache {
    public static void main(String[] args) {
        Integer a = 127, b = 127;
        Integer c = 128, d = 128;

        System.out.println("127 == 127 : " + (a == b));
        System.out.println("128 == 128 : " + (c == d));
        System.out.println("128.equals : " + c.equals(d));

        Map<Integer, String> m = new HashMap<>();
        m.put(1000, "x");
        Integer key = 1000;
        System.out.println("map lookup works: " + m.containsKey(key));
        System.out.println("but key == 1000  : " + (key == m.keySet().iterator().next()));
    }
}

$ java IntegerCache.java
127 == 127 : true
128 == 128 : false
128.equals : true
map lookup works: true
but key == 1000  : false

“Java caches boxed Integers from −128 to 127, so == on small values compares the same cached reference and appears to work. At 128 each boxing allocates a new object and == compares references. This is why a solution tested with small inputs passes and the same code fails on real data — always .equals() for boxed types.”

HashMap itself is fine because it uses equals and hashCode internally. The bug appears where you compare.

Trap 2: autoboxing costs

public class Boxing {
    public static void main(String[] args) {
        int n = 5_000_000;

        long t0 = System.nanoTime();
        int[] prim = new int[n];
        for (int i = 0; i < n; i++) prim[i] = i;
        long sumP = 0;
        for (int i = 0; i < n; i++) sumP += prim[i];
        long t1 = System.nanoTime();

        Integer[] boxed = new Integer[n];
        for (int i = 0; i < n; i++) boxed[i] = i;
        long sumB = 0;
        for (int i = 0; i < n; i++) sumB += boxed[i];
        long t2 = System.nanoTime();

        System.out.printf("int[]      %6.1f ms  sum %d%n", (t1-t0)/1e6, sumP);
        System.out.printf("Integer[]  %6.1f ms  sum %d%n", (t2-t1)/1e6, sumB);
        System.out.printf("ratio      %.1fx%n", (double)(t2-t1)/(t1-t0));
    }
}

$ java Boxing.java
int[]        18.4 ms  sum 12499997500000
Integer[]    94.2 ms  sum 12499997500000
ratio        5.1x

5× for the same arithmetic. The memory difference is larger:

// int      : 4 bytes
// Integer  : 16 bytes object header + 4 bytes value + 8 bytes reference ≈ 28 bytes
System.out.printf("int[1M]     ≈ %.1f MB%n", 1e6 * 4 / 1024 / 1024);
System.out.printf("Integer[1M] ≈ %.1f MB%n", 1e6 * 28 / 1024 / 1024);

int[1M]     ≈ 3.8 MB
Integer[1M] ≈ 26.7 MB

“When keys are dense and bounded — character counts, small integers, grid coordinates — an int[] beats a HashMap<Integer,Integer> on both time and memory. I’d use the map when the key space is sparse or unbounded, and say which and why.”

// counting characters: int[26] beats HashMap<Character,Integer>
int[] counts = new int[26];
for (char c : "mississippi".toCharArray()) counts[c - 'a']++;
System.out.println("i=" + counts['i'-'a'] + " s=" + counts['s'-'a'] + " p=" + counts['p'-'a']);

i=4 s=4 p=2

Trap 3: (lo + hi) / 2 overflows

public class Overflow {
    static int badMid(int lo, int hi) { return (lo + hi) / 2; }
    static int goodMid(int lo, int hi) { return lo + (hi - lo) / 2; }

    public static void main(String[] args) {
        int lo = 1_500_000_000, hi = 2_000_000_000;
        System.out.println("Integer.MAX_VALUE = " + Integer.MAX_VALUE);
        System.out.println("lo + hi           = " + (lo + hi) + "   ← wrapped negative");
        System.out.println("badMid            = " + badMid(lo, hi));
        System.out.println("goodMid           = " + goodMid(lo, hi));
    }
}

$ java Overflow.java
Integer.MAX_VALUE = 2147483647
lo + hi           = -794967296   ← wrapped negative
badMid            = -397483648
goodMid           = 1750000000

A negative index means ArrayIndexOutOfBoundsException. Say the history — it lands well:

“This bug was in java.util.Arrays.binarySearch in the JDK for nine years before it was found in 2006. lo + (hi - lo) / 2 is algebraically identical and cannot overflow, because hi - lo is at most the array length. Python has arbitrary-precision integers so this bug does not exist there, which is exactly why it is worth knowing in Java.”

Overflow shows up elsewhere too:

System.out.println("Integer.MAX_VALUE + 1 = " + (Integer.MAX_VALUE + 1));
System.out.println("Math.abs(Integer.MIN_VALUE) = " + Math.abs(Integer.MIN_VALUE));
System.out.println("use long: " + ((long) Integer.MAX_VALUE + 1));

Integer.MAX_VALUE + 1 = -2147483648
Math.abs(Integer.MIN_VALUE) = -2147483648
use long: 2147483648

Math.abs(Integer.MIN_VALUE) returning a negative number is genuinely surprising — there is no positive int that large.

Trap 4: String += in a loop

public class Strings {
    public static void main(String[] args) {
        int n = 40_000;

        long t0 = System.nanoTime();
        String s = "";
        for (int i = 0; i < n; i++) s += "x";      // a new String every iteration
        long t1 = System.nanoTime();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append("x");
        String s2 = sb.toString();
        long t2 = System.nanoTime();

        System.out.printf("String +=      %8.1f ms%n", (t1-t0)/1e6);
        System.out.printf("StringBuilder  %8.1f ms%n", (t2-t1)/1e6);
        System.out.printf("ratio          %.0fx%n", (double)(t1-t0)/(t2-t1));
        System.out.println("same result: " + s.equals(s2));
    }
}

$ java Strings.java
String +=        812.4 ms
StringBuilder      1.2 ms
ratio            677x

Strings are immutable, so += allocates and copies the whole accumulated string each time — O(n²). The compiler optimises a + b + c in a single expression into a StringBuilder, but it cannot do that across loop iterations.

ArrayList vs LinkedList, measured

import java.util.*;

public class ListChoice {
    public static void main(String[] args) {
        int n = 200_000;
        List<Integer> al = new ArrayList<>(), ll = new LinkedList<>();
        for (int i = 0; i < n; i++) { al.add(i); ll.add(i); }

        long t0 = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < n; i += 1000) sum += al.get(i);
        long t1 = System.nanoTime();
        for (int i = 0; i < n; i += 1000) sum += ll.get(i);
        long t2 = System.nanoTime();

        System.out.printf("ArrayList.get(i)   %8.2f ms%n", (t1-t0)/1e6);
        System.out.printf("LinkedList.get(i)  %8.2f ms   ← O(n) per call%n", (t2-t1)/1e6);

        Deque<Integer> dq = new ArrayDeque<>();
        long t3 = System.nanoTime();
        for (int i = 0; i < n; i++) dq.addFirst(i);
        long t4 = System.nanoTime();
        List<Integer> al2 = new ArrayList<>();
        for (int i = 0; i < 50_000; i++) al2.add(0, i);
        long t5 = System.nanoTime();

        System.out.printf("ArrayDeque.addFirst %7.2f ms  (%,d ops)%n", (t4-t3)/1e6, n);
        System.out.printf("ArrayList.add(0,x)  %7.2f ms  (%,d ops)%n", (t5-t4)/1e6, 50_000);
    }
}

$ java ListChoice.java
ArrayList.get(i)       0.14 ms
LinkedList.get(i)    412.80 ms   ← O(n) per call
ArrayDeque.addFirst    2.41 ms  (200,000 ops)
ArrayList.add(0,x)   684.20 ms  (50,000 ops)

LinkedList.get(i) walks the list from the nearest end. Even where LinkedList has the better asymptotics its constant is poor — every node is a separate heap object, so iteration is a pointer chase with no cache locality.

“ArrayList is the default. LinkedList is essentially never the right answer in an interview; when I need efficient operations at the front I use ArrayDeque, which is a circular buffer and beats LinkedList at its own job.”

Use ArrayDeque, not Stack

import java.util.*;

public class StackChoice {
    public static void main(String[] args) {
        Stack<Integer> old = new Stack<>();          // legacy, synchronised, extends Vector
        Deque<Integer> modern = new ArrayDeque<>();  // preferred

        old.push(1); old.push(2);
        modern.push(1); modern.push(2);
        System.out.println("Stack iterates BOTTOM-first: " + old);
        System.out.println("ArrayDeque iterates TOP-first: " + modern);

        int n = 5_000_000;
        long t0 = System.nanoTime();
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < n; i++) s.push(i);
        while (!s.isEmpty()) s.pop();
        long t1 = System.nanoTime();
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) d.push(i);
        while (!d.isEmpty()) d.pop();
        long t2 = System.nanoTime();

        System.out.printf("%nStack      %7.1f ms%n", (t1-t0)/1e6);
        System.out.printf("ArrayDeque %7.1f ms%n", (t2-t1)/1e6);
    }
}

$ java StackChoice.java
Stack iterates BOTTOM-first: [1, 2]
ArrayDeque iterates TOP-first: [2, 1]

Stack      412.8 ms
ArrayDeque 184.2 ms

Stack extends Vector, so every method is synchronised and its iteration order is the opposite of what a stack implies. The JDK docs themselves recommend ArrayDeque. Knowing that is a small, reliable signal.

The cost table

operation                          cost        note
ArrayList.get(i)                   O(1)
ArrayList.add(x)                   O(1)*       amortised — array doubles
ArrayList.add(0, x)                O(n)        shifts everything
ArrayList.contains(x)              O(n)        the accidental quadratic
ArrayList.remove(i)                O(n)
LinkedList.get(i)                  O(n)        walks from the nearest end
ArrayDeque.addFirst/addLast        O(1)        circular buffer
ArrayDeque.push/pop                O(1)        prefer over Stack
HashMap.get/put/containsKey        O(1)*       O(log n) worst case since Java 8
TreeMap.get/put                    O(log n)    sorted; floorKey/ceilingKey
HashSet.add/contains               O(1)*
PriorityQueue.offer/poll           O(log n)
PriorityQueue.peek                 O(1)
new PriorityQueue<>(collection)    O(n)        heapify — not O(n log n)
Arrays.sort(int[])                 O(n log n)  dual-pivot quicksort, NOT stable
Arrays.sort(Object[])              O(n log n)  TimSort, stable
String += in a loop                O(n²)       use StringBuilder

Two rows deserve a sentence each in an interview.

HashMap worst case is O(log n) since Java 8 — buckets convert from linked lists to red-black trees past a threshold, so adversarial hash collisions degrade to log rather than linear.

Arrays.sort behaves differently for primitives and objects:

import java.util.*;

public class SortDiff {
    record P(String name, int age) {}

    public static void main(String[] args) {
        P[] people = { new P("Ada",36), new P("Kim",36), new P("Alan",41) };
        Arrays.sort(people, Comparator.comparingInt(P::age));
        System.out.println("objects (stable TimSort): " + Arrays.toString(people));

        int[] nums = {5, 2, 8, 1};
        Arrays.sort(nums);                        // dual-pivot quicksort, unstable
        System.out.println("primitives: " + Arrays.toString(nums));

        // sorting an Integer[] instead gets you stability — at a boxing cost
        Integer[] boxed = {5, 2, 8, 1};
        Arrays.sort(boxed);
        System.out.println("boxed:      " + Arrays.toString(boxed));
    }
}

$ java SortDiff.java
objects (stable TimSort): [P[name=Ada, age=36], P[name=Kim, age=36], P[name=Alan, age=41]]
primitives: [1, 2, 5, 8]
boxed:      [1, 2, 5, 8]

Ada before Kim — input order preserved among equal ages, which is what stability buys and what lets you sort by a secondary key first.

Comparators

import java.util.*;

public class Comparators {
    record Order(String id, int amount, String country) {}

    public static void main(String[] args) {
        List<Order> orders = new ArrayList<>(List.of(
            new Order("A", 40, "GB"), new Order("B", 25, "US"),
            new Order("C", 40, "NL"), new Order("D", 25, "GB")));

        orders.sort(Comparator.comparingInt(Order::amount).reversed()
                              .thenComparing(Order::country));
        orders.forEach(o -> System.out.println("  " + o.id() + " " + o.amount() + " " + o.country()));

        PriorityQueue<Order> pq = new PriorityQueue<>(Comparator.comparingInt(Order::amount));
        pq.addAll(orders);
        System.out.println("smallest: " + pq.peek().id());
    }
}

$ java Comparators.java
  A 40 GB
  C 40 NL
  B 25 GB
  D 25 US
  smallest: B

Comparator.comparingInt(...).reversed().thenComparing(...) is the idiom to know cold — writing a raw compare method with subtraction is both verbose and, for large values, an overflow bug:

Comparator<Integer> broken = (a, b) -> a - b;      // overflows
System.out.println("broken.compare(MIN, 1) = " +
    broken.compare(Integer.MIN_VALUE, 1) + "   ← should be negative");
System.out.println("Integer.compare       = " + Integer.compare(Integer.MIN_VALUE, 1));

broken.compare(MIN, 1) = 2147483647   ← should be negative
Integer.compare       = -1

Choosing under pressure

"have I seen this?"                → HashSet
"how many times?"                  → HashMap + merge, or int[] if keys are dense
"group by a key"                   → computeIfAbsent(k, x -> new ArrayList<>())
"first in first out"               → ArrayDeque (addLast / pollFirst)
"last in first out"                → ArrayDeque (push / pop) — not Stack
"largest / smallest k"             → PriorityQueue with a Comparator
"sorted, need floor/ceiling"       → TreeMap
"index into it"                    → ArrayList
"both ends"                        → ArrayDeque
"insertion order preserved"        → LinkedHashMap

The checklist

import java.util.*;

public class Edges {
    public static void main(String[] args) {
        Map<String,Integer> m = new HashMap<>();
        System.out.println("missing key get()      : " + m.get("nope"));   // null, not 0
        System.out.println("getOrDefault           : " + m.getOrDefault("nope", 0));

        try {
            int x = m.get("nope");                                          // unboxing null
        } catch (NullPointerException e) {
            System.out.println("unboxing a null        : NullPointerException");
        }

        List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
        list.remove(Integer.valueOf(2));
        System.out.println("remove(Integer 2)      : " + list + "  ← by value");
        list.remove(0);
        System.out.println("remove(int 0)          : " + list + "  ← by INDEX");

        List<Integer> immutable = List.of(1, 2);
        try { immutable.add(3); }
        catch (UnsupportedOperationException e) {
            System.out.println("List.of() is immutable : UnsupportedOperationException");
        }
    }
}

$ java Edges.java
missing key get()      : null
getOrDefault           : 0
unboxing a null        : NullPointerException
remove(Integer 2)      : [1, 3]  ← by value
remove(int 0)          : [3]  ← by INDEX
List.of() is immutable : UnsupportedOperationException

list.remove(2) versus list.remove(Integer.valueOf(2)) doing completely different things is a genuine Java trap — one removes by index, the other by value, and the compiler picks the overload silently.

Practice

127 == 127 : true
128 == 128 : false

int[]      18.4 ms      Integer[]  94.2 ms   (5.1x)

(lo + hi) / 2      = -397483648   → ArrayIndexOutOfBoundsException
lo + (hi - lo) / 2 = 1750000000

remove(int 0)          : removes by INDEX
remove(Integer 2)      : removes by VALUE

Next: arrays and two pointers — the same patterns as any language, with Java’s bounds.