How Map and Set work

Problem

The seat was sold twice

The theater box office keeps the sold seats in a dictionary: seat → name of the customer. A seat is a class with a row and a number:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }
}

const bookings = new Map();
bookings.set(new Seat(5, 12), "Maria");

console.log(bookings.get(new Seat(5, 12)));
console.log(bookings.size);
bookings.set(new Seat(5, 12), "Ivan");
console.log(bookings.size);

Output

undefined
1
2

Maria bought seat 5/12, but get with the same seat returns undefined. Then Ivan buys the same seat, and the dictionary now has two 5/12 keys. Why?

The idea

Hash: a number from the key

A Map does not compare the key with all the others. It computes one whole number from the key, and from it, it knows where to look. This number is called a hash (hash code). JavaScript does not show it: the engine computes it, and there is no function that returns it. To see how it works, here is a hash function for text. The formula is the same as in Java:

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}

console.log(hashOf("Maria"));
console.log(hashOf("Maria"));
console.log(hashOf("Marie"));
console.log(hashOf("maria"));

Output

74113750
74113750
74113754
103666422

• The same text gives the same number, every time.
• A small change gives a different number: "Maria", "Marie" and "maria" are three different hashes.
• A hash is fast to compute, no matter how many keys are in the dictionary.
• charCodeAt(i) is the code of the character. | 0 keeps the result a 32-bit whole number, like int in Java. If it gets too big, it wraps around and can become negative.

A Map uses its own hash function, not this one. But the idea is the same.

The method that makes the number is called a hash function.

More precisely, if you are curious

• The formula is s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1], where s[i] is the code of each character. The loop computes it by multiplying by 31 at each step and adding the next code.

• Cryptographic hash functions like SHA-256 are something else. They give a long result, and it is practically impossible to find two texts with the same hash. That is why they are used to check that a file has not been tampered with and to store passwords. hashOf() is for fast lookups and gives no such protection.

See it

The buckets

Inside, a Map is an array of buckets. The number of the bucket for a key is the remainder of the hash divided by the number of buckets. The hash here comes from hashOf, because the one a Map uses is not visible:

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}

const keys = ["Boris", "Yana", "Ivan", "Emil"];
const buckets = 8;
for (const key of keys) {
  const hash = hashOf(key);
  const index = ((hash % buckets) + buckets) % buckets;
  console.log(`${key} -> ${hash} -> bucket ${index}`);
}

Step by step, in words

1. Four keys and eight empty buckets, numbered 0 to 7.
2. hashOf("Boris") is 64372111. The remainder when divided by 8 is 7: that is the bucket.
3. "Yana" gives 2748123, bucket 3.
4. "Ivan" gives 2291258, bucket 2.
5. "Emil" is also in bucket 3: a collision. The two keys are in one bucket: "Emil" hangs after "Yana" like a chain.
6. Looking up "Emil": the same number, the same bucket 3. === with "Yana": no. With "Emil": yes.

• set computes the bucket and puts the pair there. get computes the same bucket and looks only in it. That is why it is fast even with a million keys.
• % in JavaScript, as in Java, can give a negative number: -7 % 8 is -7. That is why it is ((hash % buckets) + buckets) % buckets: this way the remainder is never negative. A bucket number cannot be negative.
• "Yana" and "Emil" landed in bucket 3. This is called a collision. The next card is about it.

More precisely, if you are curious

• Exactly how a Map computes the bucket depends on the engine (V8 in Chrome and Node, a different one in Firefox). The language standard says only that a lookup must be faster on average than going through everything.

console.log(-7 % 8, ((-7 % 8) + 8) % 8);

Output

-7 1

Try it

Which bucket?

In your own hash table, the hash of a whole number is usually the number itself. The order numbers go into a dictionary with 4 buckets.

What will the program print?

const orderIds = [6, 10, 13, 21];
for (const id of orderIds) {
  console.log(`${id} -> bucket ${id % 4}`);
}

Answer

6 -> bucket 2
10 -> bucket 0
13 -> bucket 1
21 -> bucket 3

6 -> bucket 1
10 -> bucket 2
13 -> bucket 3
21 -> bucket 4

6 -> bucket 6
10 -> bucket 10
13 -> bucket 13
21 -> bucket 21

6 -> bucket 2
10 -> bucket 2
13 -> bucket 1
21 -> bucket 1

Check

The idea

Collision: the hash finds the bucket, comparing finds the key

Different keys can have the same hash. With hashOf, as with hashCode in Java, the best-known example is:

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}

console.log(hashOf("Aa"), hashOf("BB"));

const codes = new Map();
codes.set("Aa", 1);
codes.set("BB", 2);
console.log(codes.get("Aa"), codes.get("BB"));

Output

2112 2112
1 2

A Map keeps both keys and does not mix them up. It has its own hash function, and with it the collisions happen with other keys, but it is ready for them. A bucket holds several pairs, and get compares the key with each of them until it finds the one it wants.

So the two steps work like this:

1. The hash says which bucket to look in.
2. Comparing says which of the keys in the bucket is the one you want.

Now it is clear what happened with the theater seat. A Map compares keys almost like ===: text and numbers by value, but objects by reference. The two new Seat(5, 12) objects are two different objects, so they are also two different keys. A key that is the same object is found:

const seat = new Seat(5, 12);
const bookings = new Map();
bookings.set(seat, "Maria");
console.log(bookings.get(seat));

Output

Maria

The idea

No equals or hashCode: a key made of text

In Java and Python, the class says when two objects are equal (equals, __eq__) and what their hash is (hashCode, __hash__). In JavaScript there is no way to do this. Map and Set compare objects by reference and do not call your methods. Even if you write equals, the Map does not look at it:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }

  equals(other) {
    return other instanceof Seat && this.row === other.row && this.number === other.number;
  }
}

const bookings = new Map();
bookings.set(new Seat(5, 12), "Maria");

console.log(bookings.get(new Seat(5, 12)));
console.log(bookings.size);
bookings.set(new Seat(5, 12), "Ivan");
console.log(bookings.size);

Output

undefined
1
2

The usual solution is to make the key text, built from the fields that say which seat it is. Text is compared by value:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }

  key() {
    return `${this.row}/${this.number}`;
  }
}

const bookings = new Map();
bookings.set(new Seat(5, 12).key(), "Maria");

console.log(bookings.get(new Seat(5, 12).key()));
console.log(bookings.size);
bookings.set(new Seat(5, 12).key(), "Ivan");
console.log(bookings.size);

Output

Maria
1
1

The rules for a text key are the same as the contract in Java:

• Two objects that are the same seat give the same key. Always.
• Two different objects give different keys. That is what the slash between the fields is for.
• Only the fields that make two objects the same go into the key.

More precisely, if you are curious

• Without a separator, keys get mixed up: seat 51/2 and seat 5/12 both give "512".

console.log(`${51}${2}`, `${5}${12}`, `${51}/${2}` === `${5}/${12}`);

Output

512 512 false

• If you also need the object itself, put it in as the value: bookings.set(seat.key(), { seat, name: "Maria" }).

Try it

Find the bug

The catalog keeps the products in a Map with a text key. Two products with the same code are the same product, even if the price has changed. But has with the new price returns false:

const catalog = new Map();
const old = new Product("A-100", 25.0);
catalog.set(old.key(), old);
// The price went down, but it is the same product.
console.log(catalog.has(new Product("A-100", 19.9).key()));

Output

false

Which line in the class has the bug?

Pick the line with the bug.

1class Product {2 constructor(code, price) {3 this.code = code;4 this.price = price;5 }67 key() {8 return `${this.code}/${this.price}`;9 }10}

Check

The idea

The buckets fill up

When there are many pairs, the buckets get long and lookups slow down. That is why a Map grows:

• Inside, a Map also has to make more buckets when it fills up, and redistribute the keys to stay fast.
• Exactly when and by how much depends on the engine, and the program cannot see it.
• That is why, on average, set and get are fast, but now and then one set takes longer.

There is a trap too. A key must not change while it is in a dictionary or a set:

const seat = new Seat(5, 12);
const sold = new Set();
sold.add(seat.key());

seat.number = 13;
console.log(sold.has(seat.key()));
console.log(sold.has(new Seat(5, 12).key()));
console.log(sold.size);

Output

false
true
1

Here the trap is different. The set holds the text "5/12", and it does not change along with the object. After seat.number = 13 the key of seat is "5/13" and is not found, while "5/12" is still in the set, for a seat that is no longer sold to anyone. A text key is a snapshot of the object at the moment of add. That is why it is a good idea for the fields the key is made from not to change.

More precisely, if you are curious

• A key that is the object itself does not lose the object when it changes: the Map finds it by reference. But then new Seat(5, 12) is a different key. The choice is between "the same object" and "the same values".

Exercise

Your own keys

Solve the tasks in your editor.

1. A key for a person. A Person class with a first name, a last name and an age, and a key() method that makes a text key from the three fields. Create Ivan Petrov at 30 twice and once at 31. Print the keys and how many different people are left in a Map keyed by key().

Output

Ivan/Petrov/30
Ivan/Petrov/30
Ivan/Petrov/31
Different people: 2

2. The robot in the warehouse. The robot starts at cell (0, 0) and makes the moves NNEESWWN: N is up (y + 1), S is down, E is right (x + 1), W is left. How many different cells has it visited, counting the starting one? If you put objects of this class in a Set, the program says 9, but it should say 7. Fix it:

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

Output

Moves: 8
Different cells: 7

3. A hash of a file. A hashFileContent(filePath) function reads the file and returns the hash of its content as hexadecimal text. Use SHA-256 from the built-in node:crypto module: createHash("sha256").update(content).digest("hex"). Write three reports: a.txt and b.txt with "October report: €1250", and c.txt with "October report: €1260". Compare their hashes. Different hashes mean different files, and equal SHA-256 hashes in practice mean the same files.

Output

a.txt: 31c9db0c6cb9b9af7e6b355f9e6306b35281291f6a015049da01d1f6858bd293
b.txt: 31c9db0c6cb9b9af7e6b355f9e6306b35281291f6a015049da01d1f6858bd293
c.txt: cb9486eaca5007b8fef9f72a07411f78ed1fcd9a1fad3229c293ee3676024861
a and b: same
a and c: different

More tasks

• Your own hash table. A follow-up to the user table from the last lesson, this time without Map. Make an array of 8 buckets, each an array of username and email pairs. The hash function is the sum of the character codes in the name (charCodeAt). Write add, get, and a method that prints how many pairs are in each bucket.
• An ID from an email. generateUserId(email) returns "U" and the first 8 characters of the SHA-256 of the lowercase email. Is the ID the same for Ivan@Example.com and ivan@example.com? Can two different emails get the same ID? How would you find out?
• Counting collisions. Compute the bucket of the keys user1 … user1000 with hashOf from the lesson for 16, 64 and 1024 buckets, and count how many keys land in a bucket that already has a key.
• The shoe box. A Box class with a width, a height and a depth. Two boxes are the same if their sizes are the same, in the same order. Write key(), and check the boxes 30×20×10 and 10×20×30 in a Set.

Test

Check yourself

1. Why is get on a Map fast even with a million keys?

A Map keeps the keys sorted and searches by halvesA Map is a hash table: from the key it computes which bucket to look inA Map loops over the keys very fast

2. Two different keys have the same hash. What happens?

Both sit in one bucket, and comparing the keys tells them apartThe Map throws an errorThe second one deletes the first

3. The key is an object: bookings.set(new Seat(5, 12), "Maria"). What does bookings.get(new Seat(5, 12)) return?

undefined: a Map compares objects by reference, and this is a different object"Maria"It throws an error

4. You give Seat an equals(other) method that compares the row and the number. Will the Map use it?

Yes, a Map calls equals if it is thereOnly if Set has it tooNo: Map and Set do not call your methods, and there is no way to give them a different comparison

5. The key of the seat is the text `${row}/${number}`. Why is the slash needed?

A Map does not accept text without symbolsFor faster lookupsWithout it, seat 51/2 and seat 5/12 give the same key, "512"

6. The key() of a product is `${code}/${price}`, and the product is the same at a different price. What is wrong?

The key has a field that does not say which product it is: with a new price the key is different, and the product is not foundNothingThe price should come first

Check

Start the lesson over