Data Structure & Algorithms
Uso de Map y Set para pertenencia, frecuencias, agrupación, deduplicación, complementos, memoization y diseño correcto de claves.
Map y Set expresan dos necesidades distintas:
Map<Key, Value> asocia una clave con información.Set<Value> registra pertenencia sin guardar un valor separado.Ambos suelen estar implementados con hashing y ofrecen operaciones promedio cercanas a O(1), pero su valor principal es permitir que el modelo del algoritmo sea explícito.
¿ya lo vi? → Set
¿cuántas veces aparece? → Map<value, count>
¿dónde apareció? → Map<value, index>
¿qué resultado calculé? → Map<state, result>Un objeto de JavaScript también asocia claves, pero tiene diferencias:
Map acepta claves de cualquier tipo;.size;has, get, set, delete;Un objeto puede ser apropiado para registros con campos conocidos:
type User = {
id: string;
name: string;
};Un Map es apropiado para claves variables:
const usersById = new Map<string, User>();Map y Set usan semántica SameValueZero:
NaN se considera igual a NaN;0 y -0 se consideran equivalentes;const set = new Set<object>();
set.add({ id: 1 });
set.has({ id: 1 }); // falseSon dos objetos diferentes. Para igualdad por contenido, usa una clave primitiva estable, por ejemplo id, o define una representación canónica.
Contar apariciones convierte búsquedas repetidas en una sola pasada.
function frequencies<T>(values: readonly T[]): Map<T, number> {
const counts = new Map<T, number>();
for (const value of values) {
counts.set(value, (counts.get(value) ?? 0) + 1);
}
return counts;
}Tiempo promedio: O(n). Memoria: O(k), donde k es la cantidad de valores distintos.
Este patrón aparece en:
function areAnagrams(a: string, b: string): boolean {
const left = [...a];
const right = [...b];
if (left.length !== right.length) return false;
const counts = new Map<string, number>();
for (const character of left) {
counts.set(character, (counts.get(character) ?? 0) + 1);
}
for (const character of right) {
const count = counts.get(character);
if (count === undefined) return false;
if (count === 1) {
counts.delete(character);
} else {
counts.set(character, count - 1);
}
}
return counts.size === 0;
}[...text] recorre code points, pero no normaliza Unicode. Una aplicación real debe decidir si é precompuesto y e + acento son equivalentes.
function unique<T>(values: readonly T[]): T[] {
return [...new Set(values)];
}Conserva la primera aparición según el orden de iteración del Set.
Para objetos por id:
function uniqueById<T extends { id: string }>(values: readonly T[]): T[] {
const seen = new Set<string>();
const result: T[] = [];
for (const value of values) {
if (seen.has(value.id)) continue;
seen.add(value.id);
result.push(value);
}
return result;
}Debes decidir si conserva el primero, el último o combina duplicados.
function twoSum(values: readonly number[], target: number): [number, number] | null {
const indexByValue = new Map<number, number>();
for (let index = 0; index < values.length; index += 1) {
const complement = target - values[index];
const complementIndex = indexByValue.get(complement);
if (complementIndex !== undefined) {
return [complementIndex, index];
}
indexByValue.set(values[index], index);
}
return null;
}Invariante: antes de procesar index, el mapa contiene valores de posiciones anteriores. Por eso nunca usa la misma posición dos veces.
Tiempo promedio: O(n). Memoria: O(n) peor caso.
Este patrón puede ser incorrecto:
if (map.get(key)) {
// Fails when the stored value is 0, false, or "".
}Usa:
if (map.has(key)) {
const value = map.get(key)!;
}O compara explícitamente con undefined solo si undefined no es un valor válido almacenado.
function groupBy<K, T>(
values: readonly T[],
keyOf: (value: T) => K,
): Map<K, T[]> {
const groups = new Map<K, T[]>();
for (const value of values) {
const key = keyOf(value);
const group = groups.get(key);
if (group) {
group.push(value);
} else {
groups.set(key, [value]);
}
}
return groups;
}Tiempo promedio O(n) más el costo de calcular la clave. Memoria O(n) para guardar referencias en grupos.
function intersection<T>(a: ReadonlySet<T>, b: ReadonlySet<T>): Set<T> {
const [small, large] = a.size <= b.size ? [a, b] : [b, a];
const result = new Set<T>();
for (const value of small) {
if (large.has(value)) result.add(value);
}
return result;
}Recorrer el conjunto menor reduce trabajo constante. Tiempo promedio: O(min(|a|, |b|)) lookups.
Otras operaciones:
Una ventana puede mantener un Map de caracteres dentro del segmento actual.
Al expandir:
count[incoming] += 1Al contraer:
count[outgoing] -= 1
si llega a 0, eliminar claveEliminar contadores en cero mantiene map.size igual a la cantidad real de valores distintos.
Memoization guarda el resultado de una función por estado.
function fibonacci(n: number, memo = new Map<number, bigint>()): bigint {
if (!Number.isInteger(n) || n < 0) {
throw new RangeError("n must be a non-negative integer");
}
if (n <= 1) return BigInt(n);
const cached = memo.get(n);
if (cached !== undefined) return cached;
const result = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
memo.set(n, result);
return result;
}Cada estado n se calcula una vez:
O(n);O(n);O(n).La clave debe incluir toda la información que cambia el resultado futuro.
Para un estado (index, remaining):
const key = `${index}:${remaining}`;Esto es sencillo, pero debes evitar ambigüedades y costo excesivo de serialización. Para estados anidados, puedes usar Map<number, Map<number, Result>>.
Objetos como claves funcionan solo si reutilizas la misma identidad. Crear { index, remaining } en cada llamada no produce hits aunque los campos sean iguales.
Memoization suele referirse a resultados puros dentro de un algoritmo. Una cache de aplicación añade problemas:
No conviertas un ejemplo algorítmico en una garantía de diseño de sistemas.
Una LRU cache necesita:
Map para lookup promedio O(1);O(1);Este ejemplo muestra que combinar estructuras permite cumplir varias operaciones simultáneamente.
Solo aceptan objetos como claves y no impiden que el garbage collector libere esas claves. No son iterables porque su contenido puede desaparecer según reachability.
Útiles para:
No sirven cuando necesitas enumerar entradas o conocer tamaño.
Las operaciones de Map y Set suelen ser promedio o amortizadas cercanas a O(1). El estándar del lenguaje define comportamiento observable, no exige una implementación concreta de hash table ni garantiza peor caso constante.
Incluye en el análisis:
0 válido;NaN;get por truthiness.new Set(objects) cuando se necesita id.O(1) con garantía absoluta.Set responde pertenencia; Map, asociación.has y get responden preguntas diferentes.¿Por qué new Set([{ id: 1 }, { id: 1 }]).size devuelve 2?
Porque los objetos se comparan por identidad. Aunque tengan los mismos campos, son dos referencias distintas. Para deduplicar por id, debes almacenar esa clave o usar un Map indexado por ella.