bastianplsfix

← JavaScript + TypeScript

A Map maps keys to values. Any value can be a key, any value can be a value, and the map knows its own size and its own order. Four methods do almost all the work: get, set, has, and delete.

The one thing to internalise before using a Map for anything real is how keys are compared: primitives by value, objects by identity. Two objects that look alike are two different keys, and no amount of matching contents changes that; get it wrong and you build a map that quietly never finds anything. Whether to reach for a Map at all rather than a plain object is a separate question, and the objects as dictionaries page answers it from the other side in a Map when the keys are data. The short version: a Map for anything keyed at run time.

Create programs/maps.test.ts for this reference and keep it open. Start it with the assertion helpers used on this page:

import {
  assert,
  assertEquals,
  assertFalse,
  assertStrictEquals,
} from "@std/assert";

Follow the page as you add and revise the runnable examples below that import.

three ways to make one

Deno.test("three ways to make one", () => {
  const empty = new Map<string, number>();
  assertStrictEquals(empty.size, 0);

  const fromPairs = new Map([["one", 1], ["two", 2]]);

  const chained = new Map<string, number>()
    .set("one", 1)
    .set("two", 2);

  assertEquals(fromPairs, chained);
});

Check programs/maps.test.ts
running 1 test from ./programs/maps.test.ts
three ways to make one ... ok (266µs)

ok | 1 passed | 0 failed (1ms)

Empty, from an iterable of [key, value] pairs, or by chaining set, which returns the map it was called on, which is why it chains. The annotations on the empty and chained versions are not decoration, and a later step measures what happens without them.

the four methods that do the work

Deno.test("the four methods that do the work", () => {
  const prices = new Map<string, number>();

  prices.set("apple", 150);
  assertStrictEquals(prices.get("apple"), 150);
  assertStrictEquals(prices.get("pear"), undefined);

  assert(prices.has("apple"));
  assertStrictEquals(prices.delete("apple"), true);
  assertStrictEquals(prices.delete("apple"), false);
  assertFalse(prices.has("apple"));

  prices.set("plum", 90).set("fig", 220);
  assertStrictEquals(prices.size, 2);
  prices.clear();
  assertStrictEquals(prices.size, 0);
});

the four methods that do the work ... ok (50µs)

get on a key that is not there gives undefined rather than complaining, and the next step is why that is convenient. delete reports whether it removed anything, which is occasionally useful and easy to ignore. And size is a property rather than a method, a count the map keeps itself: an array's length is the highest index plus one and says nothing about how many elements exist, from the arrays page's arrays can have holes, while size is a genuine count.

counting is the pattern to learn first

Deno.test("counting is the pattern to learn first", () => {
  function countCharacters(text: string): Map<string, number> {
    const counts = new Map<string, number>();
    for (const character of text.toLowerCase()) {
      counts.set(character, (counts.get(character) ?? 0) + 1);
    }
    return counts;
  }

  assertEquals(
    countCharacters("Anna"),
    new Map([["a", 2], ["n", 2]]),
  );
});

counting is the pattern to learn first ... ok (41µs)

counts.get(character) ?? 0 is the whole idiom: read what is there or start from nothing, then write it back. Almost every real use of a Map contains this line in some form, and it is why get returning undefined is convenient rather than annoying, since ?? turns the absence into a starting value by the rule the nothing, twice page pinned in ?? treats only null and undefined as missing. For the case where the value is a container rather than a number there is now a shorter way, two steps down.

keys are compared with SameValueZero

Deno.test("keys are compared with SameValueZero", () => {
  const keyed = new Map<number, string>();

  keyed.set(NaN, "not a number");
  assertStrictEquals(keyed.get(NaN), "not a number");

  keyed.set(0, "zero").set(-0, "negative zero");
  assertStrictEquals(keyed.size, 2);
  assertStrictEquals(keyed.get(0), "negative zero");

  const origin = { x: 0 };
  const byPoint = new Map([[origin, "here"]]);
  assertStrictEquals(byPoint.get(origin), "here");
  assertStrictEquals(byPoint.get({ x: 0 }), undefined);
});

keys are compared with SameValueZero ... ok (53µs)

Three pins, all inherited from pages already visited. NaN finds itself, because a Map compares keys with SameValueZero rather than ===, the algorithm the equality page named in collections compare with SameValueZero, and this is the one place in the language where looking for NaN works. The two zeros are one key under the same algorithm, which is why the map holds two entries rather than three and why the second write replaced the first zero's value. And two objects that look alike are two keys, the identity rule the values and references page ran as a prediction in Map keys compare by identity: origin finds its entry, and a fresh { x: 0 } finds nothing.

The last pin is the mistake that makes people give up on Map. If your keys are conceptually values, a coordinate or a date range, build a string from the identifying fields and key on that, since primitives compare by value. If your keys are genuinely objects whose lifetime you do not control, the right tool is a WeakMap, from the weak collections page.

the read-or-create dance collapses into one line

Deno.test("the read-or-create dance collapses into one line", () => {
  function groupByInitial(words: string[]): Map<string, string[]> {
    const groups = new Map<string, string[]>();
    for (const word of words) {
      groups.getOrInsertComputed(word[0], () => []).push(word);
    }
    return groups;
  }

  function groupByInitialOlder(words: string[]): Map<string, string[]> {
    const groups = new Map<string, string[]>();
    for (const word of words) {
      const bucket = groups.get(word[0]) ?? [];
      bucket.push(word);
      groups.set(word[0], bucket);
    }
    return groups;
  }

  const words = ["ada", "grace", "alan"];
  assertEquals(groupByInitial(words), groupByInitialOlder(words));
  assertEquals(
    groupByInitial(words),
    new Map([["a", ["ada", "alan"]], ["g", ["grace"]]]),
  );

  let built = 0;
  const cache = new Map<string, number>([["k", 1]]);
  assertStrictEquals(
    cache.getOrInsertComputed("k", () => {
      built++;
      return 2;
    }),
    1,
  );
  assertStrictEquals(built, 0);
});

the read-or-create dance collapses into one line ... ok (138µs)

Two implementations of the same function. The older one is the three-line dance you will keep reading for years, because it is what all existing code does: get the bucket or a fresh one, push into it, set it back. getOrInsertComputed(key, compute) returns the value stored under the key, or, when there is none, calls compute, stores the result, and returns that, so for a value that is a container the dance collapses into one line and the temporary name disappears. The cache measurement is what makes this safe for something expensive: the callback runs only on a miss, so built stayed at zero when the key was already there. getOrInsert(key, value) is the eager sibling, for a value cheap enough to build whether or not it is needed. Both methods are recent, and both exist on WeakMap too.

getOrInsert keys on presence, ?? keys on value

Deno.test("getOrInsert keys on presence, ?? keys on value", () => {
  const holds = new Map<string, number | undefined>([["k", undefined]]);

  assertStrictEquals(holds.getOrInsert("k", 9), undefined);
  assertStrictEquals(holds.size, 1);
  assertStrictEquals(holds.get("k") ?? 9, 9);

  const viaGetOrInsert = new Map<string, number>();
  const viaNullish = new Map<string, number>();
  for (const character of "aab") {
    viaGetOrInsert.set(character, viaGetOrInsert.getOrInsert(character, 0) + 1);
    viaNullish.set(character, (viaNullish.get(character) ?? 0) + 1);
  }
  assertEquals(viaGetOrInsert, viaNullish);
  assertEquals(viaGetOrInsert, new Map([["a", 2], ["b", 1]]));
});

getOrInsert keys on presence, ?? keys on value ... ok (46µs)

An entry whose value is undefined is an entry. getOrInsert sees it and keeps it, where get("k") ?? 9 sees a nullish value and replaces it, so the two disagree exactly when a map stores nothing on purpose, the distinction the nothing, twice page is built around. The counter loop is the other caveat: same length, same result, and the getOrInsert line writes twice, storing the zero and then overwriting it with set. The win is for values you mutate in place, which means arrays, sets, and maps. For a number, keep ?? 0.

insertion order, and the edge of it

Every listing operation walks the entries in the order they were created, and the specification guarantees it. Setting a key that already exists updates the value in place. Predict what deleting a key and setting it again does to the order:

Deno.test("insertion order, and the edge of it", () => {
  const updated = new Map([["a", 1], ["b", 2]]);
  updated.set("a", 99);
  assertEquals(updated.keys().toArray(), ["a", "b"]);

  const reinserted = new Map([["a", 1], ["b", 2], ["c", 3]]);
  reinserted.delete("a");
  reinserted.set("a", 9);
  assertEquals(reinserted.keys().toArray(), ["a", "b", "c"]);
});

Check programs/maps.test.ts
running 7 tests from ./programs/maps.test.ts
...
insertion order, and the edge of it ... FAILED (7ms)

 ERRORS

insertion order, and the edge of it => ./programs/maps.test.ts:131:6
error: AssertionError: Values are not equal.

    [Diff] Actual / Expected

    [
+     "a",
      "b",
      "c",
-     "a",
    ]

 FAILURES

insertion order, and the edge of it => ./programs/maps.test.ts:131:6

FAILED | 6 passed | 1 failed (9ms)

error: Test failed

Two writes to "a", two different outcomes. updated.set("a", 99) found an existing entry, changed the value, and kept the position. reinserted.set("a", 9) found nothing, because the delete had removed the entry, so it created a new one, and a new entry goes at the end. Nothing in the API hints at the difference, which means a function that refreshes a key by removing and re-adding it silently reorders your data. Correct the prediction to ["b", "c", "a"]:

insertion order, and the edge of it ... ok (30µs)

The reason the order exists at all is determinism, mostly so that tests and output are reproducible. That is a claim this file makes concretely: every assertion against a whole Map in this entry relies on it.

iterating a map is iterating its entries, literally

Deno.test("iterating a map is iterating its entries, literally", () => {
  assertStrictEquals(Map.prototype[Symbol.iterator], Map.prototype.entries);

  const map = new Map([["a", 1], ["b", 2]]);

  const pairs: string[] = [];
  for (const [key, value] of map) {
    pairs.push(`${key}=${value}`);
  }
  assertEquals(pairs, ["a=1", "b=2"]);

  assertEquals(map.keys().toArray(), ["a", "b"]);
  assertEquals(map.values().toArray(), [1, 2]);
  assertEquals(Array.from(map.entries()), [["a", 1], ["b", 2]]);
});

iterating a map is iterating its entries, literally ... ok (58µs)

The first assertion is stronger than the usual description: Symbol.iterator is not equivalent to entries, it is entries, the same function object. So for (const [key, value] of map) and for (... of map.entries()) are the same call, with the pair taken apart in the head by the pattern the destructuring page covers. The three views return iterators rather than arrays, which is why .toArray() and Array.from both work on them and why every method from the iterator helpers page is available there, a fact the transforming step below builds on.

forEach reverses the pair

A Map iterates as [key, value]. Write the forEach callback in the same order:

Deno.test("forEach reverses the pair", () => {
  const seen: string[] = [];

  new Map([["k", "v"]]).forEach((key, value) => {
    seen.push(`key=${key} value=${value}`);
  });

  assertEquals(seen, ["key=k value=v"]);
});

Check programs/maps.test.ts
running 9 tests from ./programs/maps.test.ts
...
forEach reverses the pair ... FAILED (7ms)

 ERRORS

forEach reverses the pair => ./programs/maps.test.ts:160:6
error: AssertionError: Values are not equal.

    [Diff] Actual / Expected

    [
-     "key=v value=k",
+     "key=k value=v",
    ]

 FAILURES

forEach reverses the pair => ./programs/maps.test.ts:160:6

FAILED | 8 passed | 1 failed (9ms)

error: Test failed

The names are backwards: forEach hands its callback (value, key), the opposite order from iteration, and nothing warned about it because both parameters are strings. The order matches Array.prototype.forEach, where value-then-index is right, and that consistency is presumably the reason. Swap the names:

Deno.test("forEach reverses the pair", () => {
  const seen: string[] = [];

  new Map([["k", "v"]]).forEach((value, key) => {
    seen.push(`value=${value} key=${key}`);
  });

  assertEquals(seen, ["value=v key=k"]);
});

forEach reverses the pair ... ok (24µs)

It is still a trap, and one more argument for for-of on top of the one the loops page gives in .forEach() cannot stop.

transforming means convert, transform, rebuild

Deno.test("transforming means convert, transform, rebuild", () => {
  const source = new Map([[1, "a"], [2, "b"], [3, "c"]]);

  const doubled = new Map(
    source.entries().map(([key, value]) => [key * 2, `_${value}`]),
  );
  assertEquals(doubled, new Map([[2, "_a"], [4, "_b"], [6, "_c"]]));

  const small = new Map(source.entries().filter(([key]) => key < 3));
  assertEquals(small, new Map([[1, "a"], [2, "b"]]));

  const alsoDoubled = new Map(
    Array.from(source).map(([key, value]) => [key * 2, `_${value}`]),
  );
  assertEquals(alsoDoubled, doubled);
});

transforming means convert, transform, rebuild ... ok (55µs)

There is no map or filter on a Map, and there does not need to be. Three steps: take the entries iterator, transform it, hand the result to new Map. It works because the constructor accepts any iterable of pairs and a helper returns an iterator, so nothing is materialised in between, the laziness the iterator helpers page measured in nothing happens until something pulls. For older code the same three steps go through an array, as alsoDoubled shows, and the shape is identical either way.

combining is a spread, and later wins

Deno.test("combining is a spread, and later wins", () => {
  const first = new Map([[1, "1a"], [2, "1b"]]);
  const second = new Map([[2, "2b"], [3, "2c"]]);

  const combined = new Map([...first, ...second]);

  assertEquals(combined.entries().toArray(), [
    [1, "1a"],
    [2, "2b"],
    [3, "2c"],
  ]);
});

combining is a spread, and later wins ... ok (24µs)

No method exists for merging maps, and the spread does it: flatten both into an array of pairs and rebuild. Two things happen to the shared key, and only one of them is obvious. The value comes from the later map, like a later set. The position comes from the earlier one, because that is where the key was first inserted, and a set on an existing key keeps its position: the edge from the insertion-order step, showing up where you would not think to look for it.

a copy shares the values

Deno.test("a copy shares the values", () => {
  const shared = { count: 1 };
  const original = new Map([["k", shared]]);
  const copy = new Map(original);

  assertStrictEquals(copy.get("k"), original.get("k"));
  copy.get("k")!.count = 2;
  assertStrictEquals(shared.count, 2);

  copy.set("added", { count: 0 });
  assertStrictEquals(original.size, 1);
});

a copy shares the values ... ok (27µs)

new Map(original) gives a new map holding the same keys and the same values, where the same means the very same objects. Adding an entry to the copy leaves the original alone; changing an object reached through the copy changes the one object both maps hold. The ordinary shallow-copy story, from the values and references page's spread copies one level, wearing a Map constructor.

objects and maps convert both ways

A Map full of string keys looks one call away from JSON. Predict the serialised text:

Deno.test("objects and maps convert both ways", () => {
  const map = new Map([["a", 1], ["b", 2]]);

  assertStrictEquals(JSON.stringify(map), '{"a":1,"b":2}');
});

Check programs/maps.test.ts
running 13 tests from ./programs/maps.test.ts
...
objects and maps convert both ways ... FAILED (8ms)

 ERRORS

objects and maps convert both ways => ./programs/maps.test.ts:217:6
error: AssertionError: Values are not strictly equal.

    [Diff] Actual / Expected

-   {}
+   {"a":1,"b":2}

 FAILURES

objects and maps convert both ways => ./programs/maps.test.ts:217:6

FAILED | 12 passed | 1 failed (10ms)

error: Test failed

Two characters came out. JSON.stringify of a Map is "{}", silently, because a map keeps its entries somewhere stringify does not look: serialisation reads own enumerable properties, and entries are not properties. There is no error and no warning, which files it with the other quiet JSON loss, the nothing, twice page's JSON keeps null and loses undefined. Convert first, every time. Pin the conversions in both directions:

Deno.test("objects and maps convert both ways", () => {
  const map = new Map([["a", 1], ["b", 2]]);

  assertStrictEquals(JSON.stringify(map), "{}");
  assertStrictEquals(JSON.stringify(Object.fromEntries(map)), '{"a":1,"b":2}');

  assertEquals(Object.fromEntries(map), { a: 1, b: 2 });
  assertEquals(new Map(Object.entries({ a: 1, b: 2 })), map);
});

objects and maps convert both ways ... ok (41µs)

Object.fromEntries takes any iterable of pairs, and a map is one, so the way out is a single call. Object.entries gives pairs back, so the way in is too. Both directions need the keys to be strings, because a property key is text, from the objects as dictionaries page's any string can be a key. And if a Map is part of something you serialise regularly, that is a real argument for holding a plain object instead.

get is honest, and an unannotated Map is not

Ask for a price you can see, and use it:

Deno.test("get is honest, and an unannotated Map is not", () => {
  const prices = new Map([["apple", 150]]);

  const price = prices.get("apple");
  assertStrictEquals(price.toFixed(0), "150");
});

Check programs/maps.test.ts
TS18048 [ERROR]: 'price' is possibly 'undefined'.
  assertStrictEquals(price.toFixed(0), "150");
                     ~~~~~
    at file:///programs/maps.test.ts:232:22

error: Type checking failed.

get returns V | undefined and the checker holds you to it, even for a key visible one line up. That is the right behaviour, and a pleasant contrast with arr[0], which the arrays page caught typing an element as always there in the checker is optimistic about brackets. Handle it with ?? for a default, ?. for a chain, or a narrowing check when the absence means something.

The honesty has a hole, and it opens at the constructor. Write the chained style the documentation encourages, in a scratch file programs/chained-any.ts:

const loose = new Map().set("apple", 150);
const price: string = loose.get("apple");
console.log(price);

const tight = new Map<string, number>().set("apple", 150);
const alsoPrice: string = tight.get("apple");
console.log(alsoPrice);

Check programs/chained-any.ts
TS2322 [ERROR]: Type 'number | undefined' is not assignable to type 'string'.
  Type 'undefined' is not assignable to type 'string'.
const alsoPrice: string = tight.get("apple");
      ~~~~~~~~~
    at file:///programs/chained-any.ts:6:7

error: Type checking failed.

new Map() with no arguments and no annotation is Map<any, any>, and chaining set onto it does not repair that, so line 2 assigns a number to a string and nobody objects: everything coming out of an any map is any. The annotated tight map is the same code with the hole closed, and the checker catches the same assignment immediately. Delete the scratch file, and pin both the handled reads and the lie:

Deno.test("get is honest, and an unannotated Map is not", () => {
  const prices = new Map([["apple", 150]]);

  assertStrictEquals(prices.get("apple")?.toFixed(0), "150");
  assertStrictEquals(prices.get("pear") ?? 0, 0);

  const price = prices.get("apple");
  if (price !== undefined) {
    assertStrictEquals(price.toFixed(0), "150");
  }

  const loose = new Map().set("apple", 150);
  const lying: string = loose.get("apple");
  assertStrictEquals(typeof lying, "number");
});

get is honest, and an unannotated Map is not ... ok (27µs)

The lying line is the runtime truth: the annotation says string, the value is a number, and the assertion passes because any silenced the one tool that could have said so. Annotate the constructor, or build from a literal of pairs, where the types are inferred correctly.

build an index when you look things up more than once

Deno.test("build an index when you look things up more than once", () => {
  type Entry = { id: number; name: string };

  function indexById(entries: Iterable<Entry>): Map<number, Entry> {
    return new Map(
      Iterator.from(entries).map((entry) => [entry.id, entry]),
    );
  }

  const entries = [{ id: 7, name: "Ada" }, { id: 9, name: "Grace" }];
  const byId = indexById(entries);

  assertStrictEquals(byId.get(9)?.name, "Grace");
  assertStrictEquals(byId.get(7), entries[0]);
  assertStrictEquals(byId.get(8), undefined);

  const words = ["orange", "apple", "avocado"];
  assertEquals(
    Map.groupBy(words, (word) => word[0]),
    new Map([["o", ["orange"]], ["a", ["apple", "avocado"]]]),
  );
});

build an index when you look things up more than once ... ok (44µs)

Repeatedly scanning an array with find is the thing a Map replaces, and indexById is the four lines that do it: one pass to build, then every lookup is a get. Iterator.from is what turns a plain Iterable into something with map on it, the adapter from the iterator helpers page's Iterator.from turns an iterable into an iterator, needed because the parameter promises only the protocol. The values are the original objects, as the identity assertion shows, so the index is a view rather than a copy. And when the lookup you want is a grouping, Map.groupBy already exists, from the objects as dictionaries page's grouping is the same choice, made for you, keyed here on a first letter and returning its buckets in first-seen order.

In practice

• Annotate an empty constructor, such as new Map<string, number>(); let a literal of pairs infer its types.
• Read with get(key) ?? fallback. Use has separately only when the map deliberately stores undefined.
• Iterate with for-of to receive [key, value] in insertion order and retain the ability to break.
• Use getOrInsertComputed for a mutable bucket, and ?? 0 for a counter.
• Transform by converting, transforming, and rebuilding; merge maps with a spread.
• Convert a map before serializing it because JSON.stringify otherwise produces an empty object.

Related

• Sets covers collections of members rather than key-value entries.
• Weak collections covers object keys that should not be kept alive by the collection.