Map: a labeled store of key → value

A Set stores plain values and tells you whether something is in the bag. A Map (also called a dictionary) can do more. It links each key to a value. You look up a key and get back whatever you stored under it.

Here is a task that needs it. You have many records like { id, type }. You want to sort them into buckets: all the ids of type "click" together, all the ids of type "view" together, and so on. You could read all the records again for each type, but that is a loop inside a loop, and it gets slow. It is better to read the records once and drop each id into the right bucket as you go. A Map gives you those buckets and finds each one by name in about one step.

Take the lesson's three records: a of type click, b of type view, c of type click. You want click → [a, c] and view → [b].

A Map does this in one read. Each type name is a key, and under each key lies a list of ids. Read a·click: there is no click key yet, so make one with an empty list and put a in it. Read b·view: make a view key and put b in its list. Read c·click: the click key is already there, so add c to its list. Each record was read once. Finding the right list took one step each time, with no search through the other lists.

A Map is a store of key → value pairs. Put a pair in: map.set(key, value). Read a value: map.get(key). Check whether a key is there: map.has(key). Remove it: map.delete(key). Ask for a key that was never set and you get undefined, which means "nothing is stored here".

For this task a Map is better than a plain object, for two reasons. First, a key can be anything (a number, a string, even another object), and the key keeps its type. A plain object would turn the number 30 into the text "30". Second, a Map remembers the order in which you added keys. So map.keys() gives the keys back in the order they first appeared. There is a third, smaller point. A plain object cannot safely store a key like "constructor", because every object already uses that name. A Map has no taken names.

Grouping uses a Map as a multimap: under each key lies a list, and you keep adding to it. The move is always the same. For each item, look at its key. If there is no list under that key yet, start an empty one. Then add the item to the list for its key.

Trace grouping on [a·click, b·view, c·click]. See a·click: no click list yet, so start one and add a, which gives click → [a]. See b·view: no view list yet, so start one and add b, which gives view → [b]. See c·click: the click list is already there, so add c, which gives click → [a, c]. One pass was enough. click comes before view because it appeared first.

Time is O(n): one pass over the records, and each has, get and set takes about one step. Memory is O(n): in the end each id sits in one of the lists once, plus one entry for each different key. There is no loop inside a loop and no second read. Sorting n records into buckets costs about as much as reading them.

Getting the keys with map.keys() costs O(k), where k is the number of different keys. They come back in the order they were first added, and they are not sorted.

Grouping by a key comes up in real code all the time. A log dashboard (a screen that shows a program's event records) sorts lines by severity, so each panel shows its own level. An analytics job first collects the events of each user or each session into a group, then computes something for each group. An order system groups items by warehouse to plan shipments. Every request of the form "group these by that" is the same map of lists built in one pass. In SQL it is GROUP BY, in a report it is the sections, in a user interface it is the blocks of a page. The simple form, one value per key, is everywhere too: a settings store, a cache (a fast copy of data kept at hand) of id → record, a table from code to label.