Collections

Every real backend you’ll ever touch is, at its core, moving groups of things around: a list of transactions, a set of user IDs, a map of UPI handles to balances. Arrays can’t keep up with that job. Collections are the data structures you’ll use in literally every Java file you write at work — and HashMap internals is one of the most asked Java interview questions in India.

The Goal

By the end of this module you can:

• Explain why arrays fall short and what the Collection family gives you instead
• Use ArrayList, HashSet, and HashMap fluently, and say what each is for in one sentence
• Describe how a HashMap finds a value — hash, bucket, equals — well enough to survive the interview question
• Read a Big-O claim like “contains is O of n” and know what it means for real performance
• Choose the right collection for a problem instead of defaulting to ArrayList for everything

The Lesson

Why arrays are not enough

You know arrays from module 02. Here’s where they hurt:

String[] expenses = new String[5];   // fixed size, forever

• Fixed size. Sixth expense? Create a bigger array, copy everything over, by hand.
• No remove. Deleting index 2 means manually shifting everything after it.
• No “does this exist?” You write the search loop yourself, every time.
• No key-value lookup. “What’s Ravi’s balance?” forces a scan of the whole array.

Collections are classes that do all of this for you — growing, shifting, searching — battle-tested for 25 years.

The family tree

Java’s collections are organized as interfaces (the contracts — module 03 paying off already) with multiple implementations each:

flowchart TD
    C[Collection] --> L[List - ordered - duplicates ok]
    C --> S[Set - no duplicates]
    L --> AL[ArrayList]
    L --> LL[LinkedList]
    S --> HS[HashSet]
    M[Map - key value pairs - separate family] --> HM[HashMap]

Note Map is drawn separately — it’s technically not a Collection, but everyone discusses them together because you use them together.

You declare the interface type and instantiate the implementation:

List<String> names = new ArrayList<>();   // contract on the left, engine on the right

Why? Same reason as module 03: code that depends on List doesn’t care which engine is underneath, so you can swap engines later without rewriting callers.

ArrayList — the workhorse

An ArrayList is an array that resizes itself:

import java.util.ArrayList;
import java.util.List;

public class Expenses {
    public static void main(String[] args) {
        List<Integer> expenses = new ArrayList<>();
        expenses.add(250);          // chai and samosa run
        expenses.add(1200);         // electricity bill
        expenses.add(250);          // duplicates are fine in a List
        expenses.remove(Integer.valueOf(1200));     // remove by value, not index
        System.out.println(expenses.get(0));        // indexed access: 250
        System.out.println(expenses.size());        // 2
        System.out.println(expenses.contains(250)); // true
    }
}

How it grows internally — a favorite interview follow-up. Inside, there’s a plain array (default capacity 10). When you add the 11th element, the ArrayList creates a new array roughly 1.5x bigger and copies everything across. That copy is occasionally expensive, but it happens rarely enough that adding stays cheap on average.

flowchart LR
    A[Internal array full at capacity 10] --> B[Allocate new array at capacity 15]
    B --> C[Copy all 10 elements over]
    C --> D[Add element 11]

get(i) is instant — it’s array math under the hood, jump straight to the slot. That’s the superpower of ArrayList: fast indexed access.

The <Integer> in angle brackets is generics — telling the compiler “this list holds Integers only,” so it stops you putting a String in at compile time. One line of theory for now; you’ll absorb the rest by using it.

LinkedList — exists, rarely wins

LinkedList stores elements as a chain of nodes, each pointing to the next. Textbooks say it’s “fast for insertion in the middle.” Honest reality:

• get(i) means walking the chain from the start — slow.
• Each node is a separate object scattered across memory, which modern CPUs hate; they’re optimized for data sitting side by side, which is exactly what ArrayList’s internal array is.
• In real benchmarks, ArrayList wins almost every realistic workload, including many “insert in the middle” cases.

Know it exists, be able to say why it loses, default to ArrayList. If an interviewer pushes, the honest senior answer: “I’d reach for LinkedList only with a measured reason — and I’ve never had one.”

HashSet — no duplicates, fast contains

A Set has one job: hold each thing at most once.

import java.util.HashSet;
import java.util.Set;

public class UpiHandles {
    public static void main(String[] args) {
        Set<String> handles = new HashSet<>();
        System.out.println(handles.add("darshan@upi"));    // true — added
        System.out.println(handles.add("ravi@upi"));       // true — added
        System.out.println(handles.add("darshan@upi"));    // false — already there, ignored
        System.out.println(handles.size());                // 2
        System.out.println(handles.contains("ravi@upi"));  // true — and FAST
    }
}

Two things to internalize:

1. add returns false if the element was already present — a free “have I seen this before?” check. The Build This exercise leans on exactly this.
2. contains is fast regardless of size — membership in 10 elements or 10 million costs roughly the same. A List’s contains scans every element one by one. That difference is the Big-O section below.

One warning: a HashSet has no order. Iterate it and elements come out in whatever order the hashing decided. Need order? Other implementations exist — later module.

HashMap internals — THE interview classic

A Map stores key to value pairs:

import java.util.HashMap;
import java.util.Map;

public class Balances {
    public static void main(String[] args) {
        Map<String, Integer> balances = new HashMap<>();
        balances.put("darshan@upi", 5000);
        balances.put("ravi@upi", 12000);
        balances.put("darshan@upi", 4500);   // same key — value REPLACED, not duplicated

        System.out.println(balances.get("darshan@upi"));          // 4500
        System.out.println(balances.getOrDefault("priya@upi", 0)); // 0 — safe default for missing keys
        System.out.println(balances.containsKey("ravi@upi"));     // true
    }
}

Now the part interviewers actually ask: how does get find the value without scanning everything?

Inside, a HashMap is an array of buckets. The journey of balances.get("ravi@upi"):

1. Call hashCode() on the key — gives a number, say 83214041.
2. Squash that number into a bucket index — roughly hash mod array length — say bucket 6.
3. Jump straight to bucket 6. No scanning, no searching.
4. Two different keys can land in the same bucket (a collision), so a bucket holds a short chain of entries. Walk that chain, using equals() to find the exact key.
5. Return that entry’s value.

flowchart TD
    K[Key ravi at upi] --> H[hashCode gives a number]
    H --> B[Number mod array length gives bucket 6]
    B --> J[Jump straight to bucket 6]
    J --> E{equals check on each entry in the bucket}
    E --> V[Match found - return 12000]
    E --> N[No match - return null]

This is why module 03’s rule exists: equal objects must have equal hash codes. Break it, and your key hashes to bucket 6 on put but you search bucket 3 on get — the entry is there, and you can never find it. The map looks like it’s losing data. It isn’t; your hashCode is lying.

Say “hash to bucket, then equals within the bucket” in an interview and you’re ahead of most freshers.

A first taste of Big-O

Big-O answers one question: when the data gets 1000x bigger, does the operation get 1000x slower — or stay the same? No math needed yet; just two shapes:

• O(1) — constant. Same speed at any size. Jumping to a slot.
• O(n) — linear. Doubles when data doubles. Scanning everything.

The practical takeaway: if your code calls list.contains inside a loop over another big list, you’ve built an O(n squared) bomb — fine in testing with 50 rows, 30-second page loads in production with 50,000. Swapping that inner list for a HashSet is one of the most common real-world performance fixes there is. This table is a seed; the DSA track waters it — start with Arrays & Hashing, which is this exact fix taught as a pattern.

Iteration — and the trap

For-each works on every collection:

for (String handle : handles) {
    System.out.println(handle);
}

// Maps iterate over entries:
for (Map.Entry<String, Integer> entry : balances.entrySet()) {
    System.out.println(entry.getKey() + " has " + entry.getValue() + " rupees");
}

Now the trap every Java developer hits exactly once:

List<Integer> amounts = new ArrayList<>(List.of(100, 250, 990, 50));
for (Integer amount : amounts) {
    if (amount < 200) {
        amounts.remove(amount);   // BOOM — ConcurrentModificationException
    }
}

You cannot structurally change a collection while for-each is walking it — the iterator notices the collection shifted under its feet and throws, on purpose, because continuing would give garbage results. The modern fix is one line:

amounts.removeIf(amount -> amount < 200);   // safe, and clearer about intent

(That arrow is a lambda — “for each amount, is it under 200?” Full lambda treatment in a later module; for now just read it as the removal condition.)

Quick wins you’ll use constantly

A few small tools that show up in everyday work:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class QuickWins {
    public static void main(String[] args) {
        // List.of makes a fixed, read-only list — great for test data.
        // Wrap it in ArrayList when you need to modify it.
        List<Integer> amounts = new ArrayList<>(List.of(990, 50, 250, 100));

        Collections.sort(amounts);                       // in-place sort: 50 100 250 990
        System.out.println(Collections.max(amounts));    // 990
        System.out.println(Collections.min(amounts));    // 50
        System.out.println(amounts.isEmpty());           // false
    }
}

One trap inside the trap: List.of(...) returns an immutable list. Call add or remove on it directly and you get UnsupportedOperationException. That’s why the snippet wraps it in new ArrayList<>(...) — copy first, then modify. You will hit this within your first week of real Java; now you’ll recognize it.

And one honest note on ordering: HashSet and HashMap trade away order to get their speed. When you genuinely need sorted or insertion-ordered versions, Java has implementations for that too — they cost a little speed for the ordering. Parked for a later module; today’s three (ArrayList, HashSet, HashMap) cover 90 percent of real code.

How to choose — the decision tree

flowchart TD
    Q1{Do you look things up by a key} -->|yes| HM[HashMap]
    Q1 -->|no| Q2{Must duplicates be impossible}
    Q2 -->|yes| HS[HashSet]
    Q2 -->|no| Q3{Does order or index position matter}
    Q3 -->|yes| AL[ArrayList]
    Q3 -->|no| Q4{Will you call contains on it a lot}
    Q4 -->|yes| HS2[HashSet]
    Q4 -->|no| AL2[ArrayList]

Three questions, in order: lookup by key? uniqueness? order? Default to ArrayList only when nothing else claims the job — not as a reflex.

Build This

Two small terminal tools, both solving problems collections were born for.

1. Create a folder collections-practice. Inside it, create WordFrequency.java.
2. Build a word-frequency counter: read one full line with Scanner, lowercase it, split into words with sentence.split(" "), then loop the words building a Map<String, Integer> where each word maps to its count. The key move: counts.put(word, counts.getOrDefault(word, 0) + 1);. Print every entry by iterating entrySet().
3. Compile and run from a plain terminal:

   javac WordFrequency.java
   java WordFrequency
   

   Feed it: the quick brown fox jumps over the lazy dog the end — verify the shows 3.
4. Now create DuplicateExpenses.java. Hardcode an array of expense descriptions with sneaky duplicates: {"chai 20", "auto 150", "lunch 180", "chai 20", "recharge 299", "auto 150"}.
5. Loop the array adding each into a HashSet<String>. When add returns false, print that entry as a duplicate expense — a double-spend caught in one pass.
6. Compile, run, confirm it flags exactly chai 20 and auto 150.
7. Break it on purpose: in WordFrequency, swap getOrDefault for plain get and watch the NullPointerException on the first new word. Understand why, then put it back.

Where to Practice

How to Practice

• Type every line yourself. Never copy-paste — especially the getOrDefault pattern; it needs to live in your fingers.
• Time-box: 25 minutes building, 5 minutes reading.
• Break it on purpose: trigger the ConcurrentModificationException yourself, read the stack trace top to bottom, then fix it with removeIf.
• Re-explain the HashMap get journey from memory at the start of your next session. If it’s gone, re-draw the diagram by hand.

Check Yourself

1. Name three things collections give you that plain arrays don’t.
2. What happens inside an ArrayList when you add an element beyond its capacity?
3. Why does ArrayList beat LinkedList in most real workloads?
4. Walk through the full journey of map.get("ravi@upi") — every step.
5. What’s a hash collision, and how does HashMap deal with it?
6. Why is set.contains O(1) but list.contains O(n), and when does that difference actually hurt?
7. What exception do you get removing from a list inside a for-each loop, and what’s the clean fix?
8. You need to store unique visitor IDs and check membership millions of times. Which collection, and why?

Explain it out loud: explain to an imaginary interviewer how a HashMap retrieves a value, including what happens on a collision and why equals and hashCode must agree. Two minutes, no notes.

Still Unclear?

Copy-paste any of these into Claude:

• “Walk me through what physically happens in memory when I put three entries into a HashMap where two keys collide into the same bucket. Draw the bucket array as ASCII art at each step.”
• “Show me a small runnable Java program where using list.contains inside a loop is visibly slow with 100000 elements, then the same program with a HashSet. Print the timing difference and explain it in Big-O terms.”
• “I don’t fully get why removing from a list during a for-each throws ConcurrentModificationException. Show me what the iterator is tracking internally and exactly which line trips the alarm.”

Why AI Can’t Do This For You

AI will pick a collection for you — usually ArrayList, usually without thinking. It won’t be in the room when the page that was instant in dev takes 30 seconds with production data, and the fix is knowing that an O(n) contains inside a loop should have been a HashSet from day one. Choosing data structures for data you haven’t seen yet is judgment. The HashMap interview question exists precisely to separate people with that judgment from people who prompt for it.

Module done? Add it to today’s tracker