面试题：DIFF 算法的原理是什么？

DIFF 算法是虚拟 DOM（Virtual DOM）中的核心算法，用于比较新旧虚拟 DOM 树的差异，并高效地更新真实 DOM。Vue 和 React 等框架都使用了 DIFF 算法来优化渲染性能。

1. DIFF 算法的目标

DIFF 算法的目标是以最小的代价更新真实 DOM，避免不必要的 DOM 操作，从而提升性能。

2. DIFF 算法的基本原则

DIFF 算法遵循以下基本原则：

同级比较：只比较同一层级的节点，不跨层级比较。
类型不同则直接替换：如果节点类型不同（如 div 变为 span），则直接替换整个节点及其子节点。
Key 值优化：通过 key 属性标识节点，减少不必要的节点移动。

3. DIFF 算法的具体实现

DIFF 算法的具体实现可以分为以下几个步骤：

（1）树形结构的比较

从根节点开始，递归比较新旧虚拟 DOM 树的节点。
如果节点类型不同，则直接替换整个子树。

（2）列表节点的比较

对于列表节点（如 ul 中的 li），DIFF 算法会使用 双端比较 策略来优化性能。
双端比较的策略包括：
- 头头比较：比较新旧列表的头节点。
- 尾尾比较：比较新旧列表的尾节点。
- 头尾比较：比较旧列表的头节点和新列表的尾节点。
- 尾头比较：比较旧列表的尾节点和新列表的头节点。
如果以上比较都不匹配，则通过 key 值查找节点。

（3）Key 值的作用

key 是节点的唯一标识，用于在列表比较中快速定位节点。
如果节点有 key 值，DIFF 算法会通过 key 值查找节点，避免不必要的节点移动。

4. DIFF 算法的优化策略

为了进一步提升性能，DIFF 算法采用了以下优化策略：

（1）节点复用

如果新旧节点的 key 值和类型相同，则复用该节点，只更新其属性和子节点。

（2）减少 DOM 操作

DIFF 算法会尽量减少 DOM 操作，如节点的插入、删除和移动。

（3）批量更新

DIFF 算法会将多个 DOM 操作合并为一次批量更新，减少浏览器的重绘和回流。

5. DIFF 算法的示例

以下是一个简单的 DIFF 算法实现（简化版）：

function diff(oldNode, newNode) {
  // 如果节点类型不同，则直接替换
  if (oldNode.type !== newNode.type) {
    return { type: 'REPLACE', node: newNode };
  }

  // 如果节点是文本节点，则比较文本内容
  if (typeof oldNode === 'string' && typeof newNode === 'string') {
    if (oldNode !== newNode) {
      return { type: 'TEXT', content: newNode };
    }
    return null;
  }

  // 比较属性
  const attrChanges = {};
  for (const key in newNode.attrs) {
    if (newNode.attrs[key] !== oldNode.attrs[key]) {
      attrChanges[key] = newNode.attrs[key];
    }
  }
  for (const key in oldNode.attrs) {
    if (!(key in newNode.attrs)) {
      attrChanges[key] = null;
    }
  }

  // 比较子节点
  const childrenChanges = [];
  const oldChildren = oldNode.children || [];
  const newChildren = newNode.children || [];
  const maxLen = Math.max(oldChildren.length, newChildren.length);
  for (let i = 0; i < maxLen; i++) {
    const change = diff(oldChildren[i], newChildren[i]);
    if (change) {
      childrenChanges.push({ index: i, change });
    }
  }

  return {
    type: 'UPDATE',
    attrs: attrChanges,
    children: childrenChanges
  };
}