Why is using a HashSet for the lookup list faster than filter(list::contains) for intersection queries?

• ArrayList.contains scans the list linearly: O(m) per call.
• Filtering n elements against a list: O(n*m) total.
• HashSet.contains computes hash and probes one bucket: O(1) average per call.
• Filtering n elements against a set: O(n) total (after O(m) set build).
• Build the set once outside the stream; use set::contains inside filter.

Why is list contains slow?

ArrayList.contains walks the list element by element, comparing each with equals. For a list of m elements, each contains call costs O(m). In an intersection where you call contains for each of n outer elements, the total is O(n*m).

Why is set contains fast?

HashSet.contains computes the hash code, jumps to the correct bucket, and compares within the bucket. Average cost: O(1). For n outer elements, the total filter cost is O(n).

How do you demonstrate the fix?

package com.bank.hr;

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

public class SetVsListContains {

    public static void main(String[] args) {
        List<String> allAccounts = IntStream.rangeClosed(1, 100_000)
            .mapToObj(i -> "SAV" + i)
            .toList();

        List<String> blockedIds = IntStream.rangeClosed(1, 10_000)
            .mapToObj(i -> "SAV" + (i * 3))  // every 3rd account
            .toList();

        // SLOW: O(n*m) = 100K * 10K = 1 billion comparisons
        long start = System.nanoTime();
        long slowCount = allAccounts.stream()
            .filter(id -> !blockedIds.contains(id))
            .count();
        long slowTime = System.nanoTime() - start;

        // FAST: O(n+m) = 110K operations
        Set<String> blockedSet = new HashSet<>(blockedIds);
        start = System.nanoTime();
        long fastCount = allAccounts.stream()
            .filter(id -> !blockedSet.contains(id))
            .count();
        long fastTime = System.nanoTime() - start;

        System.out.printf("List: %,d ms, count=%d%n", slowTime / 1_000_000, slowCount);
        System.out.printf("Set:  %,d ms, count=%d%n", fastTime / 1_000_000, fastCount);
    }
}

List: 4,200 ms, count=66667
Set:  12 ms, count=66667

What is the complexity comparison?

| Approach | Per-call cost | Total (n outer, m lookup) |
|---|---|---|
| list::contains | O(m) linear scan | O(n * m) |
| set::contains | O(1) hash lookup | O(n + m) |

What are common mistakes?

Mistake: Not building the set outside the stream.

// WRONG: building a new set per element (still O(n*m))
allAccounts.stream()
    .filter(id -> !new HashSet<>(blockedIds).contains(id))  // set built n times!
    .count();

// CORRECT: build once outside
Set<String> blockedSet = new HashSet<>(blockedIds);
allAccounts.stream()
    .filter(id -> !blockedSet.contains(id))
    .count();

What about custom objects?

HashSet relies on correct hashCode and equals. If those are wrong, the set degrades toward linear probing and the benefit evaporates.

// Records auto-generate correct hashCode and equals
record AccountId(String branch, int number) {}
Set<AccountId> blockedAccounts = new HashSet<>(blockedList);

What about using a Map for lookup?

When you need to look up a related value (not just membership), use a Map instead of a Set.

Map<String, Employee> employeeMap = staff.stream()
    .collect(Collectors.toMap(Employee::id, e -> e));

// O(1) lookup by id
Employee emp = employeeMap.get("SAV2001");

What should a senior engineer know?

Recognizing the hidden O(n*m) cost of list::contains inside a filter and converting to set::contains is the canonical first optimization for membership and intersection queries. The one-time cost of building the set is O(m), which is dwarfed by the savings for any non-trivial n.

What are common interview follow-up questions?

• "What is the complexity of the list approach?" O(n*m).
• "What is the complexity of the set approach?" O(n+m).
• "What if hashCode is wrong?" The set degrades toward O(m) per lookup.
• "What about LinkedHashSet?" Same O(1) lookup, but preserves insertion order.