Entendendo o algoritmo de Diffing

“Diffing” vem de diff, que significa “diferença”.
É o processo de comparar duas versões de algo para descobrir o que mudou.

Nos frameworks modernos como React e Vue, esse “algo” é o Virtual DOM, uma cópia leve do DOM real, guardada na memória.

Como o processo funciona:

O estado muda, por exemplo, um contador vai de 1 para 2.
O framework cria uma nova versão do Virtual DOM com esse novo valor.
Ele compara (faz o diffing) entre o novo e o antigo Virtual DOM.
Descobre o que mudou, ou seja, só o número 1 → 2.
Atualiza apenas esse pedacinho no DOM real, sem recarregar tudo.

Você não precisa mexer direto no DOM.
O framework faz isso automaticamente, de forma rápida e eficiente, atualizando só o que realmente mudou.

Por que não comparar tudo?

Porque o DOM é enorme e lento.
Imagine um app com centenas de componentes, cada um com dezenas de elementos.
Comparar todos os nós de árvore entre duas versões seria absurdamente caro.

Tecnicamente, essa comparação completa teria complexidade O(n³). ou seja, se o DOM dobrar de tamanho, o custo cresce exponencialmente.

O navegador travaria a cada pequeno update.

Como os frameworks tornam isso viável

React e Vue usam heurísticas, regras simples que funcionam na maioria dos casos e tornam a comparação quase linear (O(n)).

Essas regras são:

Tipos diferentes?
<div> virou <p> → destrói o antigo e cria um novo.
(Não tenta comparar banana com maçã.)
Tipos iguais?
<div> continua <div> → compara atributos e filhos.
(Se a className mudou, atualiza só isso.)
Mudanças locais.
A maioria das alterações está em partes pequenas da árvore, então ele não percorre tudo.

Essas simplificações deixam o algoritmo rápido o suficiente para rodar dezenas de vezes por segundo sem travar nada.

Visualizando o processo

Imagine o componente:

function App() {
  return (
    <ul>
      <li>Amanda</li>
      <li>Lucas</li>
      <li>João</li>
    </ul>
  )
}

Agora o estado muda, e o React precisa renderizar isso:

<ul>
  <li>Amanda</li>
  <li>João</li>
  <li>Lucas</li>
</ul>

Como ele sabe que Amanda ainda está lá, mas Lucas e João trocaram de lugar?

👉 A resposta está na key.

O papel da `key`

A key é como o RG de cada elemento numa lista, uma identidade única.

Ela diz ao React/Vue “quem é quem” dentro da lista.

🚫 Sem `key` (ou usando índice como `key`)


<ul>
  {['Amanda', 'Lucas', 'João'].map((n, i) => <li key={i}>{n}</li>)}
</ul>

O que acontece? O framework identifica os itens pela posição, não pelo conteúdo.

Imagine esta lista:

Índice	Nome	Key
0	Amanda	0
1	Lucas	1
2	João	2

Agora você insere "Marina" no topo:

['Marina', 'Amanda', 'Lucas', 'João']

O React/Vue agora cria uma nova árvore virtual:

Índice	Nome	Key
0	Marina	0
1	Amanda	1
2	Lucas	2
3	João	3

E então ele compara a árvore antiga e a nova (isso é o diffing).

💥 Veja o que o React/Vue pensa:

“O elemento com key=0 ainda existe, ele só mudou de conteúdo (Amanda → Marina).
Então, não preciso criar um novo nó, só atualizar o texto.”

Isso parece inteligente… mas o React/Vue não entende o contexto da mudança, apenas vê que a key continua igual.

👉 Então ele reutiliza o mesmo nó <li> do antigo “Amanda” e só troca o texto interno para “Marina”.

Resultado:

O DOM real ainda é o mesmo elemento,
Qualquer estado, foco, ou animação desse elemento permanece,
Mesmo que agora ele “represente” outra pessoa.

Onde isso dá problema

Imagine que cada <li> tem um <input> dentro:


<li key={i}><input defaultValue={name} /></li>

Se o React/Vue acha que é o mesmo nó, ele não cria um novo input.
Ele só muda o valor, mas o campo e o estado interno continuam.

➡️ Então o que era o input de “Amanda” agora vira o input de “Marina”, com o texto digitado anteriormente ainda lá.
Parece mágica bugada 😅

✅ Com `key` (usando um id único)

Se você usa key={name} ou key={user.id}, o React/Vue vê isso assim:

key	valor
"Amanda"	Amanda
"Lucas"	Lucas
"João"	João

Quando você adiciona “Marina”, o React/Vue percebe:

“Opa, existe uma nova key (‘Marina’) que não estava antes.
Então preciso criar um novo nó real no DOM para ela.
Os outros permanecem iguais.”

Agora, o React/Vue adiciona só o necessário, sem bagunçar o resto.

Em resumo

Situação	O que o React/Vue faz	Consequência
`key = index`	Reutiliza o mesmo nó mesmo que o conteúdo mude	Bug visual e perda de estado
`key = id` (ou valor único)	Identifica cada nó de forma estável	Atualiza apenas o que mudou, com segurança

A mágica do LIS (Longest Increasing Subsequence) - Como o framework “descobre” o que pode reaproveitar

Quando uma lista muda de ordem (por exemplo, o usuário arrasta itens, reordena cards, ou o backend retorna em outra sequência), o framework precisa descobrir:

“O que eu posso reaproveitar, e o que eu preciso mover?”

É aí que entra a LIS: Longest Increasing Subsequence (em português: Maior Subsequência Crescente).

🎯 O problema

Pense que o React (ou Vue) tem duas listas:


Antes: [A, B, C, D]
Depois: [B, C, A, D]

O que ele precisa fazer?

👉 Reutilizar o máximo possível de nós reais (elementos do DOM),
👉 E mover o mínimo necessário.

Um algoritmo simples poderia olhar posição por posição:

Índice	Antes	Depois	Mudou?
0	A	B	Sim
1	B	C	Sim
2	C	A	Sim
3	D	D	Não

E concluir:

“Quase tudo mudou! 😱 vou destruir e recriar tudo!”

💣 Isso é lento e desnecessário, especialmente em listas grandes.

Com inteligência (LIS)

O algoritmo da LIS pensa diferente:

“Quais itens já estão na ordem certa na nova lista?”

Vamos ver com calma.


Antes → [A, B, C, D]
Depois → [B, C, A, D]

Agora o algoritmo mapeia a posição antiga de cada item:

Item	Posição anterior
B	1
C	2
A	0
D	3

Isso gera a sequência numérica:
[1, 2, 0, 3]

E agora o algoritmo busca a maior sequência crescente dentro disso,
ou seja, a sequência que já está na ordem correta.

Aqui, a LIS é [1, 2, 3] → que corresponde aos elementos [B, C, D].

💡 Significa:
“B, C e D já estão na ordem certa. Só o A precisa ser movido.”

Com essa inteligência, o framework:

Mantém B, C e D onde estão.
Move apenas o A pro começo.

E pronto.
A interface muda de [A, B, C, D] → [B, C, A, D] sem recriar nada desnecessário.

🔧 Ou seja:

O DOM real quase não é tocado.
O custo é mínimo.
Tudo acontece em O(n log n), muito rápido.

Um jeito simples de visualizar

Imagine que o DOM é uma estante com prateleiras:


ANTES:
1: [A]
2: [B]
3: [C]
4: [D]

Você quer reorganizar para:


DEPOIS:
1: [B]
2: [C]
3: [A]
4: [D]

Um algoritmo ingênuo tiraria tudo da estante e recolocaria um por um 😅
Mas o algoritmo da LIS olha e pensa:

“Esses livros B, C e D já estão na ordem certa.
Só preciso tirar o A e colocar no começo.”

💡 Resultado: um movimento só.

💻 7. Entendendo o pseudocódigo

Vamos destrinchar o pseudocódigo de diffing:

function diff(oldList, newList) {
  const map = new Map()
  oldList.forEach((item, i) => map.set(item.key, i))

🧩 Cria um mapa que liga cada key ao seu índice na lista antiga.
Assim o algoritmo pode achar um item antigo em O(1) (instantaneamente).

  const newIndices = []
  for (const item of newList) {
    if (map.has(item.key)) newIndices.push(map.get(item.key))
    else mount(item)
  }

📋 Aqui ele percorre a nova lista:

Se a key existia, guarda a posição antiga.
Se é uma nova key, cria o elemento (mount).

Resultado: um array com os índices antigos dos itens reaproveitados.

  const lis = computeLIS(newIndices)
  for (const i of newIndices) {
    if (!lis.includes(i)) moveNode(i)
  }

📈 A partir dos índices antigos, ele calcula a LIS —
ou seja, quais nós já estão na posição certa.
Os outros precisam ser movidos.

  for (const item of oldList) {
    if (!newList.find(n => n.key === item.key)) unmount(item)
  }
}

💣 E por fim, ele remove do DOM tudo o que desapareceu.

O resultado final é um DOM atualizado com o mínimo de mudanças possíveis.

📊 8. Complexidades explicadas

Operação	Complexidade	Significa o quê
Comparar dois arrays do mesmo tamanho	O(n)	Tempo cresce linearmente
Calcular LIS (para reordenação)	O(n log n)	Um pouco mais caro, mas ainda eficiente
Comparar sem heurísticas	O(n²) a O(n³)	Explode de lentidão rapidamente

➡️ Por isso, React e Vue são tão rápidos — eles nunca chegam perto do caso O(n³).

💡 9. Como visualizar isso no dia a dia

Você já viu isso acontecer sem perceber.

Exemplo 1: lista de tarefas

Cada tarefa tem um botão “deletar”.
Se você usa o índice como key e deleta a primeira tarefa,
todas as outras são re-renderizadas.

O foco em um input no meio da lista é perdido.

Mas se cada tarefa tem id, o React só remove aquela e deixa o resto intacto.

Exemplo 2: tabela com dados dinâmicos

Quando você atualiza uma tabela (ex: preços de produtos), o diffing garante que apenas as linhas realmente alteradas sejam atualizadas.

Isso é crucial em dashboards com dezenas de dados mudando por segundo — o navegador continua leve e rápido.

Exemplo 3: animações suaves

Quando você anima elementos de uma lista (com Framer Motion ou Vue Transition Group), o framework depende das keys para saber quem é quem durante as transições.

Se as keys mudam, ele perde a referência e o efeito “teleporta” em vez de animar.

⚙️ 10. Em resumo

Etapa	O que acontece
1️⃣ Render	Framework cria novo Virtual DOM
2️⃣ Diff	Compara com o anterior
3️⃣ Patch	Cria instruções de mudança
4️⃣ Commit	Atualiza o DOM real apenas no necessário

🎨 Analogias finais pra fixar

DOM real → o prédio construído.
Virtual DOM → a planta digital do prédio.
Diffing → o engenheiro marcando no projeto o que foi reformado.
Key → o número de identificação de cada apartamento.

Sem a key, o engenheiro não sabe qual apartamento foi reformado — e reforma o prédio inteiro 😅

Se quiser, posso gerar a versão visual desse post com diagramas mostrando:

oldTree e newTree lado a lado,
setas do diff,
patch aplicado no DOM real,
e o caso “sem key vs com key” (com cores e movimentos).

Quer que eu faça essa imagem ilustrando tudo isso?

Amanda | Engenheira Frontend

segunda-feira, 10 de novembro de 2025