HashMap and HashSet: finding things fast

Say a fruit shop keeps its stock as a list of pairs: apples 12, bananas 30, cherries 7, and so on for a hundred kinds of fruit. To find the bananas, a program would check the pairs one by one until it reached the right name. A map does better. You hand it the name, “banana”, and it goes straight to the number stored with it, however many other fruits there are. This lesson teaches you to use HashMap and its partner HashSet, then opens a HashMap up so you can watch where each key goes, and why.

A map looks a value up by its key#

A map holds pairs. In each pair, the key is what you look things up by, like a word in a dictionary, and the valueis what you find there, like the word's meaning. In the fruit shop the key is the name of a fruit and the value is how many boxes of it are in the back room. One pair is called an entry.

Here is the stock list as a HashMap. Press Run, step through it, and keep an eye on the memory view under the code.

It prints {banana=30, apple=12, cherry=7}, then Bananas: 30, then Kinds of fruit: 3. Three things in it are new.

• Map<String, Integer> stock = new HashMap<>(); makes an empty map. The first type in the angle brackets is the type of the keys and the second is the type of the values, so here the keys are String names and the values are Integer box counts. The variable has the interface type Map and the object is a HashMap, the same habit as a List variable holding an ArrayList. Both names are imported from java.util.
• stock.put("apple", 12); stores one pair: the key "apple" with the value 12.
• stock.get("banana") looks up the key "banana" and hands back its value, 30. stock.size() counts the pairs.

Printing a map shows each pair as key=value inside curly braces. Now look at the narration for each put. It names a numbered slot, called a bucket, for every key: bucket 1 for apple, bucket 0 for banana, bucket 1 again for cherry. The memory view draws those buckets under the map. They let a HashMap find a key without searching through every entry, and the second half of this lesson explains how. They also explain the printed order: apple went in first, yet banana comes out first. A HashMap does not keep the order you put things in.

Keys that are not there

Asking for a key that is not in the map is allowed. get returns null, Java's value for “no object here”. Two more methods help with missing keys.

• stock.get("kiwi") returns null, because kiwi is not a key.
• stock.getOrDefault("kiwi", 0) returns the value when the key is there, and otherwise the default you passed in. Here that is 0.
• containsKey answers whether a key is in the map at all: false for kiwi, true for apple.

The last line shows that getOrDefault only reads. It answered 0 for kiwi without storing anything, so the map still holds its two pairs: {banana=30, apple=12}.

A missing key does cause real trouble in one place. Run this.

The first lookup works and prints apples: 12. The second stops the program with a NullPointerException. get returned null for kiwi, and Java cannot unbox null into an int, because there is no number inside it to take out. Java's message says exactly that: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null.

Each key appears once

Every key in a map is unique. Values can repeat: apples and pears could both have 9 boxes. So when you put a key that is already there, the new value replaces the old one and the map stays the same size. put also hands back the value it replaced, or null when the key was new. remove(key) takes the key out together with its value, and hands back that value. Step through this and watch the map in the memory view.

It prints apple was 12, now 20 and Kinds of fruit: 2: the second put changed apple's value and added nothing. Removing banana hands back its 30 and leaves {apple=20}. Removing banana a second time finds nothing, so remove returns null. That is why before and removed are Integer variables: both methods can answer null.

Key idea

A map stores pairs, and each key appears in it at most once. put adds a pair or replaces the value of a key that is already there, and get finds the value for a key.

It prints 2 and then 90. The third put found Sana already there, so it replaced 70 with 90 instead of adding a third pair.

Walking through a map#

A map has no positions 0, 1, 2 to count through, and a for-each loop cannot walk a map directly. Instead you ask the map for one of three views and walk that.

• keySet() gives every key.
• values() gives every value.
• entrySet() gives every pair, as Map.Entry<String, Integer> objects. getKey() and getValue() read the two halves of an entry.

All three loops go through the pairs in the same order, the map's own order: banana, apple, cherry. The first prints banana: 30 boxes and so on, the second prints We sell banana and so on, and the last adds up the boxes, 30 + 12 + 7, to print Boxes in the back room: 49. Its loop variable is a plain int, and Java unboxes each Integer on the way out.

Counting and grouping#

Two jobs come up again and again in real programs, and a map handles both: counting how often each thing appears, and sorting things into groups.

Counting words

To count words, make the word the key and its count the value. For each word, read the count so far, add one, and put the new count back. A word seen for the first time has no count yet, which is where getOrDefault(word, 0) helps. One more new method: text.split(" ") cuts the text at every space and gives back the words as an array.

It prints {the=3, mat=1, too=1, and=1, cat=1, sat=2, dog=1, on=1}. Read the narration as you step. The first “the” goes in with 1, and each later “the” changes its value, from 1 to 2 and then to 3.

merge: read, add and put in one call

Counting is so common that Map has a method for it. merge(word, 1, Integer::sum) means: if word is not a key yet, store 1. If it is, combine the old count and the 1 with Integer::sum, and store the result. Integer::sum is a method reference for the lambda (a, b) -> a + b, so the old count goes up by one.

It prints {the=3, mat=1, too=1, and=1, sat=2, cat=1, dog=1, on=1}. The counts are the same, but look closely at cat and sat: they have swapped places. The section on order explains why.

1import java.util.HashMap;
2import java.util.Map;
3 
4public class Main {
5    public static void main(String[] args) {
6        String[] votes = {"pizza", "tacos", "pizza", "sushi", "tacos", "pizza", "curry"};
7        Map<String, Integer> tally = new HashMap<>();
8 
9        // TODO: count each vote into tally
10 
11        System.out.println("pizza: " + tally.get("pizza"));
12        System.out.println("tacos: " + tally.get("tacos"));
13        System.out.println("sushi: " + tally.get("sushi"));
14        System.out.println("curry: " + tally.get("curry"));
15    }
16}

Grouping with computeIfAbsent

Now say the shop wants an index of its fruit by first letter, like the index at the back of a book: a for apple, avocado and apricot, b for banana and blueberry. The key is a letter and the value is a whole list of names, so the map's type is Map<Character, List<String>>. The first time a letter turns up there is no list for it yet. You have to make an empty list and put it in the map before you can add to it, and computeIfAbsent does that for you.

index.computeIfAbsent(first, k -> new ArrayList<>()) checks whether first is a key. If it is not, it runs the lambda to make a new, empty list, stores that list under first and returns it. If it is, the lambda never runs, and you get back the list already stored there. Either way the result is the list for that letter, and .add(fruit) adds the fruit to it. The program prints {a=[apple, avocado, apricot], b=[banana, blueberry], c=[cherry]}, then [banana, blueberry] for the letter b.

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5 
6public class Main {
7    public static void main(String[] args) {
8        String[] fruits = {"fig", "kiwi", "pear", "plum", "apple", "lime", "mango", "date"};
9        Map<Integer, List<String>> byLength = new HashMap<>();
10 
11        // TODO: add each fruit to the list for its length
12 
13        System.out.println(byLength);
14    }
15}

HashSet: each value once#

Sometimes there is nothing to look up. You only need to know whether you have met something before: which people visited a website today, or which words appear in a book. A HashSet is a collection of values with no duplicates. Adding a value it already holds changes nothing.

add returns true when the value is new and false when the set already holds it, which lets the loop tell first visits from return visits. Sana visited three times and is stored once, so the program ends with 3 different visitors: [Mei, Ravi, Sana] and Has Mei visited? true. contains answers whether a value is in the set.

Inside, a HashSet is a HashMap. Each value you add becomes a key of that hidden map, with a placeholder as its value. So everything this lesson says about HashMap keys is true of HashSet values as well: contains goes straight to one bucket, the printed order looks scrambled, and a value must not change while it is in the set.

Combining two sets

Three methods combine a set with another collection. Each one changes the set you call it on, so copy the set first when you still need the original. new HashSet<>(monday) makes a new set that holds the same values as monday.

• addAll(other) adds every value from other, leaving everything that is in either one.
• retainAll(other) keeps only the values that other also has, leaving what the two have in common.
• removeAll(other) removes every value that other has, leaving what only the first one has.

Bea and Dee came on both days, five different people came at least once, and Ali and Cal came only on Monday. The output reads Both days: [Dee, Bea], Either day: [Dee, Eve, Ali, Bea, Cal] and Monday only: [Ali, Cal], and monday itself never changed.

How a HashMap finds a key#

Picture a cloakroom with 16 numbered hooks. When you hand in your coat, the attendant turns your name into a hook number with a fixed rule and hangs the coat there. When you come back, they apply the same rule to your name and walk straight to that hook. They never look at the other 15 hooks.

A HashMap works the same way. Its hooks are the buckets, kept in an array called the table, and a map made with new HashMap<>() gets a table of 16 buckets when you put its first key. The rule that turns a key into a bucket number has three steps:

1. 1Ask the key for its hash code, a single int worked out from the key.
2. 2Mix the high half of that number into the low half.
3. 3Keep only the last few bits of the result. They are the bucket number.

Take them one at a time, with the key “fig”.

Step 1: the hash code

Every Java object has a method hashCode() that turns it into one int, its hash code. Two equal strings always have the same hash code, every time the program runs. For a String, the API documentation fixes the exact formula, and you can work it out one character at a time: start with h = 0, then for each character in turn, multiply hby 31 and add the character's code. A character is a number underneath, as you saw in operators and casting: 'f' is 102, 'i' is 105 and 'g' is 103. Step through the loop and watch h grow.

By hand that is 31 × 0 + 102 = 102, then 31 × 102 + 105 = 3267, then 31 × 3267 + 103 = 101380, and the last line confirms that "fig".hashCode() is the same 101380. The documentation writes the formula as one sum, which for fig is 102 × 31² + 105 × 31 + 103. That comes to 101380 too: each character gets multiplied by 31 once for every character that follows it.

When the number gets too big

An int holds whole numbers from -2,147,483,648 to 2,147,483,647. Multiplying by 31 for every letter passes that limit after a handful of letters, and Java does not stop or warn you when intarithmetic goes past the top. The number wraps around to the bottom of the range and carries on, the way a car's mileage counter rolls over from 999999 to 000000. Here is the same loop for “banana”.

After five letters h is 93503612. The last letter makes it 31 × 93503612 + 97, which is 2,898,612,069, too big for an int. Java keeps only what fits, which here means subtracting 2³² (4,294,967,296), so h becomes -1396355227. A hash code can be negative, and nothing is wrong with that. hashCode() gives the same number because it does the same arithmetic.

Step 2: mixing in the high bits

HashMap does not use the hash code as it is. First it mixes the top half of the number into the bottom half with h ^ (h >>> 16). Both operators work on the bits of a number, the 0s and 1s it is stored as. An int has 32 of them.

• h >>> 16 slides every bit 16 places to the right and fills the gap on the left with zeros, so the top 16 bits end up as the bottom 16. For fig, 101380 >>> 16 is 1: 101380 lies between 65,536 (that is 2¹⁶) and 131,072, so its top half holds just 1.
• ^ is exclusive or. It compares two numbers bit by bit and puts a 1 wherever exactly one of them has a 1. 101380 is even, so its last bit is 0, and 101380 ^ 1 turns that bit on: 101381.

So fig's mixed hash is 101381. Why HashMap bothers to mix becomes clear after step 3.

Step 3: from hash to bucket

With 16 buckets, the bucket number is (16 - 1) & hash, which is 15 & hash. & is bitwise and: it puts a 1 only where both numbers have a 1. In binary, 15 is 1111, so 15 & hash keeps the last four bits of the hash and clears all the others. Four bits make a number from 0 to 15, one for each bucket. For a hash that is not negative, this is the remainder after dividing by 16: 101381 is 6336 × 16 + 5, so fig goes in bucket 5.

Here are the three steps as one method, run for six fruits.

It prints fig -> bucket 5, then buckets 1, 0, 1, 2 and 2. These are the buckets the narration named in the first program of the lesson: apple in bucket 1, banana in bucket 0, cherry in bucket 1. HashMap runs the same three steps, so the answers match.

Key idea

A HashMap turns each key into a bucket number with the key's hash code. To find a key, it works out the bucket and looks only there, however many other keys the map holds.

Now try the steps on words of your own. Type a word into the lab and it works out the hash code a character at a time, mixes it, and shows the bucket. Put stores the word in the table, and Add a fruit adds the fruit from this page in order. Two things to try: put Aa and then BB, and keep adding fruit until the table doubles.

Two keys in one bucket

With 16 buckets and more than a few keys, some keys are bound to share a bucket: apple and cherry both landed in bucket 1. Two keys in the same bucket is called a collision, and it is normal. A bucket holds a short chain of entries, and a new key joins the end of its bucket's chain.

To find a key, HashMap works out the bucket, then walks that bucket's chain and compares the key with each key there using equals. A chain usually holds one or two entries, so the search ends almost at once, and the other buckets are never touched.

Two different keys can even have exactly the same hash code. Aa and BB both have the hash code 2112 (31 × 65 + 97 for one and 31 × 66 + 66 for the other), so they always share a bucket. That is allowed, because equals tells them apart.

When the table fills up

Chains stay short only while there are enough buckets for the keys, so a HashMap keeps an eye on how full its table is. Its load factor is 0.75 unless you choose another: when the number of entries passes three quarters of the number of buckets, the table doubles. With 16 buckets that line is 16 × 0.75 = 12, so the put that brings in a 13th key makes the table grow to 32 buckets.

Growing is like moving to a cloakroom with twice as many hooks. The rule now chooses from 32 hooks, so every coat needs its hook worked out again. HashMap makes a new table of 32 buckets and moves each entry across. Step through this program to line 21, the 13th put, and compare the memory view just before and just after it.

The first line prints the 12 keys in bucket order, starting with the three keys in bucket 0: [banana, date, orange, apple, cherry, kiwi, lemon, pear, fig, grape, melon, mango]. The 13th put stores plum, finds 13 entries in a table meant for at most 12, and doubles the table, which the narration reports. The second line shows the new order: [banana, date, plum, cherry, kiwi, fig, grape, mango, orange, apple, lemon, pear, melon]. Adding one key reordered the others.

Each key moves by a simple rule. In a table of 32, the bucket number comes from the last five bits of the hash instead of the last four. That one extra bit decides: if it is 0 the key stays in the same bucket, and if it is 1 the key moves up exactly 16. Apple goes from bucket 1 to bucket 17, while cherry, which shared bucket 1 with it, stays in bucket 1.

Why the order looks scrambled#

You can now explain the printing order. Printing a HashMap, or walking it with a for-each loop, goes through the table from bucket 0 to the last bucket, and through each bucket's chain from front to back. The order you added the keys in plays no part. That is why banana, in bucket 0, printed ahead of apple, in bucket 1, at the start of the lesson.

Integer keys make a good test, because an Integer's hash code is the number itself, and for numbers this small the mixing step changes nothing. Decide what this prints before you run it.

It prints {1=Ravi, 17=Mei, 3=Tom, 5=Sana}. Rooms 1 and 17 share bucket 1, because 17 is 16 + 1, and 17 joined that chain after 1. Small Integer keys often come out in sorted order, which leads people to think a HashMap sorts them. Room 17 shows that the sorting was only the buckets lining up.

The order can even change while the program runs: one extra fruit made the whole stock list print in a new order. The HashMap documentation says plainly that it makes no promise about the order, and not even that the order will stay the same over time. Never write code that depends on it.

LinkedHashMap and TreeMap keep an order

When the order matters, pick a different map. A LinkedHashMap is a HashMap that also keeps its entries linked in a line, in the order the keys were first put in, and walks them in that order. Putting a key that is already there changes its value and keeps its place in the line. A TreeMap keeps its keys sorted: numbers from smallest to largest, and strings in alphabetical order, with every capital letter before every small one. The program below gives all three maps the same four puts. Only the class name after new changes.

The HashMap prints in bucket order: apple (bucket 1), pear (2), fig (5), mango (15). The LinkedHashMap prints pear, apple, mango, fig, the order of the puts. The TreeMap prints apple, fig, mango, pear, which is alphabetical.

A taste of TreeMap

Because a TreeMap knows the order of its keys, it can answer questions a HashMap cannot, such as which key is the smallest, or which key is the closest one at or below a number. Here each key is the lowest score that earns a grade.

• The puts came in a jumbled order, and the map prints sorted: {0=F, 50=D, 60=C, 70=B, 80=A}.
• firstKey() gives the smallest key, 0. lastKey() would give the largest, 80.
• floorKey(73) gives the largest key that is 73 or less. That is 70, so a score of 73 earns a B.
• headMap(60) gives the part of the map whose keys are below 60, as a map of its own: {0=F, 50=D}.

These methods belong to TreeMap, so grades is declared as a TreeMap here, not as a Map.

Key idea

A HashMap's order comes from its buckets, not from when you added things. Use a LinkedHashMap to keep the order you put keys in, and a TreeMap to keep the keys sorted.

Keys must not change#

A HashMap files each entry under its key's hash code at the moment you put it. If the key changes afterwards, its hash code changes with it, and the map looks for it in the wrong place. A list shows this well, because a list's hash code is worked out from the items in it, and a list can change. Here a café uses an order, a list of items, as the key and the order's price as the value. Step through it and watch the map in the memory view.

The first lookup finds 7. Then order.add("jam") changes the list that is sitting inside the map as a key. Its hash code changes too, and now leads to bucket 14, while the entry is still filed in bucket 4. So get(order) returns null and containsKey says false. A fresh list of tea and toast does no better: its hash code leads to bucket 4, but equals then compares it with the stored list, which now holds three items, and finds them different. The last line, 1 {[tea, toast, jam]=7}, shows the entry is still in the map, where no lookup can reach it any more.

Key idea

Never change an object while it is a key in a map or a value in a set. Use keys that cannot change, such as strings, numbers and records.

Records make good keys

Strings and Integers can never change, which makes them safe keys. When a key needs more than one value, make it a record: its fields are final, and its equals and hashCode are built from its components. A train fare depends on where the trip starts and where it ends, so here the key is a Route.

The new Route("Leeds", "Hull") on the lookup line is a different object from the one that went in, but the two are equal and have the same hash code, so get finds the fare and prints 18. Hull to Leeds is a different route, so containsKey prints false.

Further reading#

• HashMap in the Java SE 25 API documentation, including what its load factor and capacity mean
• The Map interface in the Java SE 25 API documentation, with getOrDefault, merge and computeIfAbsent
• Handling map values with lambda expressions, on dev.java
• Choosing immutable types for your key, on dev.java