Map and Set

Problem

Who is this user?

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

function findEmail(users, username) {
  for (const u of users) {
    if (u.username === 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 JavaScript the dictionary is Map:

const emails = new Map();
emails.set("ivanov", "ivanov@example.com");
emails.set("mpetrova", "mpetrova@example.com");
emails.set("georgiev", "georgiev@example.com");

console.log(emails.get("georgiev"));
console.log(emails.get("nobody"));
console.log(`Users: ${emails.size}`);

georgiev@example.com
undefined
Users: 3

new Map() is an empty dictionary. set(key, value) puts in a pair, and get(key) returns the value.
A key that is not there gives undefined.
size is the number of pairs. You write it without parentheses: it is a property, not a method.

In JavaScript a plain object {} also looks like a dictionary: stock[key] = value. A lot of code uses it that way, but there are traps:

const stock = {};
stock[1] = "laptop";
stock["1"] = "mouse";
console.log(stock);
console.log("toString" in stock);

const map = new Map();
map.set(1, "laptop");
map.set("1", "mouse");
console.log(map);
console.log(map.has("toString"));

{ '1': 'mouse' }
true
Map(2) { 1 => 'laptop', '1' => 'mouse' }
false

The keys of an object always become text: 1 and "1" are one key, and "mouse" replaced "laptop".
The object also has keys you never put in: toString comes from the shared prototype of all objects.
A Map keeps the type of the key, and it holds only what you put in. For a dictionary, use Map.

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.

const stock = new Map();
stock.set("laptop", 4);
stock.set("mouse", 25);
stock.set("laptop", 3);

console.log(stock.get("laptop"));
console.log(stock.has("monitor"));
console.log(stock.get("monitor") ?? 0);
stock.delete("mouse");
console.log(stock.size);

3
false
0
1

Keys are unique. The second set("laptop", 3) does not add a new row. It replaces 4 with 3.
has asks whether the key is in the map.
get(key) ?? 0 gives the value, or 0 if the key is not there. a ?? b is a, unless a is undefined or null: then it is b. This protects you from undefined.
delete(key) removes the pair.

More precisely, if you are curious

Values can repeat: the laptop and the mouse can both be 3. Keys cannot.
Map has no "is this value in it" method. You have to loop over values(), because a dictionary is fast only by key.

Try it

How many are on the menu?

What will the program print?

const menu = new Map();
menu.set("coffee", 2);
menu.set("tea", 2);
menu.set("coffee", 3);
console.log(menu.size, menu.get("coffee"));

Answer

3 3

2 2

2 3

3 2

The idea

Looping and order

The delivery price by city. for...of over a Map gives [key, value] pairs, and const [city, price] splits each one into two names:

const delivery = new Map();
delivery.set("Sofia", 4.5);
delivery.set("Plovdiv", 5.2);
delivery.set("Varna", 6.0);
delivery.set("Burgas", 6.0);
delivery.set("Ruse", 5.8);

for (const [city, price] of delivery) {
  console.log(`${city}: €${price.toFixed(2)}`);
}

Sofia: €4.50
Plovdiv: €5.20
Varna: €6.00
Burgas: €6.00
Ruse: €5.80

The cities come out in the order they were added. Map keeps the order of adding, and this is promised. toFixed(2) prints the price with two digits: otherwise 6.0 comes out as 6.

When you need alphabetical order, take the keys into an array and sort it. The Map does not change:

const delivery = new Map();
delivery.set("Sofia", 4.5);
delivery.set("Plovdiv", 5.2);
delivery.set("Varna", 6.0);
delivery.set("Burgas", 6.0);
delivery.set("Ruse", 5.8);

for (const city of Array.from(delivery.keys()).sort()) {
  console.log(`${city}: €${delivery.get(city).toFixed(2)}`);
}

Burgas: €6.00
Plovdiv: €5.20
Ruse: €5.80
Sofia: €4.50
Varna: €6.00

More precisely, if you are curious

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

console.log(Array.from(delivery.keys()).join(" "));

let sum = 0;
for (const price of delivery.values()) {
  sum += price;
}
console.log(`Average: €${(sum / delivery.size).toFixed(2)}`);

Sofia Plovdiv Varna Burgas Ruse
Average: €5.50

Array.from(...) makes an array from the keys, so that you have join and sort.
A plain object also keeps the order of adding, but not always: keys that look like whole numbers come out first, sorted as numbers.

const rooms = {};
rooms["Hall"] = "free";
rooms["12"] = "taken";
rooms["3"] = "free";
console.log(Object.keys(rooms));

[ '3', '12', 'Hall' ]

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:

const orders = "coffee tea coffee cocoa coffee tea";
const counts = new Map();
for (const item of orders.split(" ")) {
  counts.set(item, (counts.get(item) ?? 0) + 1);
}
console.log(counts);

Map(3) { 'coffee' => 3, 'tea' => 2, 'cocoa' => 1 }

This is the most common use of a dictionary: counting words, votes, errors by type, sales by city. The items come out in the order they were first seen. The parentheses around counts.get(item) ?? 0 are needed: without them, + 1 is computed before ??, and the count of an item already seen does not grow.

const orders = "coffee tea coffee cocoa coffee tea";
const counts = new Map();
for (const item of orders.split(" ")) {
  counts.set(item, (counts.get(item) ?? 0) + 1);
}
console.log(counts);

Step by step, in words

6 orders and an empty Map.
"coffee" is not there: get gives undefined, ?? turns it into 0, and set adds the key with 1.
"tea" is not there: get gives undefined, ?? turns it into 0, and set adds the key with 1. A Map keeps the order of adding: the new key is last.
"coffee" is already there: get gives 1, and set replaces the value with 2.
"cocoa" is not there: get gives undefined, ?? turns it into 0, and set adds the key with 1. A Map keeps the order of adding: the new key is last.
"coffee" is already there: get gives 2, and set replaces the value with 3.
"tea" is already there: get gives 1, and set 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.
JavaScript has no ready-made counter. Writing it with get, ?? 0 and set is the usual way.

Try it

Find the bug

The program should count the orders. It does not stop and shows no error, but instead of counts it prints this:

Map(2) { 'coffee' => NaN, 'tea' => NaN }

Which line has the bug?

Pick the line with the bug.

The first time, "coffee" is not there yet, and counts.get(item) returns undefined. undefined + 1 is NaN ("not a number"), and NaN + 1 is still NaN. JavaScript does not stop, so you see the error only in the output. The fix is (counts.get(item) ?? 0) + 1.

The idea

Set: 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:

const visits = ["ana@example.com", "boris@example.com", "ana@example.com", "vera@example.com", "boris@example.com"];
const visitors = new Set();
for (const email of visits) {
  visitors.add(email);
}
console.log(`Visits: ${visits.length}`);
console.log(`Unique visitors: ${visitors.size}`);
console.log(visitors.has("vera@example.com"));

Visits: 5
Unique visitors: 3
true

add on a value that is already in it does nothing. In both cases it returns the set itself, so it does not tell you whether it added anything:

const seen = new Set();
console.log(seen.add("F-101") === seen);

true

has is as fast as has on a Map. size is the number of values.
There are no indexes. A set answers only the question "is it in here?".

More precisely, if you are curious

A Set keeps the order of adding, like a Map. You can also make one all at once from an array, and Array.from turns it back into an array, for example for sort():

const tags = new Set(["java", "sql", "git", "java"]);
console.log(tags);
console.log(Array.from(tags).sort());

const backend = new Set(["java", "sql", "docker"]);
console.log(tags.intersection(backend));
console.log(tags.union(backend));

Set(3) { 'java', 'sql', 'git' }
[ 'git', 'java', 'sql' ]
Set(2) { 'java', 'sql' }
Set(4) { 'java', 'sql', 'git', 'docker' }

intersection keeps only the elements two sets have in common, and union joins them. You will need them in the exercise. They are new: Node has had them since version 22, and browsers since 2024.

Try it

A duplicate invoice

The accountant wants to see the invoice numbers that were entered twice. Which method asks whether the number is already in the set?

const invoices = ["F-101", "F-102", "F-101", "F-103"];
const seen = new Set();
for (const number of invoices) {
  if (seen.(number)) {
    console.log(`Duplicate invoice: ${number}`);
  }
  seen.add(number);
}

seen.has(number) asks whether the number has been seen already. add says nothing, so first you ask, then you 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(username, email), get(username) and size(). Inside, it is a Map. 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 Map.

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(id, ...keywords) and search(keyword), which returns an array of the numbers of the documents with that word. Inside, it is a Map of arrays: for each word, an array 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", and print the numbers in [], separated by commas.

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(name, email), addConnection(a, b) (the connection goes both ways), friendsOf(name), common(a, b) (mutual friends) and emailOf(name). Keep the contacts in a Map name → Contact, and the connections in a Map name → Set of names. friendsOf and common return a sorted array. 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 function generateUserId(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 array of activities: "Paris" → "the Eiffel Tower", "the Louvre". Print the plan in the order the destinations were added. Do you need anything more than a plain Map?
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 Map a better choice than an array?When you need the elements by numberWhen you search by key, for example the email by usernameWhen you need repeated values one after another

2. The Map menu already has the key "coffee" with the value 2. What does menu.set("coffee", 3) do?It throws an errorIt 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 error0undefined

4. You print a Map. In what order do the keys come out?In a different order every timeIn the order of addingIn alphabetical order

5. In a plain object stock you write stock[1] = "laptop" and then stock["1"] = "mouse". How many keys does stock have?Zero: numbers are not keysTwo: the number 1 and the text "1"One: "1", with the value "mouse"

6. What does add on a Set return if the value is already in it?true, and it adds it a second timeIt throws an errorThe set itself, without changing it

Map and Set

Cookies