IAE Academy

FOR CORE AND IT JOBS · CHAPTER 6 OF 7

Collections and generics

This chapter explains generics, the List, Set and Map families and their costs, safe looping, equals and hashCode for keys, and sorting. You need it to choose the right container and to avoid silent lookup failures.

Updated 30 Oct 2026

What you will be able to do

You will pick between List, Set and Map, and the class whose costs fit the job. You will loop over a collection without a ConcurrentModificationException. You will make an object a working HashMap key, sort with Comparable and Comparator, and count word frequencies.

Before you start

  1. Chapter 4, Polymorphism, abstract classes and interfaces

  2. Reading O(1), O(log n) and O(n) as how the number of steps grows with n

  3. Powers of 2 and their sum, logarithms to base 2, and remainders (mod)

Generics and the collection family

A raw List holds plain Object references: raw.add(2) compiles (with a warning), and (String) raw.get(0) then throws ClassCastException at run time. List<String> says every element is a String: the compiler rejects names.add(2) and adds the cast on each read, so the bug surfaces at compile time. In new ArrayList<>() the diamond <> copies the type from the left. Java 17 is assumed throughout.

Collection is the interface that List and Set extend. A List keeps elements by index and allows duplicates; a Set holds no two equal elements. A Map holds unique keys, one value each; it is not a Collection but belongs to the same family.

Hash classes put each key (a set's element) in a bucket, a slot of an internal array picked from the key, and promise no order. Tree classes keep keys sorted in a balanced binary tree: each entry has at most two children, and the height stays near its least possible value. ArrayList keeps an array, so get(i) is one step; adding at the end is amortised O(1), as the array is only now and then copied into a bigger one. LinkedList keeps nodes, each an element linked to its two neighbours: it adds and removes in O(1) only at an end or an iterator's position, and walks the nodes to reach an index or a value. Hash costs below are averages; a map's get and contains are get(key) and containsKey.

COST OF REMOVING FROM AN ARRAYLIST BY INDEX

Holds for an ArrayList of n elements and an index : each element after i slides one place left. moves counts elements.

SMALLEST HEIGHT OF A BINARY TREE HOLDING N ENTRIES

Holds for any binary tree, h counting levels from the root. Level k holds at most entries, so h levels hold at most . TreeSet and TreeMap keep h within twice this bound, so a lookup walks one root-to-leaf path: O(log n).

Class

get

add/put

remove

contains

ArrayList

O(1)

O(1) at the end

O(n)

O(n)

LinkedList

O(n)

O(1) at an end

O(1) at an end

O(n)

HashSet

none

O(1)

O(1)

O(1)

TreeSet

none

O(log n)

O(log n)

O(log n)

HashMap

O(1)

O(1)

O(1)

O(1)

TreeMap

O(log n)

O(log n)

O(log n)

O(log n)

WORKED EXAMPLE

An ArrayList holds n = 1000 elements. How many elements move when you remove the element at index 0, at index 900 and at index 999?

Solution
  1. Every element after index i slides one place left to close the gap, so the count is n - 1 - i.

  2. Index 0: 1000 - 1 - 0 = 999 moves, since all other elements follow it.

  3. Index 900: 1000 - 1 - 900 = 99 moves.

  4. Index 999: 1000 - 1 - 999 = 0 moves, since nothing follows the last element.

Answer: 999, 99 and 0 element moves. The nearer the front, the dearer the removal.

Iteration, equality and hashing

A for-each loop over a collection runs on an Iterator (hasNext(), next()). An ArrayList counts its adds and removes; an iterator records the count when created, and next() throws ConcurrentModificationException if it changed. The check is best effort: a bug alarm, not program logic. Iterator.remove() updates the record, so it deletes safely. List.of(...) makes a fixed list, copied here into an ArrayList.

import java.util.*;

public class RemoveDemo {
    public static void main(String[] args) {
        List<Integer> b = new ArrayList<>(List.of(1, 2, 3, 4));
        for (Iterator<Integer> it = b.iterator(); it.hasNext(); )
            if (it.next() == 2) it.remove();
        System.out.println(b); // [1, 3, 4]
        for (Integer x : b) if (x == 1) b.remove(x); // throws ConcurrentModificationException
    }
}

A HashMap keeps an array of m buckets. Each bucket holds a chain: the entries whose keys landed there, one after another. A lookup picks the bucket from hashCode, then walks its chain, calling equals only on entries with the same hash code. So equal keys with different hash codes never meet equals, and the lookup fails.

BUCKET INDEX

Holds for a HashMap, which keeps m, the number of buckets, a power of two (16 when new), and for a hash code , where its extra bit mixing changes nothing. i is the bucket, .

STEPS TO FIND A KEY

Holds on average when hashCode spreads n entries evenly over m buckets: a chain then holds n/m entries on average, so one step reaches the bucket and up to about n/m comparisons follow. HashMap doubles m once n/m passes 0.75, keeping this O(1). If all keys share one bucket, a lookup can cost up to O(n).

THE EQUALS AND HASHCODE CONTRACT

Holds for any two objects a and b. Equal objects must give equal hash codes, so they reach one bucket. Unequal objects may share a hash code. Override both, from the same fields.

o instanceof Point p tests the type and names the cast result p.

import java.util.*;

public class Point {
    final int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
    @Override public boolean equals(Object o) {
        return o instanceof Point p && p.x == x && p.y == y;
    }
    @Override public int hashCode() { return Objects.hash(x, y); }
    public static void main(String[] args) {
        Map<Point, String> m = new HashMap<>();
        m.put(new Point(1, 2), "A");
        System.out.println(m.get(new Point(1, 2))); // A
    }
}

Remove hashCode and the two points normally get different identity-based hash codes, so get prints null.

WATCH OUT FOR

Writing equals(Point p) overloads equals instead of overriding it, and HashMap never calls it. Test: put @Override on the method. If it is not an override, the compiler refuses.

WORKED EXAMPLE

A HashMap has 16 buckets. You put "Aa" (value 1), then "BB" (value 2), then call get("BB"). A two-character string's hashCode is s[0]·31 + s[1], with character codes A = 65, B = 66, a = 97. Which bucket is used, and how many stored keys does get check?

Solution
  1. Hash of "Aa": 65 · 31 + 97 = 2015 + 97 = 2112. Hash of "BB": 66 · 31 + 66 = 2046 + 66 = 2112. They are equal.

  2. 2112 lies between 0 and 65536, so the bucket formula applies: i = 2112 mod 16 = 0, since 16 · 132 = 2112. Both keys use bucket 0.

  3. put("BB") meets "Aa" in bucket 0 with the same hash, so equals runs, returns false, and "BB" joins the chain after "Aa".

  4. get("BB") walks bucket 0's chain in order: "Aa" (same hash, not equal), then "BB" (equal), and returns 2: 2 keys checked.

Answer: Bucket 0, with 2 keys checked. Equal hash codes only choose the bucket. equals decides which entry is the key.

Ordering and the word counter

A class gets one natural order by implementing Comparable: compareTo is negative if this goes first, zero if tied, positive if it goes second. A Comparator is a separate object supplying another order. TreeSet and TreeMap use either, and treat two keys as the same when the comparison gives zero, not when equals does.

COMPARATOR CONTRACT

Holds for any objects x and y that c compares; c(x, y) is signed like compareTo, and sign gives +1, 0 or -1. c must also be transitive: c(x, y) > 0 and c(y, z) > 0 give c(x, z) > 0. Break a rule and a sort can misorder or throw.

import java.util.*;

public class SortDemo {
    record Student(String name, int score) implements Comparable<Student> {
        public int compareTo(Student o) { return Integer.compare(score, o.score); }
    }
    public static void main(String[] args) {
        List<Student> list = new ArrayList<>(List.of(
            new Student("Asha", 70), new Student("Ravi", 55), new Student("Mita", 70)));
        Collections.sort(list);
        for (Student s : list) System.out.print(s.name() + " "); // Ravi Asha Mita
    }
}

A record is a class with fixed fields and generated accessors such as name(). Collections.sort orders by compareTo and is stable: equal elements keep their order, so Asha, first in the list, stays before Mita.

WATCH OUT FOR

Writing compare as a - b can overflow. Test: try a = Integer.MAX_VALUE, b = -1. a is larger, yet a - b comes out negative. Integer.compare(a, b) never subtracts.

split("[^a-z]+") cuts the text at each run of characters other than a to z. merge(w, 1, Integer::sum) stores 1 for a new word, else adds 1, with Integer::sum passing the method that adds two ints. entrySet() gives the pairs as Map.Entry objects (getKey(), getValue()). The Comparator is a lambda, a short function written inline as (a, b) -> {...}: larger count first, ties alphabetical.

import java.util.*;

public class WordCount {
    public static void main(String[] args) {
        String text = "The cat saw the dog. The dog ran!";
        Map<String, Integer> counts = new HashMap<>();
        for (String w : text.toLowerCase().split("[^a-z]+"))
            if (!w.isEmpty()) counts.merge(w, 1, Integer::sum);
        List<Map.Entry<String, Integer>> es = new ArrayList<>(counts.entrySet());
        es.sort((a, b) -> {
            int c = Integer.compare(b.getValue(), a.getValue());
            return c != 0 ? c : a.getKey().compareTo(b.getKey());
        });
        for (Map.Entry<String, Integer> e : es)
            System.out.println(e.getKey() + " " + e.getValue());
    }
}
// Output, one line each: the 3, dog 2, cat 1, ran 1, saw 1

Check yourself

CHECK YOURSELF 1

Why is List<String> names = new ArrayList<>(); better than a raw List names = new ArrayList();?

  1. (A)

    It runs faster.

  2. (B)

    A non-String add fails to compile, and reads need no cast.

  3. (C)

    It can store int values directly.

  4. (D)

    It rejects duplicates.

Answer and solution

Answer: (B)

  1. The type parameter lets the compiler check every add and insert the cast on every read.

  2. It does not change speed, allow primitives, or remove duplicates, so only B is true.

CHECK YOURSELF 2One or more options are correct

Which operations run in O(1) time on average for a list or set of n elements?

  1. (A)

    ArrayList.get(i)

  2. (B)

    LinkedList.get(i)

  3. (C)

    HashSet.contains(x), with well-spread hash codes

  4. (D)

    TreeSet.contains(x)

Answer and solution

Answer: (A), (C)

  1. ArrayList reads an array slot directly: O(1).

  2. LinkedList walks nodes: O(n).

  3. HashSet goes to one bucket: O(1) on average.

  4. TreeSet walks one path of a balanced tree: O(log n).

CHECK YOURSELF 3

An ArrayList holds 500 elements. How many elements move when you remove the one at index 120?

Answer and solution

Answer:

  1. Elements after index i slide left, so moves = n - 1 - i.

  2. 500 - 1 - 120 = 379.

CHECK YOURSELF 4

Point overrides equals (comparing x and y) but not hashCode. After m.put(new Point(1, 2), "A"), what does m.get(new Point(1, 2)) on that HashMap most likely return?

  1. (A)

    "A", always.

  2. (B)

    null, almost always: the hash codes normally differ.

  3. (C)

    An exception, always.

  4. (D)

    null, always, by the language rules.

Answer and solution

Answer: (B)

  1. Without an override, hashCode is identity-based, and two different Point objects normally get different hash codes.

  2. HashMap compares hash codes before it calls equals, so equals is normally never reached and get returns null.

  3. Two identity hash codes can be equal by chance, and then the entry is found, so 'always' is wrong and B is correct.

Used in these GATE topics