JSON Diff 算法深度实战：从 Naive 比较到智能差异引擎的完整工程方案

在 API 调试、配置管理和数据同步等场景中，JSON Diff（JSON 差异比较） 是开发者绕不开的基础需求。据 npm 下载数据统计，deep-diff、json-diff 和 fast-deep-equal 三个包的月下载量合计超过 1.2 亿次——这说明"比较两个 JSON 对象有什么不同"是一个极其高频的工程问题。但大多数开发者仍在使用 JSON.stringify(a) === JSON.stringify(b) 这种看似简洁、实则漏洞百出的方案。本文将从原理出发，手写一个生产级的 JSON Diff 引擎，覆盖对象深度比较、数组 LCS 差异、Patch 生成等核心能力。

📌 记住： JSON Diff 不等于 JSON Patch。JSON Patch（RFC 6902）定义的是"如何应用变更"的格式标准，而 JSON Diff 解决的是"如何检测变更"的算法问题。两者互补但职责不同。

🔍 一、为什么 JSON.stringify 比较是错的

1.1 三种常见的错误比较方式

大多数项目中，JSON 比较的"第一反应"是以下三种方案之一：

// ❌ 错误方式 1：引用比较 — 只比较引用，不比较内容
const a = { x: 1 }
const b = { x: 1 }
console.log(a === b)  // false（引用不同）

// ❌ 错误方式 2：JSON.stringify 比较 — 无法处理 key 顺序
const c = { x: 1, y: 2 }
const d = { y: 2, x: 1 }
console.log(JSON.stringify(c) === JSON.stringify(d))  // false！

// ❌ 错误方式 3：JSON.stringify + sort — 丢失 undefined、函数、特殊类型
const e = { x: 1, y: undefined, z: () => {} }
const f = { x: 1 }
console.log(JSON.stringify(e) === JSON.stringify(f))  // true — 但它们不相等！

1.2 JSON.stringify 比较的六大缺陷

⚠️ 警告： 在涉及 API 响应对比、配置校验等生产场景中，JSON.stringify 的 key 顺序问题是最常踩的坑。不同语言/框架序列化 JSON 的 key 顺序不同（Python 的 json.dumps 默认按 key 排序，JavaScript 不排序），导致"明明数据一样，比较结果却不同"的诡异 bug。

1.3 什么才是正确的 JSON Diff

一个正确的 JSON Diff 算法需要满足以下要求：

• ✅ Key 顺序无关：{a:1, b:2} 与 {b:2, a:1} 应被视为相等
• ✅ 支持所有 JSON 类型：string、number、boolean、null、array、object
• ✅ 精确的差异定位：告诉你"哪个路径、从什么值变成了什么值"
• ✅ 支持数组差异：不能只比较长度，要能识别"第几个元素变了"
• ✅ 高性能：10MB 级别的 JSON 比较应在 100ms 内完成

🚀 二、手写 JSON Diff 引擎：从基础到生产级

2.1 第一步：深度相等比较

一切 Diff 的基础是比较两个值是否"深度相等"。这是 fast-deep-equal 的核心逻辑：

// deep-equal.js — 深度相等比较（支持所有 JSON 类型）
function deepEqual(a, b) {
  // 1. 严格相等（处理 null、基本类型）
  if (a === b) return true

  // 2. null 检查
  if (a === null || b === null) return false

  // 3. NaN 比较
  if (typeof a === 'number' && typeof b === 'number') {
    return isNaN(a) && isNaN(b) ? true : a === b
  }

  // 4. 类型不同
  if (typeof a !== typeof b) return false

  // 5. 非对象类型
  if (typeof a !== 'object') return false

  // 6. 数组比较
  if (Array.isArray(a) !== Array.isArray(b)) return false

  if (Array.isArray(a)) {
    if (a.length !== b.length) return false
    for (let i = 0; i < a.length; i++) {
      if (!deepEqual(a[i], b[i])) return false
    }
    return true
  }

  // 7. 对象比较（key 顺序无关）
  const keysA = Object.keys(a)
  const keysB = Object.keys(b)
  if (keysA.length !== keysB.length) return false

  const keySet = new Set(keysB)
  for (const key of keysA) {
    if (!keySet.has(key)) return false
    if (!deepEqual(a[key], b[key])) return false
  }

  return true
}

// 测试
console.log(deepEqual({ a: 1, b: { c: [1, 2, 3] } }, { b: { c: [1, 2, 3] }, a: 1 }))  // true
console.log(deepEqual({ a: undefined }, {}))  // false
console.log(deepEqual({ a: NaN }, { a: NaN }))  // true

💡 提示： 上面的实现已经覆盖了 99% 的 JSON 比较场景。如果你的数据包含 Date、RegExp、Set、Map 等非 JSON 标准类型，需要在第 2 步和第 5 步之间增加类型特定的比较逻辑。

2.2 第二步：生成差异路径（Diff）

光知道"两个 JSON 不一样"是不够的——你需要知道哪里不一样。下面实现一个递归 Diff 引擎，输出结构化的差异列表：

// json-diff.js — 生成 JSON 差异路径
function jsonDiff(a, b, path = '') {
  const diffs = []

  // 基本类型或 null — 直接比较值
  if (a === b) return diffs
  if (a === null || b === null || typeof a !== 'object' || typeof b !== 'object') {
    if (a !== b && !(Number.isNaN(a) && Number.isNaN(b))) {
      diffs.push({ path: path || '/', type: 'modified', oldValue: a, newValue: b })
    }
    return diffs
  }

  // 数组比较
  if (Array.isArray(a) && Array.isArray(b)) {
    const maxLen = Math.max(a.length, b.length)
    for (let i = 0; i < maxLen; i++) {
      const childPath = `${path}[${i}]`
      if (i >= a.length) {
        diffs.push({ path: childPath, type: 'added', newValue: b[i] })
      } else if (i >= b.length) {
        diffs.push({ path: childPath, type: 'removed', oldValue: a[i] })
      } else {
        diffs.push(...jsonDiff(a[i], b[i], childPath))
      }
    }
    return diffs
  }

  // 对象比较
  const keysA = new Set(Object.keys(a))
  const keysB = new Set(Object.keys(b))
  const allKeys = new Set([...keysA, ...keysB])

  for (const key of allKeys) {
    const childPath = path ? `${path}.${key}` : key
    if (!keysA.has(key)) {
      diffs.push({ path: childPath, type: 'added', newValue: b[key] })
    } else if (!keysB.has(key)) {
      diffs.push({ path: childPath, type: 'removed', oldValue: a[key] })
    } else {
      diffs.push(...jsonDiff(a[key], b[key], childPath))
    }
  }

  return diffs
}

// 测试
const oldData = {
  name: "张三",
  age: 25,
  address: { city: "北京", zip: "100000" },
  tags: ["前端", "TypeScript"]
}

const newData = {
  name: "张三",
  age: 26,
  address: { city: "上海", zip: "200000", district: "浦东" },
  tags: ["前端", "TypeScript", "React"]
}

const result = jsonDiff(oldData, newData)
console.log(JSON.stringify(result, null, 2))
// 输出：
// [
//   { path: "age", type: "modified", oldValue: 25, newValue: 26 },
//   { path: "address.city", type: "modified", oldValue: "北京", newValue: "上海" },
//   { path: "address.zip", type: "modified", oldValue: "100000", newValue: "200000" },
//   { path: "address.district", type: "added", newValue: "浦东" },
//   { path: "tags[2]", type: "added", newValue: "React" }
// ]

2.3 第三步：数组 LCS 差异算法

上面的数组比较是按索引逐个比较的——这对"纯追加"的场景有效，但无法处理"中间插入/删除"的情况。例如：

// 按索引比较的问题
const a = [1, 2, 3, 4]
const b = [1, 3, 4]
// 按索引比较会输出：index 1 修改(2→3), index 2 修改(3→4), index 3 删除(4)
// 但正确答案是：index 1 删除(2)

解决这个问题的经典算法是 LCS（最长公共子序列，Longest Common Subsequence）。下面是针对 JSON 数组的 LCS Diff 实现：

// lcs-diff.js — 基于 LCS 的数组差异算法
function lcsDiff(oldArr, newArr, equalFn = deepEqual) {
  const m = oldArr.length
  const n = newArr.length

  // 1. 构建 LCS 表
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = equalFn(oldArr[i - 1], newArr[j - 1])
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1])
    }
  }

  // 2. 回溯生成操作序列
  const ops = []
  let i = m, j = n
  while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && equalFn(oldArr[i - 1], newArr[j - 1])) {
      ops.unshift({ type: 'keep', index: i - 1, value: oldArr[i - 1] })
      i--; j--
    } else if (j > 0 && (i === 0 || dp[i][j - 1] >= dp[i - 1][j])) {
      ops.unshift({ type: 'add', index: j - 1, value: newArr[j - 1] })
      j--
    } else {
      ops.unshift({ type: 'remove', index: i - 1, value: oldArr[i - 1] })
      i--
    }
  }

  return ops
}

// 测试
const oldTags = ["前端", "JavaScript", "TypeScript", "React"]
const newTags = ["前端", "TypeScript", "Vue", "React"]

const ops = lcsDiff(oldTags, newTags)
console.log(JSON.stringify(ops, null, 2))
// 输出：
// [
//   { type: "keep",   index: 0, value: "前端" },
//   { type: "remove", index: 1, value: "JavaScript" },
//   { type: "keep",   index: 2, value: "TypeScript" },
//   { type: "add",    index: 2, value: "Vue" },
//   { type: "keep",   index: 3, value: "React" }
// ]

⚠️ 警告： LCS 算法的时间复杂度是 O(m×n)，对于两个长度为 10000 的数组，需要比较 1 亿次。如果你的数据是"基本类型数组"（如字符串列表），可以用 hash 加速：先对每个元素计算 hash，再比较 hash 而非元素本身，时间复杂度降到 O(m+n)。

📊 三、性能基准测试与选型建议

3.1 不同方案的性能对比

以下基准测试在 Node.js 22 环境下进行，数据为随机生成的嵌套 JSON（约 500 个 key）：

3.2 选型决策

💡 提示： 大多数场景下，你不需要 LCS 数组 Diff。如果数组是"有序列表"（如搜索结果、时间序列），按索引比较就够了。只有当数组是"无序集合"且可能发生插入/删除时，才需要 LCS。

3.3 生成 RFC 6902 Patch

如果你需要将 Diff 结果转换为标准的 JSON Patch 格式（可以被 fast-json-patch 的 applyPatch 直接应用），可以用以下转换器：

// diff-to-patch.js — 将 Diff 转换为 RFC 6902 Patch
function diffToPatch(diffs) {
  return diffs.map(diff => {
    const path = '/' + diff.path.replace(/\./g, '/').replace(/\[(\d+)\]/g, '/$1')

    switch (diff.type) {
      case 'added':
        return { op: 'add', path, value: diff.newValue }
      case 'removed':
        return { op: 'remove', path }
      case 'modified':
        return { op: 'replace', path, value: diff.newValue }
      default:
        return null
    }
  }).filter(Boolean)
}

// 测试
const patch = diffToPatch(jsonDiff(oldData, newData))
console.log(JSON.stringify(patch, null, 2))
// 输出：
// [
//   { op: "replace", path: "/age", value: 26 },
//   { op: "replace", path: "/address/city", value: "上海" },
//   { op: "replace", path: "/address/zip", value: "200000" },
//   { op: "add",     path: "/address/district", value: "浦东" },
//   { op: "add",     path: "/tags/2", value: "React" }
// ]

生成的 Patch 可以直接应用到原始对象上，实现"先 Diff 再同步"的完整流程：

import { applyPatch } from 'fast-json-patch'

// 将 patch 应用到 oldData，得到 newData
const result = applyPatch(oldData, patch, true)
console.log(result.newDocument)  // 与 newData 完全一致

💡 四、生产环境最佳实践

4.1 API 响应对比工具

在 API 开发和调试中，JSON Diff 最常见的用途是对比两个 API 响应的差异。以下是一个实用的对比工具函数，支持忽略特定字段和路径过滤：

// api-diff.js — API 响应专用 Diff 工具
function apiDiff(oldResp, newResp, options = {}) {
  const { ignorePaths = [], onlyPaths = [] } = options

  const diffs = jsonDiff(oldResp, newResp)

  return diffs.filter(diff => {
    // 忽略指定路径（如 timestamp、requestId 等动态字段）
    if (ignorePaths.some(p => diff.path.startsWith(p))) return false

    // 只保留指定路径
    if (onlyPaths.length > 0 && !onlyPaths.some(p => diff.path.startsWith(p))) return false

    return true
  })
}

// 使用示例
const oldApi = { code: 0, data: { user: { name: "张三", age: 25 } }, timestamp: 1000 }
const newApi = { code: 0, data: { user: { name: "张三", age: 26 } }, timestamp: 2000 }

const diffs = apiDiff(oldApi, newApi, {
  ignorePaths: ['timestamp']  // 忽略动态字段
})
// 输出：[{ path: "data.user.age", type: "modified", oldValue: 25, newValue: 26 }]

4.2 配置漂移检测

在 DevOps 场景中，可以用 JSON Diff 检测配置文件是否被意外修改：

// config-drift.js — 配置漂移检测
function detectConfigDrift(expected, actual) {
  const diffs = jsonDiff(expected, actual)

  if (diffs.length === 0) {
    return { status: 'OK', message: '配置一致' }
  }

  return {
    status: 'DRIFT',
    message: `检测到 ${diffs.length} 处配置差异`,
    changes: diffs.map(d => ({
      path: d.path,
      expected: d.oldValue,
      actual: d.newValue,
      severity: d.type === 'removed' ? 'CRITICAL' : 'WARNING'
    }))
  }
}

// 使用示例
const expected = { db: { host: "localhost", port: 5432, pool: 10 }, cache: { ttl: 3600 } }
const actual   = { db: { host: "prod-db.example.com", port: 5432, pool: 5 }, cache: { ttl: 1800 } }

console.log(detectConfigDrift(expected, actual))
// {
//   status: 'DRIFT',
//   message: '检测到 3 处配置差异',
//   changes: [
//     { path: 'db.host', expected: 'localhost', actual: 'prod-db.example.com', severity: 'WARNING' },
//     { path: 'db.pool', expected: 10, actual: 5, severity: 'WARNING' },
//     { path: 'cache.ttl', expected: 3600, actual: 1800, severity: 'WARNING' }
//   ]
// }

4.3 避坑指南

以下是使用 JSON Diff 时最常见的三个坑点：

坑点 1：循环引用导致栈溢出

// ❌ 有循环引用的对象会导致无限递归
const obj = { a: 1 }
obj.self = obj  // 循环引用！

// ✅ 解决方案：用 WeakSet 跟踪已访问的对象
function safeDiff(a, b, path = '', visited = new WeakSet()) {
  if (typeof a === 'object' && a !== null) {
    if (visited.has(a)) return []  // 已访问过，跳过
    visited.add(a)
  }
  // ... 正常 diff 逻辑，递归时传递 visited
}

坑点 2：大数组的性能陷阱

// ❌ 两个 10 万元素的数组做 LCS = 100 亿次比较，直接卡死
const a = Array.from({ length: 100000 }, (_, i) => ({ id: i, value: Math.random() }))
const b = [...a.slice(0, 50000), ...a.slice(50001)]  // 删除了一个元素

// ✅ 解决方案：对有 "id" 字段的数组，先按 id 建索引再比较
function smartArrayDiff(oldArr, newArr, keyFn = null) {
  if (keyFn && oldArr.length > 1000) {
    // 按 key 建索引，时间复杂度 O(m+n)
    const oldMap = new Map(oldArr.map((item, i) => [keyFn(item), { item, index: i }]))
    const newMap = new Map(newArr.map((item, i) => [keyFn(item), { item, index: i }]))
    const diffs = []

    for (const [key, { item: oldItem }] of oldMap) {
      if (!newMap.has(key)) {
        diffs.push({ type: 'removed', key, value: oldItem })
      } else {
        diffs.push(...jsonDiff(oldItem, newMap.get(key).item, key))
      }
    }
    for (const [key, { item: newItem }] of newMap) {
      if (!oldMap.has(key)) {
        diffs.push({ type: 'added', key, value: newItem })
      }
    }
    return diffs
  }
  // 小数组用 LCS
  return lcsDiff(oldArr, newArr)
}

坑点 3：浮点数精度问题

// ❌ 浮点数比较的陷阱
const x = { price: 0.1 + 0.2 }
const y = { price: 0.3 }
console.log(jsonDiff(x, y))  // 会报差异！因为 0.1 + 0.2 = 0.30000000000000004

// ✅ 解决方案：引入 epsilon 容差
function numberEqual(a, b, epsilon = Number.EPSILON * 100) {
  return Math.abs(a - b) < epsilon
}

✅ 总结

JSON Diff 看似简单，实则涉及深度比较、路径追踪、数组语义差异等多个技术维度。核心结论如下：

• ⚡ 永远不要用 JSON.stringify 做 JSON 比较，key 顺序、特殊类型都会导致误判
• ⚡ 大多数场景只需递归 Diff，按 key 遍历 + 按索引比较数组就够了
• ⚡ 只有"无序数组有插入/删除"的场景才需要 LCS，性能代价不小，按需使用
• ⚡ 大数组用 key 索引加速，O(m×n) → O(m+n)
• ⚡ 生产环境注意循环引用和浮点精度，这两个坑最难排查

相关工具推荐

• 🔧 jsjson.com JSON 校验工具 — 在线 JSON 格式化与校验
• 🔧 jsjson.com JSON 数据转换 — JSON 与 CSV/XML/YAML 互转
• 🔧 json-diff — Node.js JSON Diff 库，支持颜色输出
• 🔧 fast-json-patch — RFC 6902 JSON Patch 实现
• 🔧 fast-deep-equal — 最快的深度相等比较库
• 🔧 deep-diff — 成熟的 JS 对象差异检测库