Una tabla hash como contador
En resumen: Un mapa usado como contador (Map en JavaScript) cuenta cuántas veces aparece cada elemento en una sola pasada: O(n) en lugar de O(n²) al buscar en una lista.
Problema
Los productos más vendidos del día
El panel de la tienda muestra los tres productos más vendidos del día. El registro es una lista de pedidos, uno por línea. El código mantiene dos listas, los nombres y los contadores, y para cada pedido busca el producto desde el principio de los nombres:
const log = logOf(1000);const names = [];const counts = [];let comparisons = 0;for (const item of log) { let i = 0; while (i < names.length) { comparisons++; if (names[i] === item) break; i++; } if (i === names.length) { names.push(item); counts.push(1); } else { counts[i]++; }}console.log(`pedidos: ${log.length}`);console.log(`productos: ${names.length}`);console.log(`comparaciones: ${comparisons}`);pedidos: 1000productos: 251comparaciones: 125255Mil pedidos y 251 productos distintos: 125 255 comparaciones. El catálogo crece con la tienda, y con él la lista que recorre cada pedido. En un día grande con 100 000 pedidos el panel tarda minutos en cargar.
De dónde viene el registro
El registro sigue una fórmula, para que los programas en los cuatro lenguajes y la comparación del navegador de más abajo construyan exactamente el mismo. El catálogo tiene n / 4 + 1 productos:
function logOf(n) { const catalog = Math.floor(n / 4) + 1; return Array.from({ length: n }, (_, i) => `SKU-${(i * 7919) % catalog}`);}La idea
El mapa cuenta
En la lección «Map y Set» contaste pedidos con un mapa. Aquí se convierte en una técnica: una tabla hash como contador (un mapa de frecuencias). La clave es lo que cuentas, el valor es cuántas veces lo has visto.
- Una pasada por los datos. Para cada elemento: encontrar su contador (o 0) y sumar 1.
- La búsqueda se hace en una tabla hash: O(1) en promedio, sean cuales sean los productos. En total O(n) en lugar de O(n · m).
- Después respondes las preguntas con los contadores, no con los datos: cuál es el más frecuente, cuál aparece una vez, si dos cosas tienen los mismos contadores.
La memoria es O(m): un par por cada producto distinto.
Míralo
El contador se llena
const log = [ "ratón", "audífonos", "ratón", "monitor", "teclado", "ratón", "audífonos", "monitor", "ratón", "audífonos",];const counts = new Map();for (const item of log) { counts.set(item, (counts.get(item) ?? 0) + 1);}const top = [...counts].sort((x, y) => y[1] - x[1]);for (const [item, n] of top.slice(0, 3)) { console.log(item, n);}ratón 4audífonos 3monitor 2const counts = new Map();for (const item of log) { counts.set(item, (counts.get(item) ?? 0) + 1);}const top = [...counts].sort((x, y) => y[1] - x[1]);for (const [item, n] of top.slice(0, 3)) { console.log(item, n);}Paso a paso, en palabras
- Un mapa vacío: producto → cuántas veces se vendió. El registro tiene 10 pedidos.
- Pedido 1: ratón. Todavía no está en el mapa, así que recibe un contador de 1.
- Pedido 2: audífonos. Todavía no está en el mapa, así que recibe un contador de 1.
- Pedido 3: ratón, 1 → 2. Una búsqueda en la tabla hash, sin recorrer los demás productos.
- Pedido 4: monitor. Todavía no está en el mapa, así que recibe un contador de 1.
- Pedido 5: teclado. Todavía no está en el mapa, así que recibe un contador de 1.
- Pedido 6: ratón, 2 → 3. Una búsqueda en la tabla hash, sin recorrer los demás productos.
- Pedido 7: audífonos, 1 → 2. Una búsqueda en la tabla hash, sin recorrer los demás productos.
- Pedido 8: monitor, 1 → 2. Una búsqueda en la tabla hash, sin recorrer los demás productos.
- Pedido 9: ratón, 3 → 4. Una búsqueda en la tabla hash, sin recorrer los demás productos.
- Pedido 10: audífonos, 2 → 3. Una búsqueda en la tabla hash, sin recorrer los demás productos.
- 10 pedidos, 10 actualizaciones del contador. Se ordenan solo los 4 productos distintos por contador, no los pedidos.
- Los tres primeros: ratón 4, audífonos 3, monitor 2.
counts.get(item) ?? 0 da 0 para un producto que todavía no está. Los paréntesis alrededor son necesarios: sin ellos + 1 se calcula antes que ??. Los tres primeros salen de ordenar los pares por contador: se ordenan solo los productos distintos, no los pedidos.
Pruébalo
Completa
La línea que cuenta:
counts.set(item, (counts.get(item) 0) + 1);?? da 0 cuando get devuelve undefined para un producto que todavía no está.Míralo
Las herramientas de tu lenguaje
JavaScript no tiene un contador ya hecho. Un Map con get, ?? 0 y set es la forma habitual. Un objeto normal también funciona, pero tiene claves heredadas ("constructor", "toString") y convierte cada clave en texto. Un Map recorre sus claves en el orden en que se insertaron:
const log = [ "ratón", "audífonos", "ratón", "monitor", "teclado", "ratón", "audífonos", "monitor", "ratón", "audífonos",];const counts = new Map();for (const item of log) counts.set(item, (counts.get(item) ?? 0) + 1);console.log(counts.get("ratón"), counts.get("tableta") ?? 0);for (const [item, n] of counts) console.log(item, n);4 0ratón 4audífonos 3monitor 2teclado 1Míralo
Mídelo: una lista de pares frente a un mapa
Los mismos mil pedidos con el mapa:
const log = logOf(1000);const counts = new Map();let updates = 0;for (const item of log) { counts.set(item, (counts.get(item) ?? 0) + 1); updates++;}console.log(`pedidos: ${log.length}`);console.log(`productos: ${counts.size}`);console.log(`actualizaciones del contador: ${updates}`);pedidos: 1000productos: 251actualizaciones del contador: 10001000 actualizaciones en lugar de 125 255 comparaciones. Ejecuta las dos en el navegador. n es el número de pedidos, y el catálogo crece con él:
- Una lista de pares de producto y cantidad
O(n²) - Un mapa como contador
O(n)
| Algoritmo | n = 10 | n = 1000 | n = 100.000 |
|---|---|---|---|
| Una lista de pares de producto y cantidad | 16 | 125.255 | ≈ 1.252.550.000 |
| Un mapa como contador | 10 | 1000 | 100.000 |
const counts = new Map();for (const item of log) { counts.set(item, (counts.get(item) ?? 0) + 1);}const top = [...counts].sort((x, y) => y[1] - x[1]);for (const [item, n] of top.slice(0, 3)) { console.log(item, n);}Más precisamente, para curiosos
Los k primeros sin ordenarlo todo. Ordenar m productos distintos es O(m log m). Si hay millones de productos y necesitas los 10 primeros, mantienes un heap con como máximo k pares: cada par entra, y cuando hay k + 1 sale el más pequeño. Eso es O(m log k).
Una clave con varias partes. Cuentas ventas por ciudad y producto: la clave es el par. En JavaScript un Map compara los objetos por referencia, así que la clave es texto: `${city}|${item}`.
La idea
El carrito y el kit
El kit «oficina en casa» es un monitor, un teclado, un ratón y dos cables. El almacén comprueba que el carrito que se va a enviar es exactamente el kit: nada de más, nada de menos. El orden no importa, los contadores sí.
Un contador: +1 por cada producto del kit, −1 por cada producto del carrito. El carrito coincide si todos los contadores terminan en 0.
function matches(kit, basket) { const need = new Map(); for (const item of kit) need.set(item, (need.get(item) ?? 0) + 1); for (const item of basket) need.set(item, (need.get(item) ?? 0) - 1); return [...need.values()].every((n) => n === 0);}La misma comprobación encuentra anagramas: «listen» y «silent» tienen las mismas letras con los mismos contadores. El contador es sobre letras en lugar de productos.
Pruébalo
Predice la comprobación
const kit = [ "monitor", "teclado", "ratón", "cable", "cable",];const basket1 = [ "cable", "ratón", "monitor", "cable", "teclado",];const basket2 = [ "monitor", "teclado", "ratón", "ratón", "cable",];console.log(`carrito 1: ${matches(kit, basket1) ? "kit completo" : "no coincide"}`);console.log(`carrito 2: ${matches(kit, basket2) ? "kit completo" : "no coincide"}`);El primer carrito tiene los mismos cinco productos en otro orden: cada contador pasa a 0. El segundo tiene dos ratones y un cable: el ratón se queda en −1, el cable en +1, así que no coincide, aunque sean cinco productos.
La idea
El primer cliente con un solo pedido
Marketing envía un vale de «vuelve» a los clientes que pidieron una sola vez. Quiere al primero en el tiempo. El contador da los contadores, pero no el orden:
function firstSingle(customers) { const counts = new Map(); for (const c of customers) counts.set(c, (counts.get(c) ?? 0) + 1); for (const c of customers) { if (counts.get(c) === 1) return c; } return null;}const customers = [ "C-17", "C-4", "C-17", "C-9", "C-4", "C-21", "C-9", "C-30",];console.log(`primer cliente con un solo pedido: ${firstSingle(customers)}`);primer cliente con un solo pedido: C-21Dos pasadas: la primera cuenta, la segunda recorre el registro, en el orden de los pedidos, y se detiene en el primero con contador 1. O(n), sin bucle anidado.
Más precisamente, para curiosos
¿Por qué la segunda pasada recorre el registro y no el mapa? Un Map recorre en el orden de inserción (garantizado por la especificación), así que aquí recorrer counts daría la misma respuesta. El registro sigue siendo más claro: el orden viene de él.
La idea
Dos productos por exactamente 50 €
El cliente tiene un vale de exactamente 50 € y quiere dos productos que lo agoten. Los precios del catálogo no están ordenados.
Recorres los precios y para cada uno preguntas: ¿he visto ya el precio que completa este hasta 50? El mapa guarda los precios vistos hasta ahora y sus posiciones:
function voucherPair(prices, voucher) { const seen = new Map(); for (let i = 0; i < prices.length; i++) { const j = seen.get(voucher - prices[i]); if (j !== undefined) return [j, i]; seen.set(prices[i], i); } return null;}const prices = [27, 14, 33, 25, 8, 36, 19];const [a, b] = voucherPair(prices, 50);console.log(`productos ${a} y ${b}: ${prices[a]} € + ${prices[b]} €`);productos 1 y 5: 14 € + 36 €Una pasada: O(n) de tiempo y O(n) de memoria. Con dos punteros funciona sin mapa, con memoria O(1), pero los precios tienen que estar ordenados. Si no lo están, ordenar cuesta O(n log n) y se pierde la posición de cada producto en el catálogo. Así que: datos ordenados, dos punteros; datos sin ordenar, un mapa.
Pruébalo
Encuentra el error
Alguien intercambió dos líneas. Ahora, para un vale de 50 €, el programa ofrece un producto dos veces:
const prices = [27, 14, 33, 25, 8, 36, 19];const [a, b] = voucherPair(prices, 50);console.log(`productos ${a} y ${b}: ${prices[a]} € + ${prices[b]} €`);productos 3 y 3: 25 € + 25 €Elige la línea con el error.
El precio entra en el mapa antes de buscar su pareja. El producto de 25 € busca 50 − 25 = 25 y se encuentra a sí mismo. La escritura debe ir después de la búsqueda: entonces el mapa contiene solo los productos anteriores al actual, y el programa encuentra 14 € + 36 €.
Ejercicio
Quién gasta más
Resuelve la tarea en tu propio editor.
Ingresos por cliente. El registro tiene pares de cliente e importe: C-4 con 30 €, C-17 con 55 €, C-4 con 20 €, C-9 con 80 €, C-17 con 10 € y C-4 con 45 €. Suma los importes por cliente con un mapa (el valor es una suma, no un contador) e imprime los dos que más gastaron:
C-4: 95 €C-9: 80 €Más tareas
- Anagramas. Escribe una comprobación de si dos palabras son anagramas («listen» y «silent») contando las letras con un mapa. ¿Cuántas operaciones necesita para palabras de longitud n?
- La primera repetición. Encuentra el primer pedido cuyo cliente ya había pedido antes. ¿Necesitas un contador o basta un conjunto?
- Periodos con contadores iguales. Con las sumas prefijas sabes contar periodos con una suma dada. Cuenta los periodos de días consecutivos en los que el número de pedidos devueltos es igual al de entregados.
Test