Diff

最主要的 diff 逻辑：

把树形结构按照层级分解，只比较同级元素
同个节点，会用 patch 进行打补丁操作
不同节点，会进行 insert 和 delete 操作
判断为一样的类型，使用的判断依据是：
1. key
2. tag
3. 如果是 input 标签的话，需要 type 也一样。
组件 children diff 中的得到 patch 数组方法，只需要返回插入、删除、更新的节点即可。

key 的作用

key 是给每一个 vnode 的唯一 id, 可以依靠 key, 更准确、快的拿到 oldVnode 中对应的 vnode 节点，让 vue 精准的追踪到每一个元素。

更准确：因为带 key 就不是就地复用了，在 sameNode 函数 a.key === b.key对比中可以避免就地复用的情况。所以会更加准确。
更快：利用 key 的唯一性生成 map 对象来获取对应节点，比遍历方式更快
触发过渡。元素的 key 属性就发生了改变，在渲染更新时，Vue 会认为这里新产生了一个元素，而老的元素由于 key 不存在了，所以会被删除，从而触发了过渡。

key 的作用

让 vue 精准的追踪到每一个元素，高效的更新虚拟 DOM。
触发过渡

<transition>
  <span :key="text">{{ text }}</span>
</transition>

当 text 改变时，这个元素的 key 属性就发生了改变，在渲染更新时，Vue 会认为这里新产生了一个元素，而老的元素由于 key 不存在了，所以会被删除，从而触发了过渡。

key 的作用（完整版）

能提高 diff 效率其实是不准确的。

见vue/patch.jsopen in new window，在不带 key 的情况下，判断sameVnodeopen in new window时因为 a.key 和 b.key 都是 undefined，对于列表渲染来说已经可以判断为相同节点然后调用 patchVnode 了，实际根本不会进入到答主给的 else 代码，也就无从谈起“带 key 比不带 key 时 diff 算法更高效”了。

官网推荐推荐的使用 key，应该理解为“使用唯一 id 作为 key”。因为 index 作为 key，和不带 key 的效果是一样的。index 作为 key 时，每个列表项的 index 在变更前后也是一样的，都是直接判断为 sameVnode 然后复用。

说到底，key 的作用就是更新组件时判断两个节点是否相同。相同就复用，不相同就删除旧的创建新的。

正是因为带唯一 key 时每次更新都不能找到可复用的节点，不但要销毁和创建 vnode，在 DOM 里添加移除节点对性能的影响更大。所以会才说“不带 key 可能性能更好”。看下面这个实验，渲染 10w 列表项，带唯一 key 与不带 key 的时间对比：

不使用 key 的情况：

<li v-for="item in list">{{ item.text }}</li>

open in new window

使用 id 作为 key 的情况：

<li v-for="item in list" :key="item.id">{{ n.text }}</li>

open in new window

list 构造：

const list1 = [];
const list2 = [];
for (let i = 0; i <= 100000; i++) {
  list1.push({
    id: i,
    text: i,
  });
  list2.push({
    id: i * 2,
    name: 100000 - i,
  });
}

因为不带 key 时节点能够复用，省去了销毁/创建组件的开销，同时只需要修改 DOM 文本内容而不是移除/添加节点，这就是文档中所说的“刻意依赖默认行为以获取性能上的提升”。

既然如此，为什么还要建议带 key 呢？因为这种模式只适用于渲染简单的无状态组件。对于大多数场景来说，列表组件都有自己的状态。

举个例子：一个新闻列表，可点击列表项来将其标记为"已访问"，可通过 tab 切换“娱乐新闻”或是“社会新闻”。

不带 key 属性的情况下，在“娱乐新闻”下选中第二项然后切换到“社会新闻”，"社会新闻"里的第二项也会是被选中的状态，因为这里复用了组件，保留了之前的状态。要解决这个问题，可以为列表项带上新闻 id 作为唯一 key，那么每次渲染列表时都会完全替换所有组件，使其拥有正确状态。

这只是个简单的例子，实际应用会更复杂。带上唯一 key 虽然会增加开销，但是对于用户来说基本感受不到差距，而且能保证组件状态正确，这应该就是为什么推荐使用唯一 id 作为 key 的原因。至于具体怎么使用，就要根据实际情况来选择了。

index 不能作为 key 的原因

通俗描述原因：本来不一样的东西，现在变成一样了。。。。因为 key 变成一样了，就判断是同个东西，所以循环比较虚拟 dom，还会继续一层一层进行遍历。

场景：

中间插入节点
中间删除节点

如果使用 index 的话，往数组的末尾添加元素的话问题不大，但是往数组的首位添加元素的话，就会有问题了。原本 key 值为 0 的 item value 变了，导致组件重新渲染； key 为 1 ， 2， 3， 4 ... 等也是如此，那就相当于说所有的 item 都重新更新了一遍，哪怕其他 item 没有任何变化。

会徒增很多的比较。

vue diff

采用 diff 算法来对比新旧虚拟节点，从而更新节点。

在 vue 的 diff 函数中。在交叉对比的时候，当新节点跟旧节点头尾交叉对比没有结果的时候，会根据新节点的 key 去对比旧节点数组中的 key，从而找到相应旧节点（这里对应的是一个 key => index 的 map 映射）。如果没找到就认为是一个新增节点。而如果没有 key，那么就会采用一种遍历查找的方式去找到对应的旧节点。一种一个 map 映射，另一种是遍历查找。相比而言。map 映射的速度更快。

使用 key 可以使得 DOM diff 更加高效，避免不必要的列表项更新。假设 todo.id 对此列表是唯一且稳定的，如果将此数据作为唯一键，那么 React 将能够对元素进行重新排序，而无需重新创建它们。

vue 部分源码如下：

// vue项目  src/core/vdom/patch.js  -488行
// oldCh 是一个旧虚拟节点数组，
if (isUndef(oldKeyToIdx))
  oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
idxInOld = isDef(newStartVnode.key)
  ? oldKeyToIdx[newStartVnode.key]
  : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);

创建 map 函数

function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key;
  const map = {};
  for (i = beginIdx; i <= endIdx; ++i) {
    key = children[i].key;
    if (isDef(key)) map[key] = i;
  }
  return map;
}

遍历寻找

// sameVnode 是对比新旧节点是否相同的函数
function findIdxInOld(node, oldCh, start, end) {
  for (let i = start; i < end; i++) {
    const c = oldCh[i];

    if (isDef(c) && sameVnode(node, c)) return i;
  }
}

简述 diff 算法？为什么不是 O(n3) 而可以简单理解为是 O(n)

检测 VDOM 的变化只发生在同一层，只比较同级不考虑跨级问题，很少会跨越层级地移动 Dom 元素，Virtual Dom 只会对同一个层级的元素进行对比。并且依赖于用户指定的 key

vnode 的转换过程和 dom-diff 的过程

https://juejin.im/post/5c8e5e4951882545c109ae9c#heading-5

index 不能作为 key 的原因

循环比较虚拟 dom，会一层一层进行遍历。

通俗描述原因：本来不一样的东西，现在变成一样了。。。。因为 key 变成一样了，就判断是同个东西

场景：

中间插入节点
中间删除节点

会徒增很多的比较。

React-Diff

diff 算法?

把树形结构按照层级分解，只比较同级元素。
给列表结构的每个单元添加唯一的 key 属性，方便比较。
React 只会匹配相同 class 的 component（这里面的 class 指的是组件的名字）
合并操作，调用 component 的 setState 方法的时候, React 将其标记为 - dirty.到每一个事件循环结束, React 检查所有标记 dirty 的 component 重新绘制.
选择性子树渲染。开发人员可以重写 shouldComponentUpdate 提高 diff 的性能

聊一聊你对 React 的 DOM diff 算法的理解

虚拟 DOM 的优缺点有哪些？

React Diff 算法

react 虚拟 DOM 是什么? 如何实现? 说一下 diff 算法 ? DIFF 算法为什么是 O(n)复杂度而不是 O(n^3)

差异算法涵盖了哪些规则?

在区分两棵树时，React 首先比较两个根元素。根据根元素的类型，行为会有所不同。它在重构算法中涵盖了以下规则：

不同类型的元素： 每当根元素具有不同的类型时，React 将移除旧树并从头开始构建新树。例如，元素 <a> 到 <img>，或从 <Article> 到 <Comment>的不同类型的元素引导完全重建。

相同类型的 DOM 元素： 当比较两个相同类型的 React DOM 元素时，React 查看两者的属性，保持相同的底层 DOM 节点，并仅更新已更改的属性。让我们以相同的 DOM 元素为例，除了 className 属性，

<div className="show" title="ReactJS" />

<div className="hide" title="ReactJS" />

相同类型的组件元素：

当组件更新时，实例保持不变，以便在渲染之间保持状态。React 更新底层组件实例的 props 以匹配新元素，并在底层实例上调用 componentWillReceiveProps() 和 componentWillUpdate()。之后，调用 render() 方法，diff 算法对前一个结果和新结果进行递归。

递归子节点： 当对 DOM 节点的子节点进行递归时，React 会同时迭代两个子节点列表，并在出现差异时生成变异。例如，在子节点末尾添加元素时，在这两个树之间进行转换效果很好。

<ul>
<li>first</li>
<li>second</li>
</ul>

<ul>
<li>first</li>
<li>second</li>
<li>third</li>
</ul>

处理 Key：

React 支持 key 属性。当子节点有 key 时，React 使用 key 将原始树中的子节点与后续树中的子节点相匹配。例如，添加 key 可以使树有效地转换，

<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

diff 实现方式

虚拟 DOM 算法

DOM 是很慢的，如果我们创建一个简单的 div，然后把他的所有的属性都打印出来，你会看到：

var div = document.createElement("div"),
  str = "";
for (var key in div) {
  str = str + " " + key;
}
console.log(str);

可以看到，这些属性还是非常惊人的，包括样式的修饰特性、一般的特性、方法等等，如果我们打印出其长度，可以得到惊人的 227 个。而这仅仅是一层，真正的 DOM 元素是非常庞大的，这是因为标准就是这么设计的，而且操作他们的时候你要小心翼翼，轻微的触碰就有可能导致页面发生重排，这是杀死性能的罪魁祸首。

而相对于 DOM 对象，原生的 JavaScript 对象处理起来更快，而且更简单，DOM 树上的结构信息我们都可以使用 JavaScript 对象很容易的表示出来。

 var element = {
 tagName: 'ul',
 props: {
   id: 'list'
 },
 children: {
   {
tagName: 'li',
props: {
  class: 'item'
},
children: ['Item1']
   },
   {
tagName: 'li',
props: {
  class: 'item'
},
children: ['Item1']
   },
   {
tagName: 'li',
props: {
  class: 'item'
},
children: ['Item1']
   }
 }
    }

如上所示，对于一个元素，我们只需要一个 JavaScript 对象就可以很容易的表示出来，这个对象中有三个属性:

tagName: 用来表示这个元素的标签名。
props: 用来表示这元素所包含的属性。
children: 用来表示这元素的 children。

而上面的这个对象使用 HTML 表示就是：

<ul id="list">
  <li class="item">Item 1</li>
  <li class="item">Item 2</li>
  <li class="item">Item 3</li>
</ul>

OK! 既然原来的 DOM 信息可以使用 JavaScript 来表示，那么反过来，我们就可以用这个 JavaScript 对象来构建一个真正的 DOM 树。

所以之前所说的状态变更的时候会从新构建这个 JavaScript 对象，然后呢，用新渲染的对象和旧的对象去对比，记录两棵树的差异，记录下来的就是我们需要改变的地方。这就是所谓的虚拟 DOM，包括下面的几个步骤：

用 JavaScript 对象来表示 DOM 树的结构；然后用这个树构建一个真正的 DOM 树，插入到文档中。当状态变更的时候，重新构造一个新的对象树，然后用这个新的树和旧的树作对比，记录两个树的差异。把 2 所记录的差异应用在步骤一所构建的真正的 DOM 树上，视图就更新了。 Virtual DOM 的本质就是在 JS 和 DOM 之间做一个缓存，可以类比 CPU 和硬盘，既然硬盘这么慢，我们就也在他们之间添加一个缓存；既然 DOM 这么慢，我们就可以在 JS 和 DOM 之间添加一个缓存。 CPU（JS）只操作内存（虚拟 DOM），最后的时候在把变更写入硬盘（DOM）。

算法实现

1. 用 JavaScript 对象模拟 DOM 树

用 JavaScript 对象来模拟一个 DOM 节点并不难，你只需要记录他的节点类型（tagName）、属性（props）、子节点（children）。 element.js

function Element(tagName, props, children) {
  this.tagName = tagName;
  this.props = props;
  this.children = children;
}
module.exports = function (tagName, props, children) {
  return new Element(tagName, props, children);
};

通过这个构造函数，我们就可以传入标签名、属性以及子节点了，tagName 可以在我们 render 的时候直接根据它来创建真实的元素，这里的 props 使用一个对象传入，可以方便我们遍历。

基本使用方法如下：

var el = require("./element");

var ul = el("ul", { id: "list" }, [
  el("li", { class: "item" }, ["item1"]),
  el("li", { class: "item" }, ["item2"]),
  el("li", { class: "item" }, ["item3"]),
]);

然而，现在的 ul 只是 JavaScript 表示的一个 DOM 结构，页面上并没有这个结构，所有我们可以根据 ul 构建一个真正的

：

Element.prototype.render = function () {
  // 根据tagName创建一个真实的元素
  var el = document.createElement(this.tagName);
  // 得到这个元素的属性对象，方便我们遍历。
  var props = this.props;

  for (var propName in props) {
    // 获取到这个元素值
    var propValue = props[propName];

    // 通过setAttribute设置元素属性。
    el.setAttribute(propName, propValue);
  }

  // 注意： 这里的children，我们传入的是一个数组，所以，children不存在时我们用【】来替代。
  var children = this.children || [];

  //遍历children
  children.forEach(function (child) {
    var childEl =
      child instanceof Element
        ? child.render()
        : document.createTextNode(child);
    // 无论childEl是元素还是文字节点，都需要添加到这个元素中。
    el.appendChild(childEl);
  });

  return el;
};

所以，render 方法会根据 tagName 构建一个真正的 DOM 节点，然后设置这个节点的属性，最后递归的把自己的子节点也构建起来，所以只需要调用 ul 的 render 方法，通过 document.body.appendChild 就可以挂载到真实的页面了。

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>div</title>
</head>
<body>
  <script>

    function Element(tagName, props, children) {
 this.tagName = tagName;
 this.props = props;
 this.children = children;
    }


    var ul = new Element('ul', {id: 'list'}, [
   new Element('li', {class: 'item'}, ['item1']),
   new Element('li', {class: 'item'}, ['item2']),
   new Element('li', {class: 'item'}, ['item3'])
 ]);

    Element.prototype.render = function () {
 // 根据tagName创建一个真实的元素
 var el = document.createElement(this.tagName);
 // 得到这个元素的属性对象，方便我们遍历。
 var props = this.props;

 for (var propName in props) {
   // 获取到这个元素值
   var propValue = props[propName];

   // 通过setAttribute设置元素属性。
   el.setAttribute(propName, propValue);
 }

 // 注意： 这里的children，我们传入的是一个数组，所以，children不存在时我们用【】来替代。
 var children = this.children || [];

 //遍历children
 children.forEach(function (child) {
   var childEl = (child instanceof Element)
  ? child.render()
  : document.createTextNode(child);
   // 无论childEl是元素还是文字节点，都需要添加到这个元素中。
   el.appendChild(childEl);
 });

 return el;
    }

    var ulRoot = ul.render();
    document.body.appendChild(ulRoot);
  </script>
</body>
</html>

上面的这段代码，就可以渲染出下面的结果了：

比较两颗虚拟 DOM 树的差异

比较两颗 DOM 数的差异是 Virtual DOM 算法中最为核心的部分，这也就是所谓的 Virtual DOM 的 diff 算法。两个树的完全的 diff 算法是一个时间复杂度为 O(n3) 的问题。但是在前端中，你会很少跨层地移动 DOM 元素，所以真实的 DOM 算法会对同一个层级的元素进行对比上图中，div 只会和同一层级的 div 对比，第二层级的只会和第二层级对比。这样算法复杂度就可以达到 O(n)。

（1）深度遍历优先，记录差异在实际的代码中，会对新旧两棵树进行一个深度优先的遍历，这样每一个节点就会有一个唯一的标记：上面的这个遍历过程就是深度优先，即深度完全完成之后，再转移位置。在深度优先遍历的时候，每遍历到一个节点就把该节点和新的树进行对比，如果有差异的话就记录到一个对象里面。

// diff函数，对比两颗树
    function diff(oldTree, newTree) {
 // 当前的节点的标志。因为在深度优先遍历的过程中，每个节点都有一个index。
 var index = 0;

 // 在遍历到每个节点的时候，都需要进行对比，找到差异，并记录在下面的对象中。
 var pathches = {};

 // 开始进行深度优先遍历
 dfsWalk(oldTree, newTree, index, pathches);

 // 最终diff算法返回的是一个两棵树的差异。
 return pathches;
    }

    // 对两棵树进行深度优先遍历。
    function dfsWalk(oldNode, newNode, index, pathches) {
 // 对比oldNode和newNode的不同，记录下来
 pathches[index] = [...];

 diffChildren(oldNode.children, newNode.children, index, pathches);
    }

    // 遍历子节点
    function diffChildren(oldChildren, newChildren, index, pathches) {
 var leftNode = null;
 var currentNodeIndex = index;
 oldChildren.forEach(function (child, i) {
   var newChild = newChildren[i];
   currentNodeIndex = (leftNode && leftNode.count)
   ? currentNodeIndex + leftNode.count + 1
   : currentNodeIndex + 1

   // 深度遍历子节点
   dfsWalk(child, newChild, currentNodeIndex, pathches);
   leftNode = child;
 });
    }

例如，上面的 div 和新的 div 有差异，当前的标记是 0，那么我们可以使用数组来存储新旧节点的不同：

patches[0] = [{difference}, {difference}, ...] 同理使用 patches[1]来记录 p，使用 patches[3]来记录 ul，以此类推。

（2）差异类型

上面说的节点的差异指的是什么呢？对 DOM 操作可能会：

替换原来的节点，如把上面的 div 换成了 section。
移动、删除、新增子节点，例如上面 div 的子节点，把 p 和 ul 顺序互换。
修改了节点的属性。对于文本节点，文本内容可能会改变。例如修改上面的文本内容 2 内容为 Virtual DOM2. 　　所以，我们可以定义下面的几种类型：

var REPLACE = 0;
var REORDER = 1;
var PROPS = 2;
var TEXT = 3;

对于节点替换，很简单，判断新旧节点的 tagName 是不是一样的，如果不一样的说明需要替换掉。如 div 换成了 section，就记录下：

patches[0] = [
  {
    type: REPALCE,
    node: newNode, // el('section', props, children)
  },
];

除此之外，如果给 div 新增了属性 id 为 container，就记录下：

pathches[0] = [
  {
    type: REPLACE,
    node: newNode,
  },
  {
    type: PROPS,
    props: {
      id: "container",
    },
  },
];

如果是文本节点发生了变化，那么就记录下：

pathches[2] = [
  {
    type: TEXT,
    content: "virtual DOM2",
  },
];

那么如果我们把 div 的子节点重新排序了呢？比如 p、ul、div 的顺序换成了 div、p、ul，那么这个该怎么对比呢？如果按照同级进行顺序对比的话，他们就会被替换掉，如 p 和 div 的 tagName 不同，p 就会被 div 所代替，最终，三个节点就都会被替换，这样 DOM 开销就会非常大，而实际上是不需要替换节点的，只需要移动就可以了，我们只需要知道怎么去移动。这里牵扯到了两个列表的对比算法，如下。

（3）列表对比算法　　假设现在可以英文字母唯一地标识每一个子节点：

旧的节点顺序：

a b c d e f g h i

现在对节点进行了删除、插入、移动的操作。新增 j 节点，删除 e 节点，移动 h 节点：

新的节点顺序：

a b c h d f g i j

现在知道了新旧的顺序，求最小的插入、删除操作（移动可以看成是删除和插入操作的结合）。这个问题抽象出来其实是字符串的最小编辑距离问题（Edition Distance），最常见的解决算法是 Levenshtein Distance，通过动态规划求解，时间复杂度为 O(M * N)。但是我们并不需要真的达到最小的操作，我们只需要优化一些比较常见的移动情况，牺牲一定 DOM 操作，让算法时间复杂度达到线性的（O(max(M, N))。具体算法细节比较多，这里不累述，有兴趣可以参考代码。

我们能够获取到某个父节点的子节点的操作，就可以记录下来：

patches[0] = [{
  type: REORDER,
  moves: [{remove or insert}, {remove or insert}, ...]
}]

但是要注意的是，因为 tagName 是可重复的，不能用这个来进行对比。所以需要给子节点加上唯一标识 key，列表对比的时候，使用 key 进行对比，这样才能复用老的 DOM 树上的节点。

这样，我们就可以通过深度优先遍历两棵树，每层的节点进行对比，记录下每个节点的差异了。完整 diff 算法代码可见 diff.js。

把差异引用到真正的 DOM 树上　　因为步骤一所构建的 JavaScript 对象树和 render 出来真正的 DOM 树的信息、结构是一样的。所以我们可以对那棵 DOM 树也进行深度优先的遍历，遍历的时候从步骤二生成的 patches 对象中找出当前遍历的节点差异，然后进行 DOM 操作。

function patch(node, patches) {
  var walker = { index: 0 };
  dfsWalk(node, walker, patches);
}

function dfsWalk(node, walker, patches) {
  var currentPatches = patches[walker.index]; // 从patches拿出当前节点的差异

  var len = node.childNodes ? node.childNodes.length : 0;
  for (var i = 0; i < len; i++) {
    // 深度遍历子节点
    var child = node.childNodes[i];
    walker.index++;
    dfsWalk(child, walker, patches);
  }

  if (currentPatches) {
    applyPatches(node, currentPatches); // 对当前节点进行DOM操作
  }
}

applyPatches，根据不同类型的差异对当前节点进行 DOM 操作：

function applyPatches(node, currentPatches) {
  currentPatches.forEach(function (currentPatch) {
    switch (currentPatch.type) {
      case REPLACE:
        node.parentNode.replaceChild(currentPatch.node.render(), node);
        break;
      case REORDER:
        reorderChildren(node, currentPatch.moves);
        break;
      case PROPS:
        setProps(node, currentPatch.props);
        break;
      case TEXT:
        node.textContent = currentPatch.content;
        break;
      default:
        throw new Error("Unknown patch type " + currentPatch.type);
    }
  });
}

结语: virtual DOM 算法主要实现上面步骤的三个函数： element、diff、patch，然后就可以实际的进行使用了。

// 1. 构建虚拟DOM
var tree = el("div", { id: "container" }, [
  el("h1", { style: "color: blue" }, ["simple virtal dom"]),
  el("p", ["Hello, virtual-dom"]),
  el("ul", [el("li")]),
]);

// 2. 通过虚拟DOM构建真正的DOM
var root = tree.render();
document.body.appendChild(root);

// 3. 生成新的虚拟DOM
var newTree = el("div", { id: "container" }, [
  el("h1", { style: "color: red" }, ["simple virtal dom"]),
  el("p", ["Hello, virtual-dom"]),
  el("ul", [el("li"), el("li")]),
]);

// 4. 比较两棵虚拟DOM树的不同
var patches = diff(tree, newTree);

// 5. 在真正的DOM元素上应用变更
patch(root, patches);

当然这是非常粗糙的实践，实际中还需要处理事件监听等；生成虚拟 DOM 的时候也可以加入 JSX 语法。这些事情都做了的话，就可以构造一个简单的 ReactJS 了。

转载：深入理解 react 中的虚拟 DOM、diff 算法open in new window

diff 算法

对比 Vdom 树差异的算法

同层比对

新旧状态的比对时采用同层比对，当发现某节点不一致了直接替换该节点的子树。而不管它的子树是不是真的改动了。

key 值的使用

在列表循环的时候 React 会要求每一个列表项有一个独一无二，稳定的 key 值，它的目的是为了当状态改变时新旧状态的每一个列表项能够对应起来，方便比对。

Keys 是 React 用于追踪哪些列表中元素被修改、被添加或者被移除的辅助标识。 Diff 算法中 React 会借助元素的 Key 值来判断该元素是新近创建的还是被移动而来的元素，从而减少不必要的元素重渲染。此外，React 还需要借助 Key 值来判断元素与本地状态的关联关系

虚拟 dom

首先需要明确的一点是虚拟 dom 之间的比较，是存在于同一层级的 dom，也就是说只会比较新旧 vnode 的 children ，而不会拿 children 与 children 的 children 进行比较。

diff 流程图

当数据发生改变时，set 方法会让调用Dep.notify通知所有订阅者 Watcher，订阅者就会调用patch给真实的 DOM 打补丁，更新相应的视图。

React Diff

React 中应用虚拟 DOM 来更新快速更新 DOM,那么更新虚拟 DOM 的原则主要是以下几种:

不同元素如果更新前后是两种不同类型的 DOM 元素,那就没什么说的,直接销毁原来的节点,创建新的节点.(比如原来是 div,更新为 span)在这个过程中,原来节点的 componentWillUnmount 函数被触发, 新节点的 componentWillMount 和 componentDidMount 依次被触发. 需要特别指出的是,当前更新节点的所有子节点都会被销毁重建,而不管子节点是否有更新. 简单的来说,就是根变了,那么这个根上的所有叶子都要更新了.
相同元素,不同属性当节点类型没有发生变化,而只是出行变化的话,React 就智能多了,只会更新变化的部分. 好比是一个元素有多个 CSS 样式,如果只变化了一个样式,那么 React 也只更新一个. 当元素不是叶子节点的时候,也就是一个组件元素的时候,会继续深入的去比较子元素来更新子元素.
子元素变动. 当子元素有变动的时候,React 会更新子元素. 子元素的变动指的是资源的类型/属性/位置等的变动. 类型和属性的变动会触发更新,这个比较好理解.子元素的位置变动,指的是如果一个资源原来在第一位,更新后到第二位了,React 会认为这是一种变动,从而触发更新.
key 属性的重要作用这样看起来 React 也没有那么智能.那么这个时候就要引入一个很重要的 key 属性.React 通过给子组件一个 key 属性.来唯一标识一个子组件,如果更新前后的组件 key 值一样,并且除了位置之外其他属性没有变化,那么就不会触发更新.

虚拟 DOM 和 diff 算法

什么是 diff 算法

diff 算法是比较两个虚拟 DOM 树的差异，找出需要更新的节点，并将这些节点更新到真实 DOM 上的算法。Vue.js 内部使用的是优化算法，可以快速地确定需要更新的节点，以最小化更新的时间和效果。

diff 算法如何工作

当数据改变时，Vue.js 首先创建一个新的虚拟 DOM 树，并将其与之前的虚拟 DOM 树进行比较。diff 算法是一种递归算法，它会逐层遍历节点，比较两个虚拟 DOM 树中的每个节点，找出需要更新的节点。在比较节点时，Vue.js 会使用一些启发式算法来优化比较性能。

diff 算法的优化

Vue.js 内部使用了大量的优化策略来提高 diff 算法的性能，其中最重要的包括：

只对同级组件进行比较
根据节点的关键属性进行比较
对列表中的节点采用就地复用策略

这些优化策略可以显著提高 Vue.js 应用程序的性能，并使其在渲染大型数据集时更具可扩展性。

Key of React

写 React / Vue 项目时为什么要在组件中写 key，其作用是什么

vue 和 react 都是采用 diff 算法来对比新旧虚拟节点，从而更新节点。

vue 部分源码如下：

// vue项目  src/core/vdom/patch.js  -488行
// oldCh 是一个旧虚拟节点数组，
if (isUndef(oldKeyToIdx))
  oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
idxInOld = isDef(newStartVnode.key)
  ? oldKeyToIdx[newStartVnode.key]
  : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);

创建 map 函数

function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key;
  const map = {};
  for (i = beginIdx; i <= endIdx; ++i) {
    key = children[i].key;
    if (isDef(key)) map[key] = i;
  }
  return map;
}

遍历寻找

// sameVnode 是对比新旧节点是否相同的函数
function findIdxInOld(node, oldCh, start, end) {
  for (let i = start; i < end; i++) {
    const c = oldCh[i];

    if (isDef(c) && sameVnode(node, c)) return i;
  }
}

diff

把树形结构按照层级分解，只比较同级元素
给列表结构的每个单元添加唯一的 key 属性，方便比较
React 只会匹配相同 class 的 component(这里面的 class 指的是组件的名字)
合并操作，调用 component 的 setState 方法的时候, React 将其标记为 dirty.到每一个事件循环结束, React 检查所有标记 dirty 的 component 重新绘制.
选择性子树渲染。开发人员可以重写 shouldComponentUpdate 提高 diff 的性能。

React.forwardRef 是什么？它有什么作用？

React.forwardRef 会创建一个 React 组件，这个组件能够将其接受的 ref 属性转发到其组件树下的另一个组件中。这种技术并不常见，但在以下两种场景中特别有用：

转发 refs 到 DOM 组件
在高阶组件中转发 refs

什么是 "key" 属性，在元素数组中使用它们有什么好处?

key 是一个特殊的字符串属性，帮助 React 识别哪些项已更改、添加或删除。

通常使用数据中的 IDs 作为 key。在渲染列表项时，如果你没有稳定的 IDs，你可能会使用 index 作为 key：

注意：

由于列表项的顺序可能发生改变，因此并不推荐使用 indexes 作为 keys。这可能会对性能产生负面影响，并可能导致组件状态出现问题。

O(n) 复杂度的的 diff 算法

React 通过 updateDepth 对 Virtual DOM 树进行层级控制，只会对相同颜色方框内的 DOM 节点进行比较，即同一个父节点下的所有子节点。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。

详细学习open in new window

把每一种节点类型抽象成对象，每一种节点类型有自己的属性，也就是 prop，每次进行 diff 的时候，react 会先比较该节点类型，假如节点类型不一样，那么 react 会直接删除该节点，然后直接创建新的节点插入到其中，假如节点类型一样，那么会比较 prop 是否有更新，假如有 prop 不一样，那么 react 会判定该节点有更新，那么重渲染该节点，然后在对其子节点进行比较，一层一层往下，直到没有子节点。

# Diff

# key 的作用

# key 的作用

# key 的作用（完整版）

# index 不能作为 key 的原因

# vue diff

# 简述 diff 算法？为什么不是 O(n3) 而可以简单理解为是 O(n)

# vnode 的转换过程 和 dom-diff 的过程

# index 不能作为 key 的原因

# React-Diff

# diff 算法?

# 聊一聊你对 React 的 DOM diff 算法的理解

# 虚拟 DOM 的优缺点有哪些？

# React Diff 算法

# 差异算法涵盖了哪些规则?

# diff 实现方式

# 虚拟 DOM 算法

# 算法实现

# 1. 用 JavaScript 对象模拟 DOM 树

# 比较两颗虚拟 DOM 树的差异

# diff 算法

# 同层比对

# key 值的使用

# 虚拟 dom

# diff 流程图

# React Diff

# 虚拟 DOM 和 diff 算法

# Key of React

# 写 React / Vue 项目时为什么要在组件中写 key，其作用是什么

# diff

# React.forwardRef 是什么？它有什么作用？

# 什么是 "key" 属性，在元素数组中使用它们有什么好处?

# O(n) 复杂度的的 diff 算法

Diff

key 的作用

key 的作用

key 的作用（完整版）

index 不能作为 key 的原因

vue diff

简述 diff 算法？为什么不是 O(n3) 而可以简单理解为是 O(n)

vnode 的转换过程和 dom-diff 的过程

index 不能作为 key 的原因

React-Diff

diff 算法?

聊一聊你对 React 的 DOM diff 算法的理解

虚拟 DOM 的优缺点有哪些？

React Diff 算法

差异算法涵盖了哪些规则?

diff 实现方式

虚拟 DOM 算法

算法实现

1. 用 JavaScript 对象模拟 DOM 树

比较两颗虚拟 DOM 树的差异

diff 算法

同层比对

key 值的使用

虚拟 dom

diff 流程图

React Diff

虚拟 DOM 和 diff 算法

Key of React

写 React / Vue 项目时为什么要在组件中写 key，其作用是什么

diff

React.forwardRef 是什么？它有什么作用？

什么是 "key" 属性，在元素数组中使用它们有什么好处?

O(n) 复杂度的的 diff 算法