> For the complete documentation index, see [llms.txt](https://zg-zhang.gitbook.io/note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zg-zhang.gitbook.io/note/shi-zhan-bi-ji/cloud-music-web-app-v1.0/diff.md).

# React虚拟DOM的 Diff原理全解析

![Diff算法思维图](/files/-M5LX_c3HELRh6vdZ1LB)

## 设计思想概述

对一颗树进行更新，如果利用循环递归的方法对每一个节点进行比较，那算法的复杂度可以达到 O(n^3) 简单来说就是一颗有 1000 节点的树，要对比 10亿 次，还不包括比对类型、属性等节点的细节，再好的 CPU 也难以迅速的算出结果

但 React 说它的 Diff 算法能够达到 O(n)

其实它就是偷工减料没有老老实实的对比每一个节点，有一套自己的方法论：

* 永远只比较同层节点，不会跨层级比较节点
* 不同的两个节点产生不同的树，把原来的节点以及它的后代全部干掉，换成新的
* 通过 key 值指定哪些元素是相同的

## 执行规则 流程

* 元素类型不相同时
  * 直接将原 VDOM 树上该节点以及该节点下所有的后代节点全部删除，然后替换为新 VDOM 树上同一位置的节点，当然这个节点的后代节点也全都跟着过来了
* 元素类型相同时
  * 都是 DOM 节点：
    * 通过对比两个元素，React 知道需要修改 DOM 元素上的哪些属性
    * 处理完该节点之后，继续对子节点进行递归
  * 都是组件元素：
    * 组件实例保持不变，更新 props
    * 调用 componentWillReceiveProps() 方法，然后通过 shouldComponentUpdate 返回值决定是否调用 render 方法
    * 处理完该节点之后，继续对子节点进行递归
  * 特殊情况：遍历子元素列表
    * 引入 key 值：

```markup
<ul>
  <li>1</li>
  <li>2</li>
</ul>
```

在列表末尾插入一个元素

```markup
<ul>
  <li>1</li>
  <li>2</li>
  <li>3</li>
</ul>
```

这样 React 会先匹配两个对应的树，最后插入第三个元素，没有任何问题

但是 **如果在头部插入呢** ？

```markup
<ul>
  <li>3</li>
  <li>1</li>
  <li>2</li>
</ul>
```

此时前两个元素和原来都不一样，第三个元素被当作新增的节点，明明只需要更新一个节点，现在需要更新三个，这样的情况效率是非常低的

所以，React 引入了 key 值的概念

```markup
<ul>
  <li key="first">1</li>
  <li key="second">2</li>
</ul>
```

插入数据之后变成：

```markup
<ul>
  <li key="third">3</li>
  <li key="first">1</li>
  <li key="second">2</li>
</ul>
```

现在 React 通过 key 得知 1 和 2 原来是存在的，现在只是换了位置，因此就不需要更新整个节点了，只需要移动位置即可，大大提高效率

## 选取 key 值的问题

> key 选取的原则：不需要全局唯一，但是必须列表中保持唯一

如果使用 **数组元素的下标** 作为 key 值，在元素顺序不改变的情况下是没有问题的，但一旦顺序发生改变，diff 效率就可能骤然下降 因为在数组中间插入一条数据，那么插入数组之后的数组元素下标都会发生改变，即 key 值改变，那么后面的节点都得更新

> 不要使用数组下标做 key 值的根本原因在于：数组下标值不稳定，修改顺序就会修改当前 key