Inside ArrayList and HashMap: build your own

You have used ArrayList and HashMap for many lessons, and you have looked inside both: the backing array with its spare slots, and the table of buckets. In this lesson you write a small version of each class yourself and watch every array and node it makes in the memory view as it runs. By the end you will know what the two classes do inside, because you will have written the same steps.

A list that grows#

An array has a fixed length. You choose it when you create the array, and it never changes. A list has to take as many elements as you add, without being told how many in advance. ArrayList gets round this with a plan you can copy: keep the elements in an array that is longer than you need, count how many of its slots are in use, and when every slot is taken, move everything into a bigger array.

Think of a bookshelf. While there is a gap, a new book goes into the next gap. When the shelf is full, you buy a shelf twice as long, move the books across in the same order, and put the new book after them. The old shelf is thrown away.

An array used this way is called a dynamic array. It needs two fields: the array, here called items, and size, the number of slots in use. The array's length is the list's capacity. Slots 0 to size - 1 hold the elements, and the slots after them are spare. Here is a playlist built that way. Its array starts with two slots.

It prints 5 songs in 8 slots and Song 4 is Rain. Both fields are private, so code outside the class can use the playlist only through its methods, the same as a real ArrayList.

Read add from the bottom up. Usually there is a spare slot: the song goes into items[size], the first free slot, and size++ moves the count on, so the next song lands in the slot after it. The if at the top deals with a full array, when size equals items.length. It makes an array twice as long, copies every song into the same index of the new array, and points items at the new array. Only then does the new song go in.

Step through the third add with the memory view open. The condition is true, and a second array titled bigger appears under Arrays, with four empty slots. The loop copies Intro and Waves into it. Then the step that sets items points the playlist's items field at bigger, and the old two-slot array is left with nothing pointing at it. The fifth add does it all again, with eight slots.

Key idea

A growing list is an array with spare room and a count of the slots in use. When the room runs out, add copies everything into a bigger array and carries on.

Arrays.copyOf does the copying#

Copying an array into a longer one is common enough that java.util.Arrays has a method for it. Arrays.copyOf(items, newLength) makes a new array of the length you ask for, copies the elements of items into the start of it, fills the rest with null (or 0 for an int array), and returns the new array. One line replaces the new array, the loop and the reassignment:

The file needs import java.util.Arrays; at the top. The programs from here on use this version of add.

get needs a bounds check#

The first get just returns items[index], and trusts the caller to ask only for a song that is in the list. Decide what this program prints before you run it.

It prints Echo and then null. The playlist holds three songs, but after the third add its array has four slots, so items[3] is a real slot: the spare one, which holds null. The list hands back something nobody added. Ask for get(9) and you do get an exception, but the wrong one: ArrayIndexOutOfBoundsException: Index 9 out of bounds for length 4. The 4 in it is the capacity, a detail of how the list stores its songs. A list of three songs should refuse every index from 3 up.

The fix is one line at the top of get. Objects.checkIndex(index, size), from java.util.Objects, checks that index is at least 0 and less than size. If it is, the method hands the index back and get carries on. If not, it throws an IndexOutOfBoundsException.

This prints Echo, then stops with IndexOutOfBoundsException: Index 3 out of bounds for length 3. That is word for word the message an ArrayList gave you in the ArrayList lesson when you asked for one past the end, and for a good reason. In OpenJDK, the code the usual JDK downloads are built from, ArrayList.get starts with the same call, Objects.checkIndex(index, size). The method has been in Java since version 9.

remove shifts the rest left#

Taking an element out of the middle leaves a gap, and a list's elements must stay in slots 0 to size - 1 with no gaps. So remove moves every element after the gap one slot to the left. Step through it and watch the array in the memory view.

It prints [Intro, Waves, Echo, Tides], then Removed Waves: [Intro, Echo, Tides]. remove(1) checks the index and keeps Waves in removed, to return at the end. The loop then writes Echo into items[1] and Tides into items[2], each pass copying from the slot on its right. size-- shrinks the list to three songs, and the last write puts null into items[3].

That nullmatters, even though slot 3 is outside the list now. Without it, the array would still refer to the object in that slot. Remove the last song and nothing shifts at all, so the array would go on holding the song you removed, and the garbage collector could never free it while the playlist exists. OpenJDK's ArrayList clears the slot in the same way.

toString copies the slots in use into a shorter array and lets Arrays.toString format it, which is why the spare slots never show when you print a playlist.

How long remove takes depends on where you remove from. remove(0) shifts every other element: O(n). Removing the last element shifts nothing: O(1). Those are the costs in the table from Big-O, and now you have written the loop behind them.

1import java.util.Arrays;
2import java.util.Objects;
3 
4public class Main {
5    public static void main(String[] args) {
6        Playlist songs = new Playlist();
7        songs.add("Waves");
8        songs.add("Tides");
9        songs.add(0, "Intro");
10        songs.add(2, "Echo");
11        songs.add(4, "Rain");
12        System.out.println(songs);
13    }
14}
15 
16class Playlist {
17    private String[] items = new String[2];
18    private int size;
19 
20    void add(String song) {
21        if (size == items.length) {
22            items = Arrays.copyOf(items, items.length * 2);
23        }
24        items[size] = song;
25        size++;
26    }
27 
28    // Puts song at position index and moves the songs from index onwards one place right.
29    void add(int index, String song) {
30        // TODO: check the index, grow if full, shift songs right, store the song, count it
31    }
32 
33    @Override
34    public String toString() {
35        return Arrays.toString(Arrays.copyOf(items, size));
36    }
37}

Why the array doubles#

Doubling is a choice. add could make the new array just one slot longer, which never wastes a slot. To compare the two rules, this program fills an array that starts with one slot, for a few values of n, and counts how many values each rule copies along the way.

With doubling, filling 64 slots copies 63 values. The copies happen when the array holds 1, 2, 4, 8, 16 and 32 values, and 1 + 2 + 4 + 8 + 16 + 32 = 63. Each copy moves one value more than all the copies before it put together (32 is 1 + 2 + 4 + 8 + 16, plus 1), so the total stays below n however large n gets. Adding n values costs n writes plus fewer than n copies: less than 2n steps in all, or less than 2 steps per add.

A single add can still be slow. The one that finds the array full copies the whole list, which is O(n) on its own. But a copy of k values doubles the room, so the next copy is k adds away. Spread over those k adds, the copy costs about one step each, so on average every add costs a constant amount. That is the amortized cost you met in Big-O: add is O(1) amortized. The ArrayList documentation makes exactly this promise: adding n elements takes O(n) time.

Growing by one slot behaves very differently. Once the array is full, every add finds it full again, so every add copies the whole list: 1 + 2 + 3 + ... + 63 = 2,016 copies for 64 values. That sum is n × (n - 1) / 2, about half of n², so filling a list this way is O(n²). The output shows the square: each time n doubles, the copies grow about four times, from 28 to 120 to 496 to 2,016.

For a million values, doubling copies about a million values, roughly one per add. Growing by one slot copies about half a trillion, roughly half a million per add.

Key idea

Grow an array by multiplying its length, never by adding a fixed number of slots. Multiplying keeps the total copying in proportion to the number of elements, so each add costs O(1) amortized.

A list of any type#

Playlist holds only strings. A real list class works for any element type, so the next step is a generic class, GrowList<T>, as in generics. Most of the change is renaming String to T. One line refuses to change: the one that creates the array. new T[2] does not compile. javac stops with generic array creation, because the running program no longer knows what T is, and an array has to know its element type to check every value stored in it.

The usual way round it is to make an Object[], which can hold any object, and cast it to T[]:

It prints [Intro, Waves, Echo], song 1 is Waves, then [72, 90], total 162: one class holds strings in one list and Integers in another. Step through it and look at the type printed next to each array in the memory view. It says Object[], for the list of strings as well. The cast changed what the compiler believes about the array, and nothing about the array itself.

javac accepts the cast with a warning. Take away the @SuppressWarnings line and compile, and javac prints a note; ask it for the details and you get this:

“Unchecked” means javac cannot check the cast for you. Because of erasure, T is gone when the program runs, so (T[]) has nothing to compare the array with, and the cast never fails. In general that is a risk: a variable of type T[] could end up holding an array that is not a T[] at all, and the trouble would show up far away from the cast.

In GrowList it cannot happen, for two reasons. The array is private and no method hands it out, so no code outside the class ever sees it. And the only way in is add(T item), where javac checks that every value really is a T. Every element that get returns went in through add, so it really is a T. @SuppressWarnings("unchecked") tells javac that you have checked this cast yourself, and it silences the warning for the constructor only. Keep the annotation on the smallest piece of code you can, so that a new unchecked problem anywhere else still gets its warning.

A hash map of your own#

Now the second class. A HashMap keeps its entries in an array of buckets. To put a key, it turns the key's hash code into a bucket number and stores the entry in that bucket. To get a key, it works out the same bucket and looks only there. Keys that land in the same bucket form a chain, a small linked list. Keeping each bucket's entries in a linked list like this is called chaining, or separate chaining.

Each entry is a node, like the nodes in linked lists with one more field: it holds a key, a value, and next, the next node in the same bucket. The map has two fields of its own. bucketsis an array of nodes, where each slot holds the first node of one bucket's chain, or null when the bucket is empty, and size counts the keys. The map on this page is a stock list for the fruit shop from the HashMap lesson, with String keys, int values and four buckets to start.

From hash code to bucket#

A bucket number must be between 0 and the number of buckets minus 1. The remainder after dividing by the number of buckets looks like the answer, since h % 4 ought to be 0, 1, 2 or 3. Run this:

Apple gets bucket 2, but banana and cherry get -3, and buckets[-3] would stop the program with an ArrayIndexOutOfBoundsException. Hash codes can be negative, as you saw when banana's hash code wrapped around in the HashMap lesson, and % keeps the sign of the number on its left, as operators explained. So a negative hash code gives a negative remainder, or 0.

The last column has the fix. 0x7fffffff is a number written in hexadecimal: the largest int, 2,147,483,647. In binary it is a 0 followed by 31 ones. Java stores every negative int with its highest bit set to 1, and every other int with that bit set to 0, so that bit is called the sign bit. h & 0x7fffffff keeps the lower 31 bits of h and sets the sign bit to 0, so the result is never negative. For a negative hthat is the same as adding 2,147,483,648: banana's -1,396,355,227 becomes 751,128,421, and 751128421 % 4 is 1.

So the map works out a bucket in one line, (key.hashCode() & 0x7fffffff) % tableSize, inside a method called indexFor.

put and get#

putworks out the bucket, then walks that bucket's chain. If a node there holds an equal key, putchanges that node's value and returns, because a map holds each key once. If the walk reaches the end of the chain without a match, the key is new. put makes a node for it and links the node in at the front of the chain. That is the add-at-the-front from the linked-list lesson, written as one line: buckets[i] = new Node(key, value, buckets[i]); gives the new node the old first node as its next, then makes it the first node. get walks the same chain and returns the value it finds there, or null.

It prints banana: 25, kiwi: null and kinds of fruit: 3. get returns an Integer so that it can answer null for a missing key, like the real get. indexFor takes the number of buckets as a parameter, because the bucket depends on it as well as on the key; that matters in the next section.

Step through it with the memory view open. Under Arrays, the table is a row of four slots, each holding null or the tag of the first node in that bucket's chain, such as Node #1. Under Objects, each node shows its key, value and next, and the tags follow the order the nodes were made, so a slot and an arrow that say Node #3 lead to the same box.

Watch put("cherry", 7). Cherry belongs in bucket 1, where banana already is. The walk compares cherry with banana and finds no match. The constructor points the new node's next at banana's node, and the step that writes the new node into buckets[1] makes cherry the front of the chain. Then watch put("banana", 25). The walk passes cherry, finds banana, and the step that sets node.value to 25 changes the value in place. No node is added, and size stays at 3.

Key idea

A hash map with chaining is an array of linked lists. The key's hash code picks the list, and equals finds the key inside it.

Growing the table#

Chains stay short only while there are enough buckets. Four buckets suit three fruits, but with a hundred fruits each chain would hold about 25 nodes, and every get would walk one of them. So the map counts its keys and doubles the table before the chains get long.

HashMap makes that decision with its load factor: the most keys per bucket, on average, that the table may hold before it grows. The default is 0.75, and this map uses the same rule: once size is more than three quarters of the number of buckets, the table doubles. With 4 buckets the line is 3, so the fourth key sets it off.

Doubling the array is not enough on its own, because a key's bucket depends on the number of buckets: indexFor ends with % tableSize. Banana sits in bucket 1 of 4, but belongs in bucket 5 of 8. So resize makes the bigger array, then walks every chain of the old one and moves each node into the bucket its key picks in the new table, at the front of the chain there. A new method, show, prints each bucket with its chain, front first.

The first table is the one from before: cherry and banana share bucket 1, and apple is alone in bucket 2. put("mango", 4) links mango in at the front of bucket 2, size becomes 4, and since 4 is more than 3.0, put calls resize. The second table has eight buckets, and the chain in bucket 1 has split up: cherry stayed in bucket 1, and banana moved to bucket 5.

Step through resize. It creates bigger with eight empty slots, then walks the old buckets from 0 up. For each node it saves node.next in following and works out the new bucket. Then two steps link the node in at the front there: one points node.next at whatever that bucket already holds, and the next writes the node into bigger[i]. Mango and apple both belong in bucket 2. Mango moves first, so when apple arrives, the step that sets node.next points apple at mango, and apple becomes the front. That is why the second table lists apple before mango. The order inside a bucket makes no difference to put and get, which compare the key with every node in the chain anyway.

following is there for the reason you met in the linked-list lesson: node.next = bigger[i] overwrites the only reference to the rest of the old chain, so resize has to save it first. Last of all, buckets = bigger switches the map over to the new table, and the old table is left with nothing pointing at it.

1public class Main {
2    public static void main(String[] args) {
3        StockMap stock = new StockMap();
4        stock.put("apple", 12);
5        stock.put("banana", 30);
6        stock.put("cherry", 7);
7        stock.put("mango", 4);
8        stock.put("date", 5);
9        stock.show();
10 
11        System.out.println(stock.remove("mango") + " " + stock.remove("cherry") + " "
12                + stock.remove("apple") + " " + stock.remove("kiwi"));
13        stock.show();
14        System.out.println("size " + stock.size());
15    }
16}
17 
18class StockMap {
19    private Node[] buckets = new Node[4];
20    private int size;
21 
22    private int indexFor(String key, int tableSize) {
23        return (key.hashCode() & 0x7fffffff) % tableSize;
24    }
25 
26    void put(String key, int value) {
27        int i = indexFor(key, buckets.length);
28        for (Node node = buckets[i]; node != null; node = node.next) {
29            if (node.key.equals(key)) {
30                node.value = value;
31                return;
32            }
33        }
34        buckets[i] = new Node(key, value, buckets[i]);
35        size++;
36    }
37 
38    // Takes key out of the map and returns its value, or returns null if key is not in the map.
39    Integer remove(String key) {
40        // TODO: find the key's bucket, walk its chain, and unlink the node that holds key
41        return null;
42    }
43 
44    int size() {
45        return size;
46    }
47 
48    void show() {
49        for (int i = 0; i < buckets.length; i++) {
50            System.out.print(i + ":");
51            for (Node node = buckets[i]; node != null; node = node.next) {
52                System.out.print(" " + node.key + "=" + node.value);
53            }
54            System.out.println();
55        }
56    }
57}
58 
59class Node {
60    String key;
61    int value;
62    Node next;
63 
64    Node(String key, int value, Node next) {
65        this.key = key;
66        this.value = value;
67        this.next = next;
68    }
69}

What a bad hashCode does#

All of this speed depends on the hash codes spreading the keys across the buckets. In equals, hashCode and toString you saw that a hashCode which returns the same number for every object keeps the contract, because equal objects still get equal hash codes. It is legal Java. This section measures what it costs.

To use keys of your own class, the map has to accept any key type, so it becomes generic: TinyMap<K, V> with Node<K, V>, and the same kind of cast for the array as the list needed, (Node<K, V>[]) new Node[capacity]. This cut-down version has only put, and counts how many times put compares two keys with equals. BadKey is a record whose hashCode always returns 42. Its equals is the one every record gets, which compares the text. Both maps get 32 buckets, plenty for 20 keys, so neither needs to grow.