8. Map and Set

Remembering things about objects

You want to note which particles have already been hit. An object seems like a good place to keep notes, with bracket access from chapter 3:

const hit = {};
const a = { id: 1 };
const b = { id: 2 };

hit[a] = true;
console.log(hit[b]); // true ?!

b was never hit, yet the answer is true. A property name is always a string, so JavaScript first turns a into a string, and every plain object turns into the same string: '[object Object]'. So hit[a] and hit[b] are the same property. The same thing happens with numbers: hit[1] and hit['1'] are one property too.

What you need is a lookup table whose keys can be anything, kept exactly as they are.

Map

Map is a class, so you make one with new and use its methods:

const ages = new Map();
ages.set('ada', 36);
ages.set('alan', 41);

console.log(ages.get('ada'));  // 36
console.log(ages.get('bob'));  // undefined
console.log(ages.has('alan')); // true
console.log(ages.size);        // 2
ages.delete('alan');

Object keys are compared by identity, exactly like === in chapter 4. So the particle problem goes away:

const hit = new Map();
hit.set(a, true);
console.log(hit.has(a));        // true
console.log(hit.has(b));        // false
console.log(hit.has({ id: 1 })); // false

The last line is a lookalike, a different object, so it isn’t found.

Here is the most common Map job of all, counting:

const cs = ['red', 'blue', 'red'];
const counts = new Map();
for (let i = 0; i < cs.length; i++) {
  const c = cs[i];
  if (counts.has(c)) {
    counts.set(c, counts.get(c) + 1);
  } else {
    counts.set(c, 1);
  }
}
console.log(counts);
// Map(2) { 'red' => 2, 'blue' => 1 }

for…of

Notice the counting loop only uses i to fetch cs[i]. When you don’t care about the index, there’s a shorter loop.

for (const c of ['red', 'blue']) {
  console.log(c);
}

for (const entry of counts) {
  console.log(entry[0], entry[1]);
}
// red 2
// blue 1

Looping over a Map gives you each entry as a two-slot array: [key, value]. Entries come out in the order their keys were first added^[1]. You’ll often see this written for (const [k, v] of counts), a shorthand that unpacks the two slots into the names k and v.

Set

Sometimes there’s no value to store: you only want to know whether something is in the collection. That’s a Set.

const tags = new Set();
tags.add('fast');
tags.add('red');
tags.add('fast'); // already there

console.log(tags.size);       // 2
console.log(tags.has('red')); // true

const ids = new Set([3, 1, 3, 3, 2]);
console.log(ids); // Set(3) { 3, 1, 2 }

const a = { id: 1 };
const b = { id: 2 };

const hp = new Map();
hp.set(a, 100);
hp.set(b, 40);
hp.set(a, 90);
console.log(hp.get(a), hp.size);
console.log(hp.get({ id: 1 }));

for (const e of hp) {
  console.log(e[0].id, e[1]);
}

const s = new Set([3, 1, 3, 2, 1]);
console.log(s, s.has(2));

How can a lookup be fast?

To find 'pink' in an array of a million names, a loop checks name after name, a million in the worst case. A Map gets there almost directly, however many entries it holds. How?

// toy hash: (number of letters) % 4
m.set('red', 2);
m.set('blue', 1);
m.set('green', 5);
m.set('pink', 7);
m.get('green');
m.get('pink');
m.get('gold');

Your turn

function countEach(xs) {
  // your code here
}

const m = countEach(['a', 'b', 'a']);
console.log(m);

function firstRepeat(xs) {
  // your code here
}

const xs = [3, 1, 4, 1, 5, 3];
console.log(firstRepeat(xs));

What you learned

• Object property names are always strings, so objects make poor lookup tables for non-string keys.
• A Map stores key → value entries, with keys of any type, compared like ===. Use set, get, has, delete and size.
• A Set stores unique values. Use add, has, delete and size.
• for...of visits each value of an array, string, Map or Set, in order. Over a Map, each value is a [key, value] pair.
• Hashing turns a key into a bucket number, so a lookup checks one bucket instead of everything.

That’s the end of Day 2. Next: functions that call themselves, and the stack that keeps track of every call.