HashMap and HashSet

Problem

Who is this user?

The users of the site are in a list. At every login you look up the email by the username:

static String findEmail(List<User> users, String username) {
    for (User u : users) {
        if (u.username.equals(username)) {
            return u.email;
        }
    }
    return null;
}

With three users this is instant. With 2,000,000, every login compares up to 2,000,000 names, and there are thousands of logins a minute. You do not read a phone book from the first page. You go straight to the letter.

The idea

Dictionary: key → value

You want to ask "what is the email of georgiev?" and get the answer right away. The collection for this is called a dictionary (map). It holds pairs: a key and a value. In Java the usual dictionary is HashMap:

Map<String, String> emails = new HashMap<>();
emails.put("ivanov", "ivanov@example.com");
emails.put("mpetrova", "mpetrova@example.com");
emails.put("georgiev", "georgiev@example.com");

System.out.println(emails.get("georgiev"));
System.out.println(emails.get("nobody"));
System.out.println("Users: " + emails.size());

georgiev@example.com
null
Users: 3

There are two type parameters: one for the key and one for the value. Map<String, String> is "from text to text".
put(key, value) puts in a pair, and get(key) returns the value.
A key that is not there gives null.
Map and HashMap are in java.util. Again, the interface is on the left, and the class is after new.

get does not loop over all the pairs. It finds the place of the key almost at once, no matter how many there are. How it does that is the next lesson.

The idea

The warehouse: changes and checks

The stock in a warehouse: item → count.

Map<String, Integer> stock = new HashMap<>();
stock.put("laptop", 4);
stock.put("mouse", 25);
stock.put("laptop", 3);

System.out.println(stock.get("laptop"));
System.out.println(stock.containsKey("monitor"));
System.out.println(stock.getOrDefault("monitor", 0));
stock.remove("mouse");
System.out.println(stock.size());

3
false
0
1

Keys are unique. The second put("laptop", 3) does not add a new row. It replaces 4 with 3.
containsKey asks whether the key is in the map.
getOrDefault(key, 0) returns the value, or 0 if the key is not there. This protects you from null.
remove(key) removes the pair.

More precisely, if you are curious

Values can repeat: the laptop and the mouse can both be 3. Keys cannot.
There is also containsValue. But it loops over all the values, because a dictionary is fast only by key.

Try it

How many are on the menu?

What will the program print?

Map<String, Integer> menu = new HashMap<>();
menu.put("coffee", 2);
menu.put("tea", 2);
menu.put("coffee", 3);
System.out.println(menu.size() + " " + menu.get("coffee"));

Answer

3 2

2 2

2 3

3 3

The idea

Looping and order

The delivery price by city. You loop over a dictionary in pairs with entrySet():

Map<String, Double> delivery = new HashMap<>();
delivery.put("Sofia", 4.5);
delivery.put("Plovdiv", 5.2);
delivery.put("Varna", 6.0);
delivery.put("Burgas", 6.0);
delivery.put("Ruse", 5.8);

for (Map.Entry<String, Double> e : delivery.entrySet()) {
    System.out.println(e.getKey() + ": €" + e.getValue());
}

Ruse: €5.8
Varna: €6.0
Sofia: €4.5
Plovdiv: €5.2
Burgas: €6.0

Ruse came out first, but Sofia was added first. HashMap promises no order at all. The order depends on the hash codes of the keys, which are the topic of the next lesson. Do not write code that relies on it.

When the order matters, change only the class after new:

LinkedHashMap keeps the order of adding. With the same put calls and System.out.println(delivery):

{Sofia=4.5, Plovdiv=5.2, Varna=6.0, Burgas=6.0, Ruse=5.8}

TreeMap sorts the keys:

Map<String, Double> delivery = new TreeMap<>();
delivery.put("Sofia", 4.5);
delivery.put("Plovdiv", 5.2);
delivery.put("Varna", 6.0);
delivery.put("Burgas", 6.0);
delivery.put("Ruse", 5.8);

System.out.println(delivery);

{Burgas=6.0, Plovdiv=5.2, Ruse=5.8, Sofia=4.5, Varna=6.0}

Map.Entry<String, Double> is one pair: getKey() and getValue(). There is a dot in the name because the type is declared inside Map. You will see types like this in the lesson "Classes inside classes".

More precisely, if you are curious

If you need only the keys, loop over keySet(). If you need only the values, loop over values():

for (String city : delivery.keySet()) {
    System.out.print(city + " ");
}
System.out.println();

double sum = 0;
for (double price : delivery.values()) {
    sum += price;
}
System.out.println("Average: €" + sum / delivery.size());

Ruse Varna Sofia Plovdiv Burgas
Average: €5.5

TreeMap is slower than HashMap, because it keeps the keys sorted. Use it when you need the order.
With the same keys, a HashMap in one version of Java usually prints in the same order. That is not a promise: the order can change with another version, with more elements or with a different number of buckets.

The idea

Counting

How many times was each item ordered? The key is the item, and the value is the count. At each order you take the old count (or 0) and add 1:

String orders = "coffee tea coffee cocoa coffee tea";
Map<String, Integer> counts = new TreeMap<>();
for (String item : orders.split(" ")) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts);

{cocoa=1, coffee=3, tea=2}

This is the most common use of a dictionary: counting words, votes, errors by type, sales by city. Here it is a TreeMap, so the items come out sorted.

String orders = "coffee tea coffee cocoa coffee tea";
Map<String, Integer> counts = new TreeMap<>();
for (String item : orders.split(" ")) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts);

Step by step, in words

6 orders and an empty TreeMap.
"coffee" is not there: getOrDefault gives 0, and put adds the key with 1.
"tea" is not there: getOrDefault gives 0, and put adds the key with 1.
"coffee" is already there: getOrDefault gives 1, and put replaces the value with 2.
"cocoa" is not there: getOrDefault gives 0, and put adds the key with 1. TreeMap puts it before "coffee": the keys are sorted.
"coffee" is already there: getOrDefault gives 2, and put replaces the value with 3.
"tea" is already there: getOrDefault gives 1, and put replaces the value with 2.
Each item is a key once, and the value is how many times it was ordered.

More precisely, if you are curious

split(" ") from the lesson on text splits the line into words.
In the "Modern Java" module you will see a shorter way to write the same thing, with the merge method.

Try it

Find the bug

The program should count the orders. Instead, it stops at the very first one:

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null

Which line has the bug?

Pick the line with the bug.

The first time, "coffee" is not there yet, and counts.get(item) returns null. To add up null + 1, Java has to unbox the Integer into an int, and there is nothing to unbox from null. The message says exactly that. The fix is counts.getOrDefault(item, 0) + 1.

The idea

HashSet: each one once

How many different people logged in to the site today? If someone logs in five times, they should be counted once. A collection that holds each value only once is called a set:

String[] visits = { "ana@example.com", "boris@example.com", "ana@example.com", "vera@example.com", "boris@example.com" };
Set<String> visitors = new HashSet<>();
for (String email : visits) {
    visitors.add(email);
}
System.out.println("Visits: " + visits.length);
System.out.println("Unique visitors: " + visitors.size());
System.out.println(visitors.contains("vera@example.com"));

Visits: 5
Unique visitors: 3
true

add on a value that is already in it does nothing and returns false. If it is new, it returns true.
contains is as fast as containsKey on a dictionary. Inside, a HashSet is a HashMap in which you keep only the keys.
There are no indexes. A set answers only the question "is it in here?".

More precisely, if you are curious

Here too, the order is not promised. LinkedHashSet keeps the order of adding, and TreeSet sorts:

Set<String> tags = new TreeSet<>();
tags.add("java");
tags.add("sql");
tags.add("git");
tags.add("java");
System.out.println(tags);

[git, java, sql]

retainAll keeps only the elements two sets have in common, and addAll joins them. You will need them in the exercise.

Try it

A duplicate invoice

The accountant wants to see the invoice numbers that were entered twice. Which method checks and adds at the same time?

String[] invoices = { "F-101", "F-102", "F-101", "F-103" };
Set<String> seen = new HashSet<>();
for (String number : invoices) {
    if (!seen.(number)) {
        System.out.println("Duplicate invoice: " + number);
    }
}

add returns false when the number is already in the set. So with one call you both check and remember. The program prints "Duplicate invoice: F-101".

Exercise

Dictionaries at work

Solve the tasks in your editor.

1. A user table. A UserTable class with the methods add(String username, String email), get(String username) and size(). Inside, it is a HashMap. Add ivanov, mpetrova and georgiev with emails in the form ivanov@example.com, and look up mpetrova and nobody. In the next lesson you will also build your own hash table, without HashMap.

mpetrova: mpetrova@example.com
nobody: no such user
Users: 3

2. Word frequency. Read a line of text, make it lowercase and count each word. Print the words in alphabetical order.

Coffee with milk and coffee without sugar and coffee

and: 2
coffee: 3
milk: 1
sugar: 1
with: 1
without: 1

3. Documents by keyword. A DocumentIndex class with the methods addDocument(int id, String... keywords) and search(String keyword), which returns a list of the numbers of the documents with that word. Inside, it is a Map<String, List<Integer>>: for each word, a list of documents. Add document 1 with "OOP" and "Java", document 2 with "SQL" and "databases", and document 3 with "Java" and "collections". Search for "Java", "SQL" and "Python".

Java: [1, 3]
SQL: [2]
Python: []

4. A contact network. A Contact class with a name and an email, and a ContactNetwork class with the methods addContact(String name, String email), addConnection(String a, String b) (the connection goes both ways), friendsOf(String name), common(String a, String b) (mutual friends) and emailOf(String name). Keep the contacts in a Map<String, Contact> and the connections in a Map<String, Set<String>>. Use a TreeSet so the names come out sorted. Connect Ivan with Maria and Ivan with Peter.

Ivan: [Maria, Peter]
Maria: [Ivan]
Mutual friends of Maria and Peter: [Ivan]
Peter's email: peter@example.com

More tasks

A unique ID. A method generateUserId(String email) gives each new email a number, U001, U002 and so on, and for an email it has already seen it returns the same number. Capital and lowercase letters in the email are treated the same. There is a version with a hash function in the next lesson.
A book catalog. The key is the ISBN, for example 978-954-28-0001-2, and the value is the title. Add books, look one up and print all of them, sorted by ISBN.
A trip planner. For each destination, keep a list of activities: "Paris" → "the Eiffel Tower", "the Louvre". Print the plan in the order the destinations were added. Which dictionary will you choose?
An online dictionary. Word → definition. Read words until "end" comes. For an unknown word, print "No such word."
Grades by subject. Read lines like "Math 6", "Physics 5", "Math 4", and print the average grade for each subject, sorted by name.

Test

Check yourself

1. When is a HashMap a better choice than a list?When the order of adding matters mostWhen you search by key, for example the email by usernameWhen you need the elements by number

2. The map already has the key "coffee" with the value 2. What does put("coffee", 3) do?It throws an exceptionIt replaces the value with 3; there is still one keyIt adds a second "coffee" key

3. What does get return for a key that is not there?It throws an exception0null

4. You print a HashMap. In what order do the keys come out?In the order of addingIn an order HashMap does not promiseIn alphabetical order

5. What does add on a HashSet return if the value is already in it?It throws an exceptionfalse, and it does not change the settrue, and it adds it a second time

HashMap and HashSet

Cookies