Collections in Java SpringBoot Roadmap

Every Spring Boot service moves its data through List, Set and Map, and a wrong collection choice is behind most slow service code. This is Week 1 of the Spring Boot roadmap, so we start here, before annotations, starters or REST controllers.

The article assumes you already know the C++ STL. It maps each STL container to its Java equivalent, then covers boxing, the basic API, iteration, one practice problem per structure, records, concurrent collections, and finally how HashMap and ArrayList work inside.

From STL to Java collections

Each STL container has a direct Java counterpart, with a few differences in naming and defaults.

Two things differ from C++ right away. First, List, Set, Map, Queue and Deque are interfaces, so you declare the interface and pick the implementation on the right:

List<Integer> numbers = new ArrayList<>();
Map<String, Integer> counts = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>();

Second, PriorityQueue pops the smallest element first. For a max-heap, pass a comparator: new PriorityQueue<>(Comparator.reverseOrder()).

Collections store objects, not primitives

Java collections hold objects only, so the type parameter must be a wrapper class: ArrayList<Integer>, not ArrayList<int>, and HashMap<Long, String>, not HashMap<long, String>.

Java converts between the two automatically. Putting an int into a collection is autoboxing; reading it back into an int is unboxing.

List<Integer> numbers = new ArrayList<>();
numbers.add(10);
numbers.add(20);

// Integer is automatically converted to int (unboxing)
int first = numbers.get(0);

Three pitfalls catch C++ developers:

• Null unboxing. map.get(key) returns null for a missing key, and assigning that to an int throws NullPointerException. Use map.getOrDefault(key, 0).
• == compares references. For Integer values, use .equals(). == appears to work for small values (the JVM caches -128 to 127) and fails above that.
• list.remove(int) vs list.remove(Object). On a List<Integer>, remove(1) removes the element at index 1. To remove the value 1, call remove(Integer.valueOf(1)).

Every boxed value is a separate heap object, so a List<Integer> of a million numbers uses far more memory than an int[]. Keep that in mind in hot paths.

The basic API: initialize, populate, access

These are the calls you will use daily, grouped by structure. Think of them as the Java equivalents of the STL member functions.

List (ArrayList, LinkedList)

List<Integer> list = new ArrayList<>();
List<Integer> fixed = List.of(1, 2, 3);                 // immutable
List<Integer> copy  = new ArrayList<>(fixed);           // mutable copy

list.add(10);            // push_back
list.add(0, 5);          // insert at index
list.set(1, 99);         // overwrite at index
int x = list.get(0);     // operator[]
list.remove(0);          // erase by index
list.contains(99);       // O(n) search
list.size();
list.isEmpty();
Collections.sort(list);  // std::sort

Set (HashSet, TreeSet)

Set<String> seen = new HashSet<>();
seen.add("a");                       // returns false if already present
seen.contains("a");
seen.remove("a");

TreeSet<Integer> sorted = new TreeSet<>(List.of(5, 1, 3));
sorted.first();      // smallest
sorted.last();       // largest
sorted.floor(4);     // greatest element <= 4
sorted.ceiling(4);   // smallest element >= 4

Map (HashMap, TreeMap)

Map<String, Integer> freq = new HashMap<>();
freq.put("a", 1);
freq.get("a");                              // null if missing
freq.getOrDefault("b", 0);
freq.containsKey("a");
freq.merge("a", 1, Integer::sum);           // freq["a"]++ in one call
freq.putIfAbsent("c", 0);
freq.remove("a");

Unlike C++, map[key] never inserts a default value in Java. get returns null, so use getOrDefault or merge.

Queue, Deque and PriorityQueue

Queue<Integer> q = new ArrayDeque<>();
q.offer(1);      // push
q.peek();        // front, null if empty
q.poll();        // pop front, null if empty

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);   // add to front
stack.peek();    // top
stack.pop();     // remove top

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.poll();       // 1, the smallest

poll and peek return null on an empty queue, while remove and element throw. Prefer poll and peek unless an empty queue is a bug.

Iterating in Java

Java offers five common ways to loop over a collection; the enhanced for loop covers most cases.

List<String> names = List.of("Asha", "Ben", "Chen");

// 1. Enhanced for (like C++ range-based for)
for (String n : names) {
    System.out.println(n);
}

// 2. Indexed loop (Lists only)
for (int i = 0; i < names.size(); i++) {
    System.out.println(names.get(i));
}

// 3. Iterator (needed when removing while looping)
Iterator<String> it = new ArrayList<>(names).iterator();
while (it.hasNext()) {
    String n = it.next();
    if (n.startsWith("B")) it.remove();
}

// 4. forEach with a lambda
names.forEach(n -> System.out.println(n));

// 5. Streams (transform, filter, collect)
List<String> upper = names.stream().map(String::toUpperCase).toList();

Iterating a Map

A Map is not Iterable, so you iterate one of its views: entrySet(), keySet() or values().

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

freq.forEach((k, v) -> System.out.println(k + " -> " + v));

Loop over entrySet() rather than keySet() followed by get(key); it avoids a second lookup per key.

Fail-fast iterators

If you modify a collection while looping over it, the iterator throws ConcurrentModificationException. This is the fail-fast behavior, and the usual cause is calling list.remove(x) inside an enhanced for loop.

for (String n : list) {
    if (n.isEmpty()) list.remove(n);   // throws ConcurrentModificationException
}

list.removeIf(String::isEmpty);        // correct and shorter

Use Iterator.remove() or removeIf instead. Fail-fast is a best-effort bug detector, not a thread-safety guarantee, which is why concurrent collections exist (see below).

Practice: one LeetCode problem per collection

Solve each problem in Java, not C++. The goal is not the algorithm but the muscle memory: initialize the structure, populate it, traverse it, and use its built-in methods the way you use the STL.

A starting point for the HashMap problem, to compare with your C++ version:

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> index
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) {
            return new int[] { seen.get(need), i };
        }
        seen.put(nums[i], i);                        // int autoboxed to Integer
    }
    return new int[0];
}

Records

A record is a compact class for immutable data, and it became a permanent Java feature in Java 16 (JEP 395). It appeared as a preview in Java 14 and again in Java 15, so you need Java 16 or later to use it without flags. Spring Boot 3 requires Java 17, so records are always available in modern Spring projects.

One line replaces what used to be a class with fields, a constructor, getters, equals, hashCode and toString:

public record User(long id, String name, String email) { }

User u = new User(1L, "Asha", "[email protected]");
u.name();        // accessor is name(), not getName()
System.out.println(u);   // User[id=1, name=Asha, [email protected]]

Features

• Immutable. Every component becomes a private final field, and there are no setters.
• Generated members. The compiler adds the canonical constructor, one accessor per component, and equals, hashCode and toString based on all components.
• Implicitly final. A record cannot extend another class and cannot be extended. It can implement interfaces.
• Compact constructor for validation without repeating the assignments:

public record Range(int low, int high) {
    public Range {
        if (low > high) throw new IllegalArgumentException("low > high");
    }
}

• Extra members allowed. You can add static fields, static methods and instance methods, but no additional instance fields.
• Safe as collection keys. Value-based equals and hashCode make records good HashMap keys and HashSet elements.

Where you will use them

In Spring Boot, records are a natural fit for request and response DTOs, query results and small value objects. They are not a fit for JPA entities, which need a no-argument constructor and mutable state.

Concurrent collections: know the names

The collection family most beginners overlook is the concurrent one. A Spring Boot service handles many requests on many threads at once, so any shared map or list is accessed concurrently, and a plain HashMap is not safe for unsynchronized concurrent mutation. Concurrent writes can lose updates or corrupt its structure.

Know these four names now; you do not need to master them today.

The usual upgrade path is small:

Map<String, Integer> hits = new ConcurrentHashMap<>();
hits.merge("/home", 1, Integer::sum);   // atomic increment

Collections.synchronizedMap(...) also exists, but it locks every operation, and iterating over it still needs manual synchronization. Prefer the java.util.concurrent classes.

Week 1 deep dive: how collections work inside

Knowing the internals tells you which collection to pick and explains the performance surprises. Learn these four topics this week.

HashMap: buckets, resize, treeification

HashMap stores entries in an array of buckets. To place a key, Java computes hashCode(), mixes the high bits into the low bits, and takes the result modulo the table size to pick a bucket. The table size is always a power of two, so the modulo is a bit mask.

• Collisions. Keys that land in the same bucket are chained in a linked list, and equals() decides which node is the match. This is why a key class must override equals and hashCode together.
• Resize. The default capacity is 16 and the default load factor is 0.75. When the entry count passes capacity times load factor (12 at the start), the table doubles and every entry is redistributed.
• Treeification. Since Java 8, a bucket with 8 or more entries is converted from a linked list to a red-black tree, but only when the table has at least 64 buckets; below that the map resizes instead. This caps the worst case at O(log n). Trees shrink back to lists when a bucket falls to 6 entries or fewer.
• Practical rules. Never use a mutable object as a key if its hash changes. If you know the size up front, pass an initial capacity to avoid repeated resizes.

HashSet is a thin wrapper: it is a HashMap where each element is a key with a dummy value, so it has the same behavior and the same rules.

ArrayList vs LinkedList

ArrayList wraps an Object[]. When it fills, it allocates a new array about 1.5 times larger and copies the elements, so appends are amortized O(1). Reading by index is O(1), while inserting or removing in the middle shifts elements, which is O(n).

LinkedList is a chain of nodes with previous and next links. Adding or removing at either end is O(1), but get(i) walks the chain from the nearest end, which is O(n). Each element also costs an extra node object, so memory use and cache misses are higher.

Default to ArrayList. Even for inserts in the middle it often wins on real hardware because arrays are contiguous in memory. For a queue or stack, use ArrayDeque, which is usually faster than LinkedList.

TreeMap and TreeSet

TreeMap is a red-black tree that keeps keys sorted by natural order or by a Comparator you pass in. Every operation is O(log n), and you gain navigation methods such as floorKey, ceilingKey, headMap, tailMap and firstEntry. TreeSet is backed by a TreeMap the same way HashSet is backed by a HashMap. Choose a tree only when you need sorted order or range queries; otherwise HashMap is faster.

Fail-fast iterators

Every ArrayList, HashMap and similar class keeps a modification counter, modCount, that increases on each structural change. An iterator records the value when it is created and compares it on every next(). A mismatch throws ConcurrentModificationException. The check is best effort and not a thread-safety mechanism, and concurrent collections use weakly consistent iterators instead, which never throw it.

Complexity at a glance

Practical tasks

Two exercises turn the theory into something you have measured yourself. Both are beginner level (S1).

• Write a toy HashMap with put, get and automatic resizing
• Benchmark ArrayList against LinkedList on large workloads
• Solve the nine LeetCode problems from the practice table

Task 1: a toy HashMap

Implement separate chaining with an array of buckets, a power-of-two table and a 0.75 load factor. This skeleton covers put, get and resize; adding remove and containsKey is a good stretch goal, and treeification can be skipped.

import java.util.Objects;

public class ToyHashMap<K, V> {

    private static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;
        Node(K key, V value, Node<K, V> next) {
            this.key = key; this.value = value; this.next = next;
        }
    }

    private static final double LOAD_FACTOR = 0.75;
    private Node<K, V>[] table;
    private int size;

    @SuppressWarnings("unchecked")
    public ToyHashMap() {
        table = (Node<K, V>[]) new Node[16];
    }

    private int indexFor(Object key, int length) {
        int h = (key == null) ? 0 : key.hashCode();
        h ^= (h >>> 16);              // mix high bits into low bits
        return h & (length - 1);      // length is a power of two
    }

    public V get(K key) {
        for (Node<K, V> n = table[indexFor(key, table.length)]; n != null; n = n.next) {
            if (Objects.equals(n.key, key)) return n.value;
        }
        return null;
    }

    public V put(K key, V value) {
        int i = indexFor(key, table.length);
        for (Node<K, V> n = table[i]; n != null; n = n.next) {
            if (Objects.equals(n.key, key)) {
                V old = n.value;
                n.value = value;
                return old;
            }
        }
        table[i] = new Node<>(key, value, table[i]);
        if (++size > table.length * LOAD_FACTOR) resize();
        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        Node<K, V>[] bigger = (Node<K, V>[]) new Node[table.length * 2];
        for (Node<K, V> head : table) {
            Node<K, V> n = head;
            while (n != null) {
                Node<K, V> next = n.next;
                int i = indexFor(n.key, bigger.length);
                n.next = bigger[i];
                bigger[i] = n;
                n = next;
            }
        }
        table = bigger;
    }

    public int size() { return size; }
}

Test it against the real thing: insert a million random keys into both ToyHashMap and java.util.HashMap, then assert that every get returns the same value. Then write a key class with a deliberately bad hashCode (always return 1) and watch the toy map slow down; that is what treeification protects against.

Task 2: ArrayList vs LinkedList benchmark

Time the same operations on both lists and write the results in a table. Use System.nanoTime() and repeat each run several times, because the JIT compiler makes the first runs unrepresentative. For serious measurements, use JMH.

static long millis(Runnable r) {
    long start = System.nanoTime();
    r.run();
    return (System.nanoTime() - start) / 1_000_000;
}

Scale the counts down where one structure becomes impractically slow; that gap is the finding. Add ArrayDeque to the front-insertion test with addFirst and compare it with both lists.

Cheat sheet: which collection do I pick?

Start from what you need, not from what you know.

By the end of Week 1 you should be able to declare any of these without looking anything up, loop over it three different ways, explain why HashMap resizes and treeifies, and say why LinkedList is rarely the right answer. That vocabulary is what the rest of the Spring Boot roadmap builds on.