Structural sharing: reusar lo que no cambió

La objeción eterna contra la inmutabilidad es “copiar todo en cada cambio debe ser carísimo”. Es falsa, y entender por qué es el corazón de este nivel. Nunca copias todo: copias el camino desde la raíz hasta lo que cambió, y reutilizas —compartes por referencia— absolutamente todo lo demás. A esa técnica se le llama structural sharing, y es lo que hace que la inmutabilidad no sea solo elegante sino práctica. Es la diferencia entre pagar O(n) por cada actualización y pagar O(log n).

Copiar solo el camino que cambió

Imagina el estado como un árbol. Cuando actualizas una hoja profunda no necesitas un árbol nuevo entero: necesitas nodos nuevos solo en el camino que va de la raíz hasta esa hoja. Cada nodo de ese camino se copia superficialmente y apunta a los hijos que no cambiaron —que siguen siendo exactamente los mismos objetos de la versión anterior—. El resto del árbol se comparte intacto entre las dos versiones.

type Nodo = { valor: number; hijos: Record<string, Nodo> };

// Actualiza una hoja profunda copiando SOLO el camino raiz -> hoja.
function set(nodo: Nodo, camino: string[], valor: number): Nodo {
  if (camino.length === 0) return { ...nodo, valor };
  const [clave, ...resto] = camino;
  return {
    ...nodo,                                   // copia superficial: reusa hermanos
    hijos: { ...nodo.hijos, [clave]: set(nodo.hijos[clave], resto, valor) },
  };
}

const v0: Nodo = {
  valor: 0,
  hijos: {
    a: { valor: 1, hijos: {} },
    b: { valor: 2, hijos: { c: { valor: 3, hijos: {} } } },
  },
};

const v1 = set(v0, ["b", "c"], 99);
v1 === v0;                 // false -> raiz nueva
v1.hijos.a === v0.hijos.a; // true  -> la rama 'a' se COMPARTE
v1.hijos.b === v0.hijos.b; // false -> 'b' esta en el camino, se copio

La rama a no se tocó, así que v1.hijos.a y v0.hijos.a son el mismo objeto en memoria. Solo b y su descendiente c —el camino— estrenan identidad. Dos versiones completas del estado coexisten compartiendo la mayor parte de su estructura.

flowchart TD
R0[raiz v0] --> A[rama a]
R0 --> B0[rama b v0]
R1[raiz v1] --> A
R1 --> B1[rama b v1]
B0 --> C0[hoja c igual 3]
B1 --> C1[hoja c igual 99]
A --> A1[hoja a1]

Fíjate en el diagrama: raiz v1 reutiliza la misma rama a que raiz v0. Solo se crearon nodos nuevos a lo largo del camino hasta la hoja modificada. Los métodos inmutables de array siguen la misma lógica: crean un contenedor nuevo pero comparten los elementos que no reconstruiste.

const xs = [{ id: 1 }, { id: 2 }, { id: 3 }];
const ys = xs.map((x) => (x.id === 2 ? { ...x, marcado: true } : x));
ys === xs;         // false -> array nuevo
ys[0] === xs[0];   // true  -> el elemento 0 no cambio, se comparte
ys[1] === xs[1];   // false -> el elemento 1 se reemplazo

Por qué copiar no es tan caro

El miedo a la copia nace de imaginar una copia profunda —clonar recursivamente cada valor—. Pero la actualización inmutable usa copia superficial: { ...obj } crea un objeto nuevo con las mismas claves apuntando a los mismos valores. No copia los valores, copia las referencias. Copiar un objeto de mil claves es copiar mil punteros de ocho bytes: microsegundos.

const grande = Object.fromEntries(
  Array.from({ length: 1000 }, (_, i) => [`k${i}`, { pesado: new Array(1000) }]),
);
const copia = { ...grande, k0: { pesado: [] } };
// Se copiaron 1000 punteros, NO 1000 arrays de 1000 elementos.
copia.k1 === grande.k1;   // true -> los 999 valores no tocados se comparten

El coste de una actualización inmutable no depende del tamaño total del estado, sino del ancho de los nodos del camino y de la profundidad de ese camino. Si tu estado está bien estructurado —anidado en vez de un único objeto gigante y plano— cada actualización toca pocos nodos pequeños. El antídoto contra el coste no es abandonar la inmutabilidad: es normalizar y estructurar el estado para que los caminos sean cortos y los nodos estrechos.

El sharing tiene un segundo regalo, menos obvio: no solo abarata escribir, también abarata comparar. Una igualdad “profunda” puede cortarse en O(1) en cuanto dos ramas comparten referencia, porque compartir referencia implica ser idénticas.

// Igualdad estructural que se corta en O(1) cuando hay sharing.
function iguales(a: unknown, b: unknown): boolean {
  if (a === b) return true;               // misma referencia: subarbol identico
  if (typeof a !== "object" || !a || typeof b !== "object" || !b) return false;
  const ka = Object.keys(a), kb = Object.keys(b);
  if (ka.length !== kb.length) return false;
  return ka.every((k) => iguales((a as Record<string, unknown>)[k],
                                  (b as Record<string, unknown>)[k]));
}

La primera línea es la clave. En cuanto dos versiones comparten una rama entera, iguales la salta sin mirar dentro. El structural sharing convierte grandes porciones del árbol en comprobaciones de un solo puntero.

Tries: structural sharing a escala

¿Y si necesitas una colección de un millón de elementos con actualizaciones inmutables rápidas? Copiar un array de un millón en cada operación sí sería O(n). Aquí entran las estructuras persistentes de verdad: los bit-partitioned vector tries y los hash array mapped tries (HAMT) que usan Immutable.js, el runtime de Clojure y las librerías tipadas modernas.

La idea: en vez de un array plano, la colección es un árbol ancho —factor de ramificación 32— y poco profundo. Un millón de elementos cabe en un árbol de profundidad cuatro, porque 32 elevado a 4 supera el millón. Actualizar un elemento copia solo los nodos del camino: cuatro nodos de 32 referencias, unas 128 copias de puntero en vez de un millón. Por eso se dice que estas operaciones son O(log n) con base 32, es decir, efectivamente constantes para tamaños reales.

El factor 32 no es arbitrario. Cuanto mayor sea, menos profundo el árbol —menos saltos de puntero al leer— pero más grande cada nodo a copiar al escribir. Treinta y dos equilibra ambos y encaja con operaciones de bits sobre enteros, de ahí el nombre bit-partitioned: cinco bits del índice eligen la rama en cada nivel. La profundidad crece con una lentitud que asusta:

• Mil elementos caben en profundidad 2.
• Un millón, en profundidad 4.
• Mil millones, en apenas profundidad 6.

Seis saltos de puntero para llegar a cualquiera de mil millones de elementos, y una actualización toca solo esos seis nodos del camino.

flowchart TD
RT[raiz trie v1] --> N1[nodo 32 ramas]
RT --> N2[nodo 32 ramas compartido]
N1 --> H1[hojas 0 a 31]
N2 --> H2[hojas 32 a 63]
RT2[raiz trie v2] --> N1b[nodo 32 ramas nuevo]
RT2 --> N2
N1b --> H1b[hojas 0 a 31 con un cambio]

En el diagrama, la nueva raíz raiz trie v2 reutiliza intacto el subárbol nodo 32 ramas compartido y solo reconstruye la rama donde ocurrió el cambio. Un millón de elementos, y una actualización toca un puñado de nodos.