react-虚拟dom+diff算法

1. 虚拟dom

1.1 和真实dom的对比

(1) 结构对比

首先分别通过React.createElement和document.createElement创建一个dom节点，然后进行打印对比看看二者的区别：

        const VDOM = React.createElement('div', {}, 'yoimiya')
        const DOM = document.createElement("div");
        DOM.innerHTML = 'yoimiya'

        console.log(`虚拟DOM:`, VDOM)
        console.log(`真实DOM:`, DOM)

可以看出来虚拟dom是一个对象结构，而真实dom就是普通的dom结构，普通的dom结构包含了什么呢？

可以看到，真实dom上默认挂载了很多属性和方法，因此从结构上看，虚拟dom比真实dom要轻很多。

(2) 操作对比

假设现在有如下列表：

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

现在希望将123替换成4567，该怎么操作呢？
方法一： 将原列表的123替换成456，再新增一个7
方法二： 将原列表的内容全删掉，再新增4567
方法三： 直接通过innerHTML覆盖ul的内容

单纯从操作讲，方法一最复杂，方法三最方便。而从性能上讲，也是方法三的性能最高，因为渲染存在着回流和重绘的问题，如果页面比较复杂，频繁操作dom会造成很大的开销。

(3) 流程对比
传统的web应用中，数据的变化会实时地更新到用户界面中，因此每次微小的变化都会引起dom的渲染。

而虚拟dom的目的是：将所有的操作聚集到一块，计算出所有的变化后，统一更新虚拟dom。

也就是说，一个页面如果有500次变化，没有虚拟DOM的就会渲染500次，而虚拟DOM只需要渲染一次，从这点上来看，页面越复杂，虚拟DOM的优势越大。

1.2 虚拟dom概念

在上面我们说过虚拟dom就是对象，接下来详细看看这个对象包含了什么，举个例子：

    <div className='Index'>
      <div>yoimiya</div>
      <ul>
        <li>React</li>
        <li>Vue</li>
      </ul>
    </div>

转化后：

    {
        type: 'div',
        props: { class: 'Index' },
        children: [
            {
                type: 'div',
                children: 'yoimiya'
            },
            {
                type: 'ul',
                children: [
                    {
                        type: 'li',
                        children: 'React'
                    },
                    {
                        type: 'li',
                        children: 'Vue'
                    },
                ]
            }
        ]
    }

主要转化为：

type：实际的标签
props：标签内部的属性（除了key和ref，会形成单独的key名）
children：节点内容
key：组件内的唯一标识，用于Diff算法
ref：用于访问原生dom节点
owner：当前正在构建的Component所属的Component
$$typeof：默认为REACT_ELEMENT_TYPE，可以防止XSS攻击

从结构上说，虚拟dom没有真实dom那些乱七八糟的东西，因此我们就算删除掉一个虚拟dom，重新建一个也是非常快的。

1.3 react中组件为何要大写

我们写的代码最终是要呈现在浏览器上，浏览器会识别你的代码是React吗？很显然，浏览器并不知道你的代码是React,更不会识别JSX了，实际上浏览器对ES6的一些语法都识别不了，要想让浏览器识别，就需要借助Babel。

要通过Babel去对JSX进行转化为对应的JS对象，才能让浏览器识别，此时就会有个依据去判断是原生DOM标签，还是React组件，而这个依据就是标签的首字母。

如果标签的首字母是小写，就是原生标签；反之就是react组件。

    class Info extends React.Component {
        render(){
            return(
                <div>
                    Hi！yoimiya!
                    <p>欢迎</p>
                    <Children>我是子组件</Children>
                </div>
            )
        }
    }

上述代码会被转化为：

    class Info extends React.Component {
        render(){
            return React.createElement(
                'div', 
                null, 
                "Hi！yoimiya!",
                React.createElement('p', null, '欢迎')， // 原生标签
                React.createElement( 
                    Children, //自定义组件
                    null, // 属性
                    '我是子组件'  //child文本内容
                )
            )
        }
    }

1.3.1 React.Fragment

此处顺便说一下React.Fragment这个组件。

在react中，组件是不允许返回多个节点的。

比如要return 若干个p，必须在外面套一层div

    return <div>
       <p>1</p>
       <p>2</p>
       <p>3</p>
    </div>

但是这样做的话就会多增加一个节点，造成性能和内存的损耗，因此官方在react16推出了Fragment的概念，可以让一个组件返回多个元素。

    return <React.Fragment> 
       <p>1</p>
       <p>2</p>
       <p>3</p>
    </React.Fragment>

这样就不会新增节点了

<React.Fragment> </React.Fragment> 等价于 <></>，但是在一种情况时有不同：

  [1,2,3].map(item=><p key={item} >{item}</p>)

比如这种循环创建p节点，实际上会被React底层进行处理，默认加入Fragment

    <React.Fragment> 
       <p>1</p>
       <p>2</p>
       <p>3</p>
    </React.Fragment>

在循环数组时，我们必须有key，而<React.Fragment>这种写法允许有key，<></>这种写法是无法附上key的。

1.4 虚拟dom优势

(1) 提高开发效率
使用原生JS的时候，我们需要的关注点在操作DOM上，而React会通过虚拟DOM来确保DOM的匹配，也就是说，我们关注的点不再是如何操作DOM，怎样更新DOM，React会将这一切处理好。

(2) 提升性能
React虚拟DOM在组件状态发生变化时，构造新的虚拟DOM树并依赖算法计算出与上一个虚拟DOM树的差异，只针对变化的部分执行真实DOM操作。

相较于原生DOM每次数据发生改变就去创建一个真实DOM，经过比较去修改真实DOM的操作，React虚拟DOM将多次操作合并为一次操作，提高了渲染效率。

要注意的是，虚拟dom也不一定会提高性能。
虚拟dom的计算也是需要消耗性能的，所以计算消耗的性能可能多于节省下来的dom操作性能。

1.5 预防XSS攻击

XSS攻击即跨站脚本攻击，通常指的是通过利用开发时留下的漏洞，通过巧妙的方法注入恶意指令代码到网页，使用户加载并执行攻击者恶意制造的网页程序。

React自身可以预防XSS,主要依靠的就是$$typeof属性，默认值为REACT_ELEMENT_TYPE，该值是Symbol类型。

原理是如果攻击者恶意伪造一个类似React element对象的数据返回给前端，React就会执行恶意代码。
因此从react14版本开始，React为每个element添加了一个Symbol标志：

$$typeof: Symbol.for('react.element')

因为JSON不支持Symbol，因此即使是服务端有风险漏洞并且返回一个JSON，这个JSON也不会包含Symbol.for('react.element')。因此react可以在渲染时把没有$$typeof标识的组件过滤掉，从而达到预防XSS的功能。

1.6 转化为真实DOM

处理参数：处理好组件后需要通过ReactDom.render()进行组件渲染，这里会判断是原生组件还是react组件
批量处理：统一处理虚拟DOM
生成html：对特殊的DOM标签、props进行处理，并根据对应的标签类型创造对应的DOM节点，利用updateDOMProperties将props插入到DOM节点，最后渲染到上面
渲染html：渲染html节点，渲染文本节点，但不同的浏览器可能会做不同的处理

2. diff算法

经过上面的解析，我们知道react会维护两棵虚拟dom树，那么react如何来比较判断出最优的解法呢，这里就用到了diff算法。

react中的diff算法并非首创。而是引入，但是react对传统的diff算法作出了质的优化，再将虚拟dom和diff算法相结合。

2.1 react diff大致流程

react diff算法会对新旧两棵树做深度优先遍历，避免对两棵树做完全比较，因此算法复杂度可以达到O(n)。然后给每个节点生成一个唯一的标志：

再将新旧两棵树作比较，并且只对同一级别的元素进行比较，也就是只比较图中用虚线连接起来的部分，把前后差异记录下来：

在计算一颗树转化为另一颗树有哪些改变时，传统的diff算法通过循环递归对节点进行依此对比，其算法复杂度达到了O(n^3)，也就是说，如果展示一千个节点，就要计算十亿次。
React中的diff算法，算法复杂度为O(n),如果展示一千个节点，只需要计算一千次。

react是如何实现如此巨大的优化的呢？

tree diff： WEB UI中DOM节点跨层级的移动操作特别少，可以忽略不计
component diff： 拥有相同类的两个组件会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构
element diff： 对于同一层级的一组子节点，它们可以通过唯一id进行区分

2.2 tree diff

tree diff主要针对的是React dom节点跨层级的操作。 由于跨层级的DOM移动操作较少，所以React diff算法的tree diff没有针对此种操作进行深入比较，只是简单进行了删除和创建操作

既然DOM节点跨层级的移动操作少到可以忽略不计，那么React通过updateDepth对虚拟DOM树进行层级控制：也就是同一层在对比的过程中，如果发现节点缺失，会直接删除掉整颗树而不会再比较别的地方，这样只需要遍历一次树即可。

如图：

首先比较时会一层层地比较，也就是图中蓝框那样
比较到第二层时发现L带着B和C从A下面跑到了R下面，按理来说diff算法应该将L移到R下方，但是这样会牵涉跨层级比较，有可能会移动很多个层级，导致时间复杂度大幅上升
所以在这里，当A节点发现L消失了，会直接删除掉L；而当R节点发现多出来一个L，则会创建新的L（包括L的子节点）

由此可以发现，当出现节点跨层级移动时，并不会出现想象中的移动操作，而是以L为根节点的整个树被重新创建。这是一种影响React性能的操作，因此官方建议不要进行DOM节点跨层级的操作。

注意：保持DOM的稳定会有助于性能的提升，合理的利用CSS显示和隐藏效果会更好，而不是真正的删除或增加DOM节点

2.3 component diff

component diff是专门针对更新前后的同一层级间的React组件比较的diff算法

React对于组件的策略有两种方式，分别对应于相同类型的组件和不同类型的组件。

对于相同的组件来说： 按照tree diff继续比较虚拟dom即可，当组件A变化为组件B时，有可能虚拟DOM并没有任何变化，所以用户可以通过shouldComponentUpdate() 来判断是否需要更新和计算
对于不同类型组件来说： react会直接判定该组件为dirty component（脏组件），无论结构是否相似，只要被判断为脏组件就会直接替换整个组件的所有节点

如图：
在比较时发现D不同于G，虽然两个组件的结构非常相似，React判断这两个组件并不是同一个组件（dirty component），就会直接删除D，重新构建G。

在实际中，两个组件不同，但结构又非常相似，这样的情况也很少。

2.4 element diff

element diff是专门针对同一层级的所有节点（包括元素节点和组件节点）的diff算法。

当节点处于同一层级时，diff 提供了 3 种节点操作，分别为INSERT_MARKUP、MOVE_EXISTING和REMOVE_NODE。（插入，移动和删除）

我们将虚拟dom树中欲比较的某同一层级的所有节点的集合分别称为新集合和旧集合，则有以下策略：

INSERT_MARKUP： 新集合的某个类型组件或者元素节点不存在旧集合里，也就是全新的节点，那么就对该全新节点执行插入操作

如：C 不在集合A、B中需要插入
MOVE_EXISTING： 新集合的某个类型组件或元素节点存在旧集合里，且element是可更新的类型，generateComponent-Children已调用receiveComponent，这种情况下prevChild=nextChild，就需要做移动操作，可以复用以前的DOM节点

如：组件D在集合 A、B、C、D中，且集合更新时，D没有发生更新，只是位置发生了改变，如：A、D、B、C，D的位置由4变换到了2

如果是传统的diff，会让旧集合的第二个B和新集合的D做比较，删除第二个B，再插入D

React中的diff并不会这么做，而是通过key来进行直接移动
REMOVE_NODE： 旧集合的某个组件或节点类型，在新集合里也有，但对应的element不同则不能直接复用和更新，需要执行删除操作；或者旧组件或节点不在新集合里的，也需要执行删除操作。

如：组件D在集合 A、B、C、D中，如果集合变成了新的集合A、B、C，D就需要删除

如果D的节点发生改变，不能复用和更新，此时会删除旧的D，再创建新的

2.4.1 情形一：同层级节点只发生了位置变化

React会判断新中第一个B是否在旧的中出现过，如果发现旧的中存在，然后判断是否去移动B
判断B是否移动的条件为index < lastIndex,B在旧的Index为1，lastIndex为0，所以并不满足条件，因此不会移动B

lastIndex实际上是一个浮标，一开始是默认的0。每次比较后，会改变对应的值，也就是 lastIndex=(index, lastIndex)中的最大值

此时到了A的比较，在旧的中A的index为0，lastIndex为1，满足index < lastIndex,因此对A进行移动，lastIndex还是为1
相同的方法到D，index为3，lastIndex为1，D不移动，并且lastIndex为3
相同的方法到C，index为2，lastIndex为3，C移动，lastIndex不变，此时操作结束

2.4.2 情形二：既有新的节点加入，又有旧的节点删除

B与上述讲的一样，不移动，lastIndex为1
到E时，发现在旧的中并没有E这个节点，所以此时会建立，此时的lastIndex还是为1
在C中，index 为 2，lastIndex为 1，所以此时不满足index < lastIndex，故C不移动，lastIndex更新为 2
A同理，A移动，lastIndex不更新，为2
在新集合遍历完毕中，发现并没有D这个节点，所以会删除D，操作结束

2.4.3 减少将节点移入首部

来看看这种情况，如果将D移入到第一个，我们发现lastIndex为3，之后在进行比较，发现lastIndex都大于index，所以剩下的节点都会移动，所以在开发的过程中应该尽量减少节点移入首部的操作，会影响其性能。

3. 循环中的key

我们知道，在我们进行循环的时候要加入key，那么为什么不能用index作为key值呢？key值又应该如何设置呢？

3.1 为什么不能用index作为key值？

会发现当我们判断新集合中第一个元素B时，此时的key等于index等于0，但是在旧集合中key为0的是A，B和A明显不是一个组件，因此会删除重建。

因此就导致：无论移动，新增还是删除，都会导致节点的删除和重新建立。

比如当前遍历的所有节点类型都相同，其内部文本不同，在用index作key的情况下，当我们对原始的数据list进行了某些元素的顺序改变操作，导致了新旧集合中在进行diff比较时，相同index所对应的新旧的节点其文本不一致了，就会出现一些节点需要更新渲染文本。

而如果用了其他稳定的唯一标识符作为key，则只会发生位置顺序变化，无需更新渲染文本，提升了性能。

{this.state.data.map((v,index) => <Item key={index} v={v} />)}
// 开始时：['a','b','c']=>
<ul>
    <li key="0">a <input type="text"/></li>
    <li key="1">b <input type="text"/></li>
    <li key="2">c <input type="text"/></li>
</ul>

// 数组重排 -> ['c','b','a'] =>
<ul>
    <li key="0">c <input type="text"/></li>
    <li key="1">b <input type="text"/></li>
    <li key="2">a <input type="text"/></li>
</ul>

同样也不能用index去拼接别的值作为key，因为每一个节点都找不到对应的key，导致所有的节点都不能复用，都会重新创建。

3.2 该如何设置key？

通过给每个节点设置唯一值作为key，才能真正起到diff算法的作用。