diff js

在Web开发中，数据比对（Diff）是优化性能、提升用户体验的关键技术，本文通过JavaScript实现差异比对算法，并解析其应用场景。
一、什么是Diff算法？
Diff算法通过比较新旧数据的差异，仅更新变化部分而非全量渲染，传统暴力比对的时间复杂度为O(n³)，而优化后的算法可降至O(n)，典型案例包括：
虚拟DOM更新（如React/Vue）
文本版本控制系统（如Git）
实时协同编辑工具
二、核心实现原理
1. 基础版本比对

function simpleDiff(oldArr, newArr) {

const patches = [];

for(let i=0; i<newArr.length; i++){

if(oldArr[i] !== newArr[i]) {

patches.push({type: ‘UPDATE’, index:i, value:newArr[i]});

}

}

return patches;

// 示例输出：

// 输入([1,2,3], [1,4,3])

// 返回 [{type:’UPDATE’,index:1,value:4}]

2. 键值优化策略（Keyed Diff）

function keyedDiff(oldNodes, newNodes) {

const patches = [];

const keyMap = new Map();

// 建立旧节点索引

oldNodes.forEach((node, index) => {

keyMap.set(node.key, index);

});

// 比对新增/移动的节点

newNodes.forEach((newNode, newIndex) => {

const oldIndex = keyMap.get(newNode.key);

if(typeof oldIndex === ‘undefined’) {

patches.push({type:’INSERT’, index:newIndex, node:newNode});

} else if(oldIndex !== newIndex) {

patches.push({type:’MOVE’, from:oldIndex, to:newIndex});

}

// 递归比对子节点

if(newNode.children) {

const childPatches = keyedDiff(

oldNodes[oldIndex].children || [],

newNode.children

);

patches.push(…childPatches);

}

});

return patches;

三、性能优化技巧
1、分层比对：DOM树按层级比较，减少递归深度
2、哈希标记：对静态节点添加唯一标识跳过比对
3、批处理：累积多个变更后统一提交
4、最长稳定子序列：通过LCS算法减少DOM操作次数
四、实际应用场景
1、富文本编辑器：协同编辑时传输差异数据

// 使用diff-match-patch库

const dmp = new diff_match_patch();

const diffs = dmp.diff_main(oldText, newText);

dmp.diff_cleanupSemantic(diffs);

2、API数据缓存：比对本地缓存与接口返回数据
3、动画系统：检测CSS属性变化触发过渡效果
五、推荐工具库jsdiff：轻量级文本差异库（[GitHub 18k⭐](https://github.com/kpdecker/jsdiff)）deep-diff：对象深层比对工具immer：不可变数据差异处理
> 本文参考：  
> 1. React Reconciler源码（React官方文档）  
> 2. 《算法导论》动态规划章节  
> 3. jsdiff v4.0.1核心实现逻辑