Collection Design, Streams, and Performance

Introduction

Java collections are central to almost every non-trivial application. They represent groups of objects, support searching and ordering, enable data transformation, and provide the foundation for many concurrent and database-oriented programs. However, choosing a collection merely because it is familiar can produce excessive memory use, poor performance, unsafe mutation, or code that is difficult to maintain.

This chapter develops a systematic approach to collection design. It examines complexity, memory behaviour, ordering, equality, streams, collectors, mutation safety, parallel processing, and performance measurement. The aim is not to memorise one “best” collection, but to select an appropriate representation for a known workload.

Learning Objectives

By the end of this chapter, you should be able to:

• distinguish the major Java collection interfaces and implementations;
• select data structures using time complexity, memory, ordering, and access requirements;
• explain hashing, equality, ordering, and comparator contracts;
• construct readable and correct stream pipelines;
• use collectors for grouping, partitioning, summarising, and reduction;
• identify unsafe mutation and side effects in collection processing;
• evaluate sequential and parallel stream trade-offs;
• design simple, evidence-based performance experiments;
• balance performance, scalability, readability, and maintainability.

1. Collection Abstractions and Design Intent

The Java Collections Framework separates an abstract data type from its implementation. An interface expresses what clients need; an implementation determines how those operations are achieved.

Programming to an interface reduces coupling. For example:

List<String> names = new ArrayList<>();

The variable communicates that list behaviour is required, while the implementation can later be changed if requirements change. ArrayList is commonly appropriate when indexed access and iteration are frequent. LinkedList is not automatically faster: although insertion at a known node can be constant time, locating that node is usually linear, and linked nodes consume additional memory.

A collection decision should therefore begin with operations, not with implementation names. Ask:

1. Are duplicates allowed?
2. Is encounter order significant?
3. Is sorted order required?
4. Are lookups based on a key?
5. Are indexed reads common?
6. Which operations dominate the workload?
7. Is the collection shared between threads?
8. Is bounded memory or predictable latency important?

2. Complexity, Capacity, and Memory

Big-O notation describes how resource requirements grow as input size increases. If a method performs a constant number of operations independent of the number of elements, it is O(1). If it scans all elements once, it is commonly O(n). Sorting typically requires O(n log n) comparisons, although exact behaviour depends on the algorithm and input.

The notation describes growth, not exact running time. A linear operation over a compact array may be faster than a constant-time operation involving hashing, allocation, cache misses, or contention. Consequently, complexity is a design guide, not a substitute for measurement.

2.1 Typical operation costs

These are typical bounds under normal assumptions. Hash-based performance depends on good hash distribution, stable keys, and implementation details. Tree-based performance assumes a balanced tree. Array resizing causes occasional copying, so append is described as amortised constant time: over many appends, the average cost per append remains bounded even though some individual appends are expensive.

2.2 Memory and locality

An ArrayList stores references in a contiguous array. This supports efficient traversal and good processor-cache locality, but resizing may allocate a larger array and copy references. A linked structure stores node objects and links, creating allocation and pointer-navigation overhead. A HashMap needs a table plus entries and may reserve unused capacity to control collisions.

Capacity is not the same as size. Size is the number of stored elements; capacity is the currently allocated room. Excessive capacity wastes memory, while insufficient capacity causes resizing or rehashing. If the approximate number of entries is known, specifying an initial capacity can reduce resizing, but capacity estimates should be based on realistic data rather than arbitrary large values.

3. Equality, Hashing, and Ordering

Collection correctness depends on contracts involving equals, hashCode, and comparison.

The equals contract requires reflexivity, symmetry, transitivity, consistency, and that comparison with null returns false. Whenever two objects are equal, they must have the same hash code:

if (a.equals(b)) {
    assert a.hashCode() == b.hashCode();
}

The reverse is not required: equal hash codes do not imply equality. A HashSet uses hash codes to locate a region and equality to distinguish entries within that region.

Keys in a HashMap should be immutable with respect to fields used by equals and hashCode. If a key changes after insertion, the map may no longer find it in the expected bucket. Records are often useful for value-based keys because they provide stable, generated equality and hash behaviour when their components are appropriately immutable.

Sorted collections use natural ordering or a Comparator. The ordering should normally be consistent with equality. If a comparator considers two distinct objects equal, a TreeSet may retain only one of them. This is not a bug in the set; it follows the comparator’s definition of uniqueness.

Example:

record Student(String id, String name) {}

Set<Student> students = new HashSet<>();
students.add(new Student("S01", "Amina"));

Here, the record’s components define equality. If identity rather than value is required, the design must state that explicitly.

4. Choosing a Collection: A Decision Framework

A practical selection framework considers four dimensions:

1. Semantic requirement: list, set, queue, deque, or map.
2. Dominant operation: indexed access, membership, insertion, removal, priority retrieval, or range query.
3. Ordering requirement: none, insertion order, sorted order, or access order.
4. Operational constraints: memory, concurrency, latency, readability, and expected scale.

For example, suppose an application stores user IDs and repeatedly tests whether an ID has already been processed. A HashSet<String> is usually more appropriate than an ArrayList<String> because membership is the dominant operation. If IDs must be displayed in insertion order, LinkedHashSet is appropriate. If IDs must be returned lexicographically, TreeSet may be preferable, accepting logarithmic operations and comparator costs.

For a first-in-first-out work queue, ArrayDeque is usually preferable to using ArrayList.remove(0), because removing the first array element shifts the remaining elements. For highest-priority processing, use PriorityQueue; do not assume that iterating it produces sorted output. To obtain sorted output, repeatedly remove the head or sort a separate result.

5. Streams as Declarative Collection Processing

A stream is a pipeline for processing a source of elements. It is not a data structure and does not normally store elements independently. A pipeline consists of:

• a source, such as a collection or array;
• intermediate operations, such as filter, map, sorted, and distinct;
• a terminal operation, such as collect, count, forEach, reduce, or findFirst.

List<String> names = List.of("Mina", "Omar", "Mina", "Leo");

List<String> result = names.stream()
        .filter(name -> name.length() >= 4)
        .distinct()
        .sorted()
        .toList();

Intermediate operations are lazy. They describe work that begins when a terminal operation is invoked. Many operations can be fused so that each element passes through several stages without creating a separate collection at each stage.

A stream cannot normally be reused after a terminal operation:

Stream<String> stream = names.stream();
long count = stream.count();
// stream.count();  // IllegalStateException if attempted again

Create a new stream when another traversal is needed.

5.1 Intermediate operations

filter retains elements satisfying a predicate. map transforms one element into one result. flatMap transforms each element into a stream and flattens the results. distinct uses equality, while sorted uses natural ordering or a comparator. limit and skip are useful for bounded processing but may have special costs in parallel pipelines.

Prefer a pipeline that expresses a clear transformation. Avoid placing unrelated business operations in one long chain. Named methods can improve readability:

static boolean isActive(Employee e) {
    return e.active();
}

static String displayName(Employee e) {
    return e.name().trim();
}

5.2 Terminal operations and short-circuiting

findFirst, findAny, anyMatch, allMatch, and noneMatch can stop early. This can make them more efficient than collecting all results. findFirst respects encounter order; findAny may be more flexible in parallel processing.

reduce is suitable for combining values according to an associative operation:

int total = numbers.stream().reduce(0, Integer::sum);

The identity is 0, and addition is associative for mathematical integers. For floating-point values, rounding means that different accumulation orders can produce slightly different results. A collector such as summarizingDouble may be clearer when producing several statistics.

6. Collectors and Result Design

Collectors describe mutable reduction into a result. Common collectors include:

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

Map<Boolean, List<Employee>> statusGroups = employees.stream()
        .collect(Collectors.partitioningBy(Employee::active));

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

groupingBy creates groups according to a classifier. partitioningBy is specialised for a boolean predicate and produces two logical groups. Downstream collectors allow a group to be transformed, counted, summed, or reduced.

For immutable or unmodifiable results, use an explicit finalisation choice:

List<String> names = employees.stream()
        .map(Employee::name)
        .toList();

The result of Stream.toList() is unmodifiable in modern Java APIs. If a mutable list is required, use a collector such as Collectors.toCollection(ArrayList::new). The distinction should be documented because callers may otherwise attempt an unsupported mutation.

6.1 Collector characteristics and correctness

A collector has a supplier, accumulator, combiner, and finisher. In sequential execution, the accumulator adds elements to a result. In parallel execution, partial results are combined. The combiner must produce the same logical result as processing the input sequentially.

A custom collector should be used only when it provides a clear benefit. Incorrect combiners can silently produce wrong results, particularly in parallel streams. Mutable accumulation is safe inside a properly designed collector because each partial result is managed according to the collector contract; arbitrary shared mutation in forEach is not equivalent.

7. Mutation, Immutability, and Side Effects

Unsafe mutation is a major source of collection defects. The following code modifies a list while iterating through it:

for (String item : items) {
    if (item.isBlank()) {
        items.remove(item);
    }
}

This may throw ConcurrentModificationException or produce incorrect behaviour. Safer alternatives include:

items.removeIf(String::isBlank);

or constructing a new result:

List<String> nonBlank = items.stream()
        .filter(item -> !item.isBlank())
        .toList();

A stream pipeline should generally avoid modifying its source or external state. This is dangerous:

List<String> output = new ArrayList<>();
items.parallelStream().forEach(output::add);

The list is not thread-safe, and even a synchronised list may provide poor scalability and obscure the intended result. Prefer a collector:

List<String> output = items.parallelStream()
        .map(String::trim)
        .toList();

Immutability reduces aliasing: if an object cannot change after construction, callers do not need to coordinate every read with a possible write. List.of, Set.of, records, defensive copies, and unmodifiable views are useful tools. An unmodifiable view does not necessarily make the underlying collection immutable; changes to the original collection may still appear through the view. A defensive copy provides stronger isolation.

8. Sequential and Parallel Streams

Parallel streams divide processing among threads in the common fork/join pool. They can help when the dataset is large, operations are CPU-intensive, tasks are independent, and splitting and combining costs are small. They can harm performance when the dataset is small, operations block on I/O, ordering is essential, tasks are cheap, or the application already has competing common-pool work.

A useful conceptual model is:

Here, T_parallel is elapsed parallel time, T_work is total useful work, p is effective parallelism, T_overhead includes task creation and combination, and T_imbalance represents unequal distribution of work. This is an approximation, not a guarantee. It assumes independent tasks and ignores hardware-specific effects such as cache contention and memory bandwidth.

Parallelism is not a replacement for algorithm selection. An O(n) sequential algorithm may outperform a parallel O(n log n) design. Measure with representative data and a reliable benchmark method, such as JMH, rather than timing a single cold execution with System.nanoTime().

9. Performance Evaluation in Practice

Performance includes more than elapsed time:

• Throughput: operations completed per unit time.
• Latency: time taken by one operation or request.
• Memory footprint: heap and auxiliary memory used.
• Allocation rate: objects created per unit time.
• Scalability: behaviour as data volume or concurrent users increase.
• Predictability: variation in response time, including pauses.

A sound experiment changes one meaningful factor at a time. Use realistic data distributions, warm up the JVM, repeat measurements, and report variation rather than a single attractive result. Garbage collection, JIT compilation, CPU frequency, operating-system activity, and database or network effects can all distort results.

Readability is also a performance factor in professional systems. A complicated micro-optimisation that introduces defects may cost more than the time it saves. First select an algorithmically suitable structure, then profile, then optimise the measured bottleneck.

10. Applied Case: Transaction Processing Service

Background

This illustrative case concerns a service that receives transaction records and produces a report of suspicious accounts. Each record contains an account ID, amount, timestamp, and status. The service receives up to several hundred thousand records per batch.

Problem

An initial implementation stores records in an ArrayList, repeatedly scans the list to determine whether an account has appeared, and uses a stream with an external mutable map to accumulate totals. Processing time increases sharply as batches grow, and occasional concurrent executions produce inconsistent totals.

Analysis

The repeated membership scan is linear for each record. If there are n records and the implementation scans an average number proportional to n for each record, the total membership work grows approximately quadratically, or O(n²). The shared mutable map also creates a correctness risk.

Approach

The revised design uses:

Map<String, Double> totals = records.stream()
        .filter(Transaction::successful)
        .collect(Collectors.groupingBy(
                Transaction::accountId,
                Collectors.summingDouble(Transaction::amount)));

Set<String> suspicious = totals.entrySet().stream()
        .filter(entry -> entry.getValue() >= 10_000.0)
        .map(Map.Entry::getKey)
        .collect(Collectors.toUnmodifiableSet());

The map expresses account-to-total association directly. The collector owns accumulation, and the final set communicates that the report should not be modified. If exact financial calculations are required, BigDecimal should generally replace double, with an explicit scale and rounding policy.

Outcome

The revised design removes repeated membership scans, makes the aggregation logic explicit, and avoids unsafe external mutation. Actual improvement must still be measured because input distribution, account cardinality, memory pressure, and downstream reporting costs affect the result.

Learning Points

• Choose a structure that represents the dominant operation.
• Replace shared mutation with a collector or controlled reduction.
• Treat numerical representation as a domain decision.
• Verify performance with realistic benchmarks rather than assumptions.

11. Challenges, Governance, and Contemporary Practice

Collection design can affect privacy and governance. A cache or in-memory collection may retain personal data longer than necessary. Applications should define retention, access control, deletion, and logging policies. Sensitive values should not be exposed through diagnostic dumps or careless stream logging.

Modern Java development increasingly uses records, immutable result types, pattern matching features, and sequenced collection APIs where available. These features can improve clarity, but they do not eliminate the need to understand contracts and complexity. Frameworks and AI-assisted code generation may suggest a collection or stream pipeline, yet generated code must be reviewed for equality semantics, numeric correctness, mutation safety, exception handling, and benchmark evidence.

Best practice is therefore evidence-based: state the requirement, select the simplest suitable abstraction, document non-obvious trade-offs, test correctness, profile the real workload, and revisit the decision when scale or concurrency changes.

Chapter Summary

Collection design begins with semantic requirements and dominant operations. Lists support positional sequences, sets enforce uniqueness, queues model processing order, and maps associate keys with values. ArrayList, hash-based collections, tree-based collections, deques, and priority queues offer different complexity, memory, ordering, and locality characteristics.

Correct use of collections depends on stable equality and hashing, suitable comparators, and immutable or carefully managed keys. Streams provide lazy, declarative pipelines, while collectors support grouping, partitioning, summarising, and safe reduction. External mutation within stream pipelines is error-prone, particularly in parallel execution. Parallel streams are beneficial only when workload size, independence, and overhead justify them.

Performance evaluation must consider time, memory, allocation, latency, throughput, and scalability. Complexity analysis guides design, but measurement with representative workloads validates decisions. The professional objective is not maximum theoretical speed; it is a correct, maintainable, appropriately scalable solution.

Key Terms

Collection: An object that represents a group of elements.

List: An ordered collection that generally permits duplicates.

Set: A collection intended to contain unique elements.

Map: A structure that associates keys with values.

Deque: A double-ended queue supporting operations at both ends.

Hashing: Transforming a value into a hash code used for efficient lookup.

Equality contract: Rules governing consistent value comparison through equals.

Comparator: An object defining an ordering between values.

Big-O notation: A description of asymptotic resource growth.

Amortised complexity: Average cost over a sequence of operations, including occasional expensive operations.

Stream: A pipeline abstraction for processing elements from a source.

Lazy operation: An operation whose processing is deferred until a terminal operation runs.

Collector: A reduction strategy that accumulates stream elements into a result.

Reduction: Combining multiple values into one result.

Side effect: Observable modification outside the local computation of an operation.

Immutability: A property whereby an object’s state cannot change after construction.

Parallel stream: A stream whose work may be divided among multiple threads.

Throughput: Completed work per unit of time.

Latency: Time required for an individual operation or request.

Cache locality: The performance benefit of accessing data located close together in memory.

Review Questions

Short Answer Questions

1. Why is ArrayList often preferred for indexed reads?
2. State the relationship required between equals and hashCode.
3. What is the difference between an intermediate and a terminal stream operation?
4. Why can modifying a collection during an enhanced for loop be unsafe?
5. Name two conditions under which a parallel stream may be inappropriate.

Long Answer Questions

1. Compare ArrayList, LinkedList, HashSet, and TreeSet in terms of operations, ordering, memory, and appropriate use cases.
2. Explain how groupingBy and downstream collectors can be used to create a departmental employee report.
3. Discuss equality, hashing, and comparator consistency in relation to HashSet and TreeSet.
4. Explain the causes of overhead in parallel streams and describe how performance should be measured.
5. Discuss how immutability and defensive copying improve the safety of collection-based APIs.

Analytical / Application Questions

1. An application repeatedly checks whether 500,000 user IDs have already been processed and must later display them in insertion order. Which collection would you select, and why?
2. A stream pipeline adds results to a shared ArrayList using parallelStream().forEach(...). Diagnose the risks and redesign the operation.
3. A financial reporting system groups transactions by account and sums amounts. Compare double and BigDecimal, and propose a collection and stream design that prioritises correctness and maintainability.

Multiple Choice Questions with Answers

Question 1

Which collection is generally most appropriate for frequent indexed reads and append operations?

A. ArrayList

B. TreeSet

C. PriorityQueue

D. HashMap

Correct Answer: A. ArrayList

Question 2

What is the typical average complexity of lookup in a well-designed HashMap?

A. O(n log n)

B. O(1)

C. O(n)

D. O(log n)

Correct Answer: B. O(1)

Question 3

Which operation is terminal in a stream pipeline?

A. filter

B. map

C. sorted

D. collect

Correct Answer: D. collect

Question 4

What is the principal risk of using a mutable key whose hash-relevant fields change after insertion into a HashMap?

A. The map becomes automatically sorted

B. The key may no longer be found correctly

C. The map converts into a TreeMap

D. All values are duplicated

Correct Answer: B. The key may no longer be found correctly

Question 5

Which collector is most directly suited to dividing elements into two groups based on a boolean predicate?

A. partitioningBy

B. joining

C. mapping

D. counting

Correct Answer: A. partitioningBy

Question 6

Why is adding elements to an ordinary ArrayList from a parallel stream unsafe?

A. ArrayList always rejects null values

B. Parallel streams cannot process lists

C. The list is not designed for unsynchronised concurrent mutation

D. The stream automatically sorts the list

Correct Answer: C. The list is not designed for unsynchronised concurrent mutation

Question 7

Which structure is designed to provide efficient retrieval of the highest-priority element?

A. PriorityQueue

B. LinkedHashSet

C. ArrayList

D. TreeMap

Correct Answer: A. PriorityQueue

Question 8

What does lazy evaluation mean in a stream pipeline?

A. The source is permanently copied before processing

B. Intermediate operations execute when a terminal operation is invoked

C. Every operation executes immediately in a new thread

D. The stream can be reused indefinitely

Correct Answer: B. Intermediate operations execute when a terminal operation is invoked

Question 9

Which statement about TreeSet is correct?

A. It provides sorted uniqueness according to natural ordering or a comparator

B. It guarantees insertion order and permits duplicates

C. It stores key-value pairs

D. It provides constant-time indexed access

Correct Answer: A. It provides sorted uniqueness according to natural ordering or a comparator

Question 10

Which factor is a valid reason to benchmark a collection design instead of relying only on Big-O notation?

A. Big-O always gives exact elapsed time

B. Hardware locality and allocation costs can affect real performance

C. Benchmarking makes equality contracts unnecessary

D. Complexity analysis applies only to databases

Correct Answer: B. Hardware locality and allocation costs can affect real performance