Collections and Stream API

Solution and explanation

What it is

The Java Collections Framework (JCF, java.util) is a unified set of **interfaces**, **implementations** and **algorithms** for storing and processing groups of objects. Code is written against interfaces (List, Map) so implementations can be swapped without changing the rest of the program.

Hierarchy

Iterable
 └─ Collection
     ├─ List      (ordered, duplicates, index access)   ArrayList, LinkedList, CopyOnWriteArrayList
     ├─ Set       (no duplicates)                        HashSet, LinkedHashSet, TreeSet
     └─ Queue     (processing order)                     ArrayDeque, PriorityQueue, LinkedList
         └─ Deque (both ends)                            ArrayDeque, LinkedList

Map (key → value, not a Collection)                       HashMap, LinkedHashMap, TreeMap, ConcurrentHashMap

Choosing an implementation

Algorithms in Collections

List<Integer> scores = new ArrayList<>(List.of(70, 95, 82));
Collections.sort(scores);
Collections.reverse(scores);
Collections.max(scores);
Collections.unmodifiableList(scores);
Collections.frequency(scores, 82);

Why it matters

• Program to interfaces: List<Job> jobs = new ArrayList<>();.
• Generics give compile-time type safety.
• Iterators are **fail-fast**: modifying a collection while iterating throws ConcurrentModificationException (use Iterator.remove or removeIf).

Summary

The JCF provides interfaces (List, Set, Queue, Map), ready implementations with known complexity, and utility algorithms; choose the implementation from your access pattern.

Solution and explanation

Comparison

Examples

List<String> applied = new ArrayList<>(List.of("TCS", "Infosys", "TCS"));
System.out.println(applied);          // [TCS, Infosys, TCS] duplicates kept
System.out.println(applied.get(1));   // Infosys

Set<String> companies = new HashSet<>(applied);
System.out.println(companies);        // [Infosys, TCS] duplicates removed
System.out.println(companies.contains("TCS"));   // true, O(1)

Map<String, Integer> applicationsPerCompany = new HashMap<>();
for (String c : applied) applicationsPerCompany.merge(c, 1, Integer::sum);
System.out.println(applicationsPerCompany);      // {TCS=2, Infosys=1}
System.out.println(applicationsPerCompany.getOrDefault("Wipro", 0));   // 0

Iterating a Map

for (Map.Entry<String, Integer> e : applicationsPerCompany.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}
applicationsPerCompany.forEach((k, v) -> System.out.println(k + "=" + v));

How a Set guarantees uniqueness

HashSet is backed by a HashMap (elements are keys). It uses hashCode() then equals(); if you put your own objects in a Set or use them as Map keys, override both consistently.

Choosing

• Ordered collection, duplicates allowed, positional access: **List**.
• "Have I seen this?" or remove duplicates: **Set**.
• Look something up by an identifier, count occurrences, group: **Map**.

Summary

List keeps an ordered sequence with duplicates, Set keeps unique elements, Map associates unique keys with values; pick by whether you need order, uniqueness or lookup by key.

Solution and explanation

Internal structure

• **ArrayList:** a resizable array. Elements sit next to each other in memory.
• **LinkedList:** a doubly linked list. Each element is a node object with prev and next pointers. It implements both List and Deque.

Complexity

Reality in benchmarks

ArrayList is faster in almost all real programs, even for many middle inserts of moderate size: copying a contiguous array (System.arraycopy) is very fast and CPU-cache-friendly, while walking linked nodes scattered across the heap causes cache misses.

List<Integer> a = new ArrayList<>();
List<Integer> l = new LinkedList<>();
for (int i = 0; i < 1_000_000; i++) { a.add(i); l.add(i); }
a.get(500_000);   // instant
l.get(500_000);   // walks 500,000 nodes

A classic mistake: for (int i = 0; i < linked.size(); i++) linked.get(i) is O(n²).

When LinkedList makes sense

• You need a queue or deque and many removals from both ends; but ArrayDeque is usually better still.
• You remove elements while iterating with a ListIterator over very large lists.

Summary

ArrayList gives O(1) random access and is the default choice; LinkedList offers O(1) insertions at the ends or at an iterator position but has O(n) access and higher memory use, so it is rarely the better option.

Solution and explanation

HashMap internals

• An array of **buckets**; index = hash(key) & (n - 1).
• Collisions go into a linked list in the bucket; since Java 8 a bucket with more than 8 entries (and table size ≥ 64) becomes a **red-black tree**, so worst-case lookup is O(log n) instead of O(n).
• Default capacity 16, **load factor 0.75**: when size exceeds capacity × 0.75 the table doubles and entries are rehashed.
• Allows one null key and null values.
• **Not thread-safe:** concurrent puts can lose updates, and resizing during concurrent access can corrupt the structure.

ConcurrentHashMap internals (Java 8+)

• Same bucket array, but writes lock only **one bucket** (CAS for an empty bucket, synchronized on the first node otherwise). Many threads can write to different buckets at once.
• Reads take **no lock** (volatile reads).
• Resizing is done cooperatively by several threads.
• **No null keys or values**: get returning null must mean "absent", not "mapped to null".
• Iterators are **weakly consistent**: no ConcurrentModificationException; they may or may not show concurrent updates.

Comparison

Atomic compound operations

ConcurrentHashMap<String, Integer> views = new ConcurrentHashMap<>();

// Wrong even on ConcurrentHashMap: check-then-act race
if (!views.containsKey(jobId)) views.put(jobId, 0);
views.put(jobId, views.get(jobId) + 1);

// Correct: atomic per key
views.merge(jobId, 1, Integer::sum);
views.computeIfAbsent(city, c -> new ConcurrentLinkedQueue<>()).add(job);

For high-contention counters, ConcurrentHashMap<String, LongAdder> is faster.

Summary

Use HashMap in single-threaded code; use ConcurrentHashMap when threads share a map, and use its atomic methods (merge, compute, putIfAbsent) instead of check-then-act.

Solution and explanation

Comparable: natural order inside the class

public class Job implements Comparable<Job> {
    String title; int salary; LocalDate postedOn;

    @Override
    public int compareTo(Job other) {
        return Integer.compare(this.salary, other.salary);   // natural order: by salary
    }
}
Collections.sort(jobs);          // uses compareTo
new TreeSet<Job>(jobs);          // also uses compareTo

One natural order per class, written in the class itself (java.lang.Comparable, method compareTo(T)).

Comparator: any order, outside the class

Comparator<Job> byNewest = Comparator.comparing(Job::getPostedOn).reversed();
Comparator<Job> byTitleThenSalary = Comparator.comparing(Job::getTitle)
        .thenComparing(Job::getSalary, Comparator.reverseOrder());

jobs.sort(byNewest);
jobs.sort(byTitleThenSalary);
jobs.sort(Comparator.comparing(Job::getCity, Comparator.nullsLast(Comparator.naturalOrder())));

java.util.Comparator, method compare(T a, T b). Create as many orderings as you need, even for classes you cannot modify (e.g. third-party types).

Comparison

Pitfall: subtraction

return this.salary - other.salary;   // can overflow for large or negative ints
return Integer.compare(this.salary, other.salary);   // safe

Summary

Comparable defines one natural ordering inside the class; Comparator defines any number of external orderings, built fluently with comparing, thenComparing and reversed.

Solution and explanation

What it is

The Stream API (Java 8, java.util.stream) processes sequences of elements in a **declarative, functional** style: you describe *what* to compute (filter, transform, group) instead of writing loops. A stream is not a data structure; it is a pipeline over a source (collection, array, file lines, generator).

List<String> topJavaCompanies = jobs.stream()
        .filter(j -> j.getSkills().contains("Java"))
        .filter(j -> j.getSalary() >= 1_000_000)
        .sorted(Comparator.comparing(Job::getSalary).reversed())
        .map(Job::getCompany)
        .distinct()
        .limit(5)
        .toList();

The same with loops would need a temporary list, a sort, a set for uniqueness and a counter.

Properties

• **Lazy:** intermediate operations do nothing until a terminal operation runs; elements flow one by one through the whole pipeline, and limit can stop early.
• **Single use:** a stream cannot be reused after a terminal operation (IllegalStateException).
• **Does not modify the source.**
• **Can be parallel:** parallelStream() splits work across the ForkJoin pool.

Creating streams

list.stream();
Arrays.stream(new int[]{1, 2, 3});           // IntStream
Stream.of("a", "b");
IntStream.rangeClosed(1, 10);
Files.lines(Path.of("jobs.csv"));            // close it (try-with-resources)
Stream.iterate(1, x -> x * 2).limit(10);

Powerful collectors

Map<String, List<Job>> byCity = jobs.stream().collect(Collectors.groupingBy(Job::getCity));
Map<String, Long> countByCity = jobs.stream().collect(Collectors.groupingBy(Job::getCity, Collectors.counting()));
Map<String, Double> avgSalary = jobs.stream().collect(Collectors.groupingBy(Job::getCity, Collectors.averagingInt(Job::getSalary)));
Map<Boolean, List<Job>> remoteSplit = jobs.stream().collect(Collectors.partitioningBy(Job::isRemote));
String titles = jobs.stream().map(Job::getTitle).collect(Collectors.joining(", "));
IntSummaryStatistics stats = jobs.stream().mapToInt(Job::getSalary).summaryStatistics();

Summary

Streams describe data processing as lazy pipelines of intermediate operations ending in one terminal operation, producing concise, readable code for filtering, mapping, grouping and aggregating.

Solution and explanation

Intermediate operations

Return a **new stream** and are **lazy**: they only describe a step.

Terminal operations

Trigger execution and produce a result or side effect; the stream is consumed.

Laziness demonstrated

Stream<String> s = Stream.of("java", "php", "go", "kotlin")
        .filter(x -> { System.out.println("filter " + x); return x.length() > 2; })
        .map(x -> { System.out.println("map " + x); return x.toUpperCase(); });
System.out.println("nothing printed yet");
s.findFirst();
// filter java
// map java       (stops: findFirst needs only one)

Elements pass **vertically** through the whole pipeline one at a time, not stage by stage.

flatMap example

List<List<String>> skillsPerCandidate = List.of(List.of("Java", "SQL"), List.of("React", "Java"));
Set<String> allSkills = skillsPerCandidate.stream()
        .flatMap(List::stream)
        .collect(Collectors.toCollection(TreeSet::new));   // [Java, React, SQL]

Rules

• Without a terminal operation nothing runs.
• Put filter before map and sorted to process fewer elements.
• Avoid side effects in intermediate operations (except peek for debugging).

Summary

Intermediate operations are lazy and return streams; a single terminal operation runs the pipeline, element by element, and short-circuiting operations can stop early.

Solution and explanation

filter(): keep what matches

List<Job> remoteJobs = jobs.stream().filter(Job::isRemote).toList();
List<Integer> evens = nums.stream().filter(n -> n % 2 == 0).toList();

Takes a Predicate<T> (returns boolean). Output has the same type, possibly fewer elements.

map(): transform each element

List<String> titles = jobs.stream().map(Job::getTitle).toList();
List<Integer> squares = nums.stream().map(n -> n * n).toList();
int totalSalary = jobs.stream().mapToInt(Job::getSalary).sum();   // primitive stream, no boxing

Takes a Function<T, R>. Same number of elements, possibly a different type.

reduce(): combine everything into one value

int sum = nums.stream().reduce(0, Integer::sum);                 // identity + accumulator
Optional<Integer> max = nums.stream().reduce(Integer::max);      // no identity → Optional
int product = nums.stream().reduce(1, (a, b) -> a * b);

// reduce to a different type: identity, accumulator, combiner (used in parallel)
int totalChars = words.stream().reduce(0, (acc, w) -> acc + w.length(), Integer::sum);

• **Identity:** the starting value and neutral element (0 for sum, 1 for product).
• **Accumulator:** combines the running result with the next element.
• The function must be **associative** so parallel streams give correct results.

Together: total salary of senior Java jobs in Bengaluru

long total = jobs.stream()
        .filter(j -> j.getCity().equals("Bengaluru"))
        .filter(j -> j.getExperience() >= 5)
        .map(Job::getSalary)
        .reduce(0L, Long::sum, Long::sum);

Specialised alternatives to reduce

For common cases prefer clearer methods: sum(), max(), count(), Collectors.summingInt, Collectors.joining. Use collect (mutable reduction) to build collections; using reduce to build a list creates many intermediate copies.

Summary

filter selects elements with a predicate, map transforms each element, and reduce folds all elements into one result using an identity and an associative accumulator.

Solution and explanation

What parallel streams do

list.parallelStream() or .parallel() splits the source into chunks processed on the **common ForkJoinPool** (threads = CPU cores − 1) and then combines the results. It can speed up CPU-heavy work on large data, but often makes code slower or wrong.

Avoid them when

1. **The data is small.** Splitting, scheduling and merging cost more than the work. Below roughly 10,000 simple elements, sequential is usually faster.
2. **The work is I/O-bound** (HTTP calls, database queries, file reads). Threads in the common pool block, starving every other parallel stream and CompletableFuture in the JVM. Use a dedicated executor, virtual threads (Java 21) or async clients instead.
3. **The source splits poorly.** ArrayList, arrays and IntStream.range split well; LinkedList, Stream.iterate and Files.lines split badly.
4. **Operations have shared mutable state.**

List<Integer> out = new ArrayList<>();
nums.parallelStream().forEach(out::add);     // race condition: lost elements or exceptions
List<Integer> safe = nums.parallelStream().toList();   // correct: let the collector combine

1. **Order matters and you use order-sensitive operations** (findFirst, limit, sorted, forEachOrdered): they force extra coordination. forEach on a parallel stream prints in unpredictable order.
2. **Inside a web server request.** Every request competing for the same small common pool hurts throughput and latency under load.
3. **Boxing-heavy pipelines:** use mapToInt/IntStream or the gain disappears.

When they can help

• Large in-memory data (millions of elements), CPU-bound, independent work per element (for example computing scores or hashes), on a machine with spare cores, in a batch job.
• Always **measure** with JMH or realistic timings.

long count = LongStream.rangeClosed(1, 50_000_000).parallel().filter(Primes::isPrime).count();

Summary

Avoid parallel streams for small data, I/O, poorly splitting sources, shared mutable state, order-dependent logic and request-handling code; use them only for large, CPU-bound, independent work after measuring.