Java Toolkit & Collections: guided lesson

the story

The Collections Framework

Every tool here exists because something was too slow or broke without it. Here is what.

1998 · Joshua Bloch (design lead) and the JDK team at Sun Microsystems

Early Java had arrays, Vector and Hashtable, with no shared interface between them. JDK 1.2 (renamed Java 2, shipped December 1998) added the Collections Framework: interfaces like List, Set and Map, plus ready-made implementations behind them. Joshua Bloch led its design. The old Vector and Hashtable were retrofitted to fit the new interfaces.

the problem it solved

Every library invented its own containers, so code couldn't pass collections around, or swap a slow implementation for a faster one without a rewrite.

why it matters: without it

Every solution would start with a hand-written hash table or heap, and every library would speak its own container dialect.

sources: Collections Framework Overview (Oracle) ↗ · OpenJDK source: java.util.Collection (@author Josh Bloch, Neal Gafter; @since 1.2) ↗ · Joshua Bloch, author bio (InformIT) ↗ · LWN, 10 Dec 1998: JDK 1.2 ships as the Java 2 Platform ↗

also in this chapter: ArrayList (dynamic array) · HashMap & HashSet (hash table) · ArrayDeque (ring buffer) · PriorityQueue (binary heap) · TreeMap & TreeSet (red-black tree) · Autoboxing & the Integer cache

the idea

The idea in 30 seconds

Most interview solutions are 80% choosing the right container: ArrayList, ArrayDeque, HashMap/HashSet, TreeMap/TreeSet, PriorityQueue.

Each one is a data structure you'll meet later in the course. The JDK already wrote it for you. Know what's inside, and you know what each call costs.

A few traps (Integer ==, a - b comparators, remove(int) vs remove(Object)) cause most "it works on my example" bugs.

picture this

java.util is like the tools already installed on your laptop. Nobody writes a text editor before taking notes, but you do need to know when to open Notepad and when to open Excel. Same here: pick the container whose strengths match the job.

watch it

Inside ArrayList: growing by 1.5×

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Inside ArrayList: growing by 1.5×

Adds are cheap writes. When the array is full, Java allocates about 1.5× the slots and copies everything. That's rare enough that add stays amortized O(1).

loading simulation…

javajava.util.*

1class IntArrayList {2    private int[] data;                       // the backing array: capacity = data.length3    private int size = 0;                     // how many slots are actually used4 5    IntArrayList(int initialCapacity) {6        data = new int[initialCapacity];7    }8 9    void add(int value) {10        if (size == data.length) grow();      // full? make room first11        data[size++] = value;                 // the cheap O(1) part12    }13 14    private void grow() {15        int oldCapacity = data.length;16        int newCapacity = oldCapacity + Math.max(1, oldCapacity >> 1); // about 1.5x, like java.util.ArrayList17        data = Arrays.copyOf(data, newCapacity); // copies every element: O(size)18    }19 20    int get(int i) {21        Objects.checkIndex(i, size);          // same bounds check ArrayList.get does22        return data[i];23    }24 25    int size() { return size; }26 27    int capacity() { return data.length; }28}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

watch it

Inside HashMap: buckets, collisions, resizing

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Inside HashMap: buckets, collisions, resizing

Each key is hashed to a bucket. Watch a collision form a chain, then the table double at load factor 0.75.

loading simulation…

javajava.util.*

1class IntHashMap {2    private List<int[]>[] buckets;            // each bucket: a chain of {key, value}3    private int size = 0;4 5    @SuppressWarnings("unchecked")6    IntHashMap(int capacity) {                // capacity: a power of two7        buckets = new List[capacity];8    }9 10    static int spread(int h) {11        return h ^ (h >>> 16);                // same bit-mixing java.util.HashMap uses12    }13 14    private int indexFor(int key, int capacity) {15        return spread(Integer.hashCode(key)) & (capacity - 1); // fast "mod capacity"16    }17 18    void put(int key, int value) {19        int b = indexFor(key, buckets.length);20        if (buckets[b] == null) buckets[b] = new ArrayList<>();21        for (int[] entry : buckets[b])22            if (entry[0] == key) { entry[1] = value; return; } // key exists: overwrite23        buckets[b].add(new int[] {key, value}); // append to the chain24        if (++size > buckets.length * 3 / 4) resize(); // load factor 0.7525    }26 27    Integer get(int key) {28        List<int[]> chain = buckets[indexFor(key, buckets.length)];29        if (chain != null)30            for (int[] entry : chain) if (entry[0] == key) return entry[1];31        return null;32    }33 34    @SuppressWarnings("unchecked")35    private void resize() {36        List<int[]>[] old = buckets;37        buckets = new List[old.length * 2];   // double, then re-bucket every entry: O(n)38        for (List<int[]> chain : old)39            if (chain != null)40                for (int[] e : chain) {41                    int b = indexFor(e[0], buckets.length);42                    if (buckets[b] == null) buckets[b] = new ArrayList<>();43                    buckets[b].add(e);44                }45    }46 47    int size() { return size; }48 49    int capacity() { return buckets.length; }50}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

key idea 1 of 8