← Data structures from scratch · Lesson 14/32
Map and Set: JavaScript's hash tables
Map: key → value
You don't need to write your own table: JavaScript ships Map, which is exactly that. set puts, get takes, has asks and delete removes, all O(1) on average.
A plain object {} also stores pairs, but its keys always turn into strings and it comes with inherited properties. Map accepts any key (numbers, objects), remembers insertion order and knows its size with size. For data that changes, use Map.
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
- The tamal is 20 and the
Mapholds 2 items, not 3. Object.keysreturns'1'in quotes: the object turned the number into a string.- The
Maptells1and"1"apart: with the string it finds nothing.
The whole lesson on one page
Map: key → value
You don't need to write your own table: JavaScript ships Map, which is exactly that. set puts, get takes, has asks and delete removes, all O(1) on average.
A plain object {} also stores pairs, but its keys always turn into strings and it comes with inherited properties. Map accepts any key (numbers, objects), remembers insertion order and knows its size with size. For data that changes, use Map.
const precios = new Map();
precios.set("tamal", 18);
precios.set("atole", 22);
precios.set("tamal", 20); // same key: replaced
console.log(precios.get("tamal"));
console.log(precios.has("champurrado"));
console.log(precios.size);
console.log(precios);
// With an object, the key 1 turns into the string "1"
const obj = {};
obj[1] = "uno";
console.log(Object.keys(obj));
const m = new Map([[1, "uno"]]);
console.log(m.get(1), m.get("1"));
- The tamal is 20 and the
Mapholds 2 items, not 3. Object.keysreturns'1'in quotes: the object turned the number into a string.- The
Maptells1and"1"apart: with the string it finds nothing.
Set: is it there or not?
A Set is a hash table without values: just keys, each one once. It's good for two things that come up all the time:
- Removing duplicates:
[...new Set(arr)]. - Asking whether you've seen something already, in O(1), inside a loop.
With that, "are there duplicates?" is answered in one pass: if the set ends up smaller than the array, something repeated.
const visitas = ["Ana", "Beto", "Ana", "Caro", "Beto", "Ana"];
const unicos = new Set(visitas);
console.log(unicos);
console.log([...unicos]);
console.log("any duplicates?", unicos.size < visitas.length);
// The first one to repeat, in a single pass
const vistos = new Set();
for (const nombre of visitas) {
if (vistos.has(nombre)) {
console.log("first duplicate:", nombre);
break;
}
vistos.add(nombre);
}
- The
Setkeeps three names, in the order they first appeared. - Since 3 < 6, there were duplicates.
- The loop stops on the third turn: "Ana" was already in
vistos.
Counting and grouping
The most useful pattern of the whole course fits on one line: counting frequencies with m.set(x, (m.get(x) ?? 0) + 1). The ?? 0 puts a zero when the key doesn't exist yet.
And a variant: grouping by a computed key. Two words are anagrams if they have the same letters; if you sort their letters, both give the same key ("amor" and "roma" → "amor"). That way they group in one pass, without comparing each word with all the others.
// Count letters
const cuenta = new Map();
for (const letra of "banana") {
cuenta.set(letra, (cuenta.get(letra) ?? 0) + 1);
}
console.log(cuenta);
// Group anagrams: the key is the word with its letters sorted
const palabras = ["amor", "roma", "saco", "mora", "cosa", "luna"];
const grupos = new Map();
for (const p of palabras) {
const clave = [...p].sort().join("");
if (!grupos.has(clave)) grupos.set(clave, []);
grupos.get(clave).push(p);
}
console.log([...grupos.values()]);
- "banana": three
a, twonand oneb. - Three groups come out: amor/roma/mora, saco/cosa and luna alone. Each word was touched once.
Two Sum: remember what you're missing
An interview classic: given an array and a target, find the positions of two numbers that add up to the target. With two loops it's O(n²). With a Map it's O(n):
When you see each number x, ask whether you've already seen its complement objetivo - x. If so, there's the pair; if not, store x with its position and move on. You trade memory for time, which is almost always what a hash table does.
function dosSuma(nums, objetivo) {
const vistos = new Map(); // number -> position
for (let i = 0; i < nums.length; i++) {
const falta = objetivo - nums[i];
if (vistos.has(falta)) return [vistos.get(falta), i];
vistos.set(nums[i], i);
}
return null;
}
console.log(dosSuma([2, 7, 11, 15], 9));
console.log(dosSuma([3, 2, 4], 6));
console.log(dosSuma([1, 2], 10));
[0, 1]: 2 + 7 = 9. When the 7 arrives, the 2 is already stored.[1, 2]: 2 + 4. The 3 isn't paired with itself, because you ask before storing it.nullwhen there's no pair.