← Estructuras de datos desde cero · Lección 14/32
Map y Set: las tablas hash de JavaScript
Map: clave → valor
No hace falta escribir tu propia tabla: JavaScript trae Map, que es exactamente eso. set mete, get saca, has pregunta y delete borra, todas en O(1) promedio.
Un objeto {} también guarda pares, pero sus claves siempre se vuelven texto y trae propiedades heredadas. Map acepta cualquier clave (números, objetos), recuerda el orden en que entraron y sabe su tamaño con size. Para datos que cambian, usa Map.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
- El tamal vale 20 y el
Maptiene 2 elementos, no 3. Object.keysdevuelve'1'entre comillas: el objeto convirtió el número en texto.- El
Mapdistingue1de"1": con el texto no encuentra nada.
Toda la lección en una página
Map: clave → valor
No hace falta escribir tu propia tabla: JavaScript trae Map, que es exactamente eso. set mete, get saca, has pregunta y delete borra, todas en O(1) promedio.
Un objeto {} también guarda pares, pero sus claves siempre se vuelven texto y trae propiedades heredadas. Map acepta cualquier clave (números, objetos), recuerda el orden en que entraron y sabe su tamaño con size. Para datos que cambian, usa Map.
const precios = new Map();
precios.set("tamal", 18);
precios.set("atole", 22);
precios.set("tamal", 20); // misma clave: se reemplaza
console.log(precios.get("tamal"));
console.log(precios.has("champurrado"));
console.log(precios.size);
console.log(precios);
// Con un objeto, la clave 1 se vuelve el texto "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"));
- El tamal vale 20 y el
Maptiene 2 elementos, no 3. Object.keysdevuelve'1'entre comillas: el objeto convirtió el número en texto.- El
Mapdistingue1de"1": con el texto no encuentra nada.
Set: ¿está o no está?
Un Set es una tabla hash sin valores: sólo claves, y cada una una vez. Sirve para dos cosas que salen todo el tiempo:
- Quitar repetidos:
[...new Set(arr)]. - Preguntar si algo ya se vio, en O(1), dentro de un ciclo.
Con eso, «¿hay repetidos?» se contesta en una pasada: si el conjunto queda más chico que el arreglo, algo se repitió.
const visitas = ["Ana", "Beto", "Ana", "Caro", "Beto", "Ana"];
const unicos = new Set(visitas);
console.log(unicos);
console.log([...unicos]);
console.log("¿hubo repetidos?", unicos.size < visitas.length);
// El primero que se repite, en una sola pasada
const vistos = new Set();
for (const nombre of visitas) {
if (vistos.has(nombre)) {
console.log("primer repetido:", nombre);
break;
}
vistos.add(nombre);
}
- El
Setse queda con tres nombres, en el orden en que aparecieron por primera vez. - Como 3 < 6, sí hubo repetidos.
- El ciclo se detiene en la tercera vuelta: «Ana» ya estaba en
vistos.
Contar y agrupar
El patrón más útil de todo el curso cabe en una línea: contar frecuencias con m.set(x, (m.get(x) ?? 0) + 1). El ?? 0 pone cero cuando la clave aún no existe.
Y una variante: agrupar por una clave calculada. Dos palabras son anagramas si tienen las mismas letras; si ordenas sus letras, las dos dan la misma clave ("amor" y "roma" → "amor"). Así se agrupan en una pasada, sin comparar cada palabra con todas las demás.
// Contar letras
const cuenta = new Map();
for (const letra of "banana") {
cuenta.set(letra, (cuenta.get(letra) ?? 0) + 1);
}
console.log(cuenta);
// Agrupar anagramas: la clave es la palabra con sus letras ordenadas
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»: tres
a, dosny unab. - Salen tres grupos: amor/roma/mora, saco/cosa y luna sola. Cada palabra se tocó una vez.
Two Sum: guardar lo que te falta
Un clásico de entrevista: dado un arreglo y un objetivo, encuentra las posiciones de dos números que sumen el objetivo. Con dos ciclos es O(n²). Con un Map es O(n):
Al ver cada número x, preguntas si ya viste a su complemento objetivo - x. Si sí, ahí está la pareja; si no, guardas x con su posición y sigues. Cambias memoria por tiempo, que es casi siempre lo que hace una tabla hash.
function dosSuma(nums, objetivo) {
const vistos = new Map(); // número -> posición
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. Al llegar al 7, el 2 ya estaba guardado.[1, 2]: 2 + 4. El 3 no se usa con él mismo, porque se pregunta antes de guardarlo.nullcuando no hay pareja.