虚拟DOM与DIFF算法学习

摘要：比较虚拟与的差异，以及对节点的操作，其实就是树的差异比较，就是对树的节点进行替换。忽略掉这种特殊的情况后，大胆的修改了算法按直系兄弟节点比较比较。这当中对比的细节才是整个算法最精粹的地方。

       在jQuery横行的时代，FEer们，通过各种的方式去对页面的DOM进行操作，计算大小，变化，来让页面生动活泼起来，丰富的DOM操作，让一个表面简单的页面能展示出花一般的操作。

       这个时候，人们通过DOM简单的方法去对页面DOM结构作出操作和改变，每一次数据的革新，都通过复杂的操作去执行变化。直到有人指出，浏览器对于页面的paint和layout是有性能消耗的，多次layout会占用大量的浏览器计算内存。

       于是人们开始想办法去减少layout，尽可能的去利用class改变，fragment包裹，display的设置来操作dom，避免浏览器的layout发生。甚至还有人根据浏览器渲染的频率，通过requestAnimationFrame的回调来触发渲染。

       然而，随着三大框架的诞生，有一群人站出来呼吁大家放弃掉对dom的操作，用状态去控制组件的生命，用状态去控制页面的变化，而与dom打交道的事，交给他们来做就行了……

       每一个页面都是由DOM节点构成的，这可以从DOM的原意Document Object Model 文档对象模型看出来，页面文档都是通过DOM节点组成，这是HTML的基架。因此而言，想要页面是可动态变化的，就不得不去对页面做一些操作。fragment 和 requestAnimationFrame 的使用，告诉了我们，页面的操作其实可以通过一个异步的形式来完成，将多次操作合并在一次当中执行，根据一定的周期去重新改变页面的显示。
       但是很大的一个痛点就是，页面中存在多个地方的内容需要变化，那我在最后的变化关头应该如何取舍对dom的操作呢？我如何知道，哪些需要变化，哪些不需要变化呢？

       react的开发者明确了一个首要的问题，那就是如何衡量dom什么时候需要变化，什么位置需要变化。

       众所周知，每一个DOM节点都带有自身的属性，一个简单的div上面挂载了几十个attributes，显然dom其实可以看作一个对象，这是就是虚拟dom的原型——以对象的形式去模拟dom，这样子操作前后的dom就可以量化他们的区别，dom的比较就能被开发者握在手中。通过每次操作去变化dom上各对象，子对象的属性，最后统一与现有dom结构做对比，就能计算出当中的差异，最后去对这些差异进行dom操作，就可以简单的对页面进行变更。

       虚拟dom(VirtualDOM)由此产生，它是平行于dom的另一套对象体系，用于记录dom的状态，我上一篇文章对setState的介绍，其实就是对虚拟dom属性的变化操作，其中的batching就是虚拟dom最核心的阻塞功能，通过事务去控制数据在一个周期内不做多次更新，通过state去保证最后的状态即为要更新的状态。

       有了虚拟dom，对页面元素进行了抽象，其实才是虚拟dom最重要的意义，这种概念让react有了’一次编写，处处运行’的坚实基础。
       既然知道虚拟dom的实际是带有属性的对象，那么我们解决了第一个问题，也就是如何衡量dom什么时候需要变化，接下来就介绍一下如何衡量，什么位置需要变化？

       虚拟dom和dom有一个共同的特点，就是树形结构。比较虚拟dom与dom的差异，以及对dom节点的操作，其实就是树的差异比较，就是对树的节点进行替换。对于树的比较，有一个最简单的方法就是循环递归比较树的节点，也就是传统的diff算法，这个算法的复杂度达到了立方级别，效率可以说很差。
       而react使用diff算法的时候，根据应用场景大胆的改变了算法本身的难度，硬生生把算法复杂度降到了O(n)

       react diff遵循三个策略：

webUI种，dom节点跨层级移动操作特别少，所以忽略这种操作

拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构

对于同一层级的一组子节点，它们可以通过唯一id进行区分

       这么听下来，感觉这三个策略莫名奇妙，接下来，我通过diff算法在不同层次的比较，介绍diff算法如何去利用这三个策略高效更新组件的

       所谓的跨层级dom操作是指，原本在dom节点A下面的一个组件a，被移动到dom节点B下面。这种操作我见过最常见的应用场景是把左侧区域的数据添加到右侧区域，然而除了这种业务场景之外，很少有把一个dom从自身的容器中移到另一个容器中的情况，因此，策略一，这种操作在react当中默认是很少有的操作。

       忽略掉这种特殊的情况后，react大胆的修改了diff算法——按直系兄弟节点比较比较。多个组件拥有同一个父组件，归为一个组，整组与变化后的情况做对比，缺了就补上，多了就删除。一层一层的，从上至下进行按层的比较。这种比较过程中，如果发现某一个节点发生变化，可以直接不遍历其子节点，直接统一删除整个节点以及其子节点，把新节点直接替换上去，这样子大大减少了遍历的消耗。

       基于这种’粗暴的方式’来修改页面dom，如果是进行跨层级操作，则会删除一个完整节点，再新增一个完整节点，这是高消耗的事情，所以react考虑到跨层级操作很少，所以作出了react diff的优化。

react当中，组件的概念贯通全局，所以到了组件新旧的比较上，react直接给出策略：

如果是同一类型组件，按照原策略继续比较Virtual DOM树即可。

如果不是同一类型组件，则将该组件判定为dirty component，从而替换整个组件下所有子节点。

对于同一类型的组件，有可能其Virtual DOM没有任何变化，如果能确切知道这点，那么可以节省大量diff运算时间。因此，react允许通过shouldComponentUpdate()判定该组件是否需要进行diff分析。

       1、3两条对于react的使用者来说非常好理解，一样的组件，直接比较子组件的变化即可；开发者可以控制组件更新的条件，也可以对diff进行优化。

       那么第2条可能就不是那么容易被理解了，为什么不是同一类型的组件就一定直接替换呢？比如我一个A组件一个B组件，都是一个div嵌套一个p标签，里面有个span包裹的文字，两个组件只有文字不同，那我直接替换组件岂不是浪费了div、p和span标签的重新创建吗？

       这里react认为，两个不同类型的组件，在实际处理业务过程中，结构一致的概率很低。因为既然拆分为两个不同的组件，若里面的dom结构还非常相似，只能说明对组件的拆分粒度还不够。不同组件在业务上完成的事情应该是不同的，所以不去考虑结构近似的情况，直接替换组件。

       我们介绍tree diff的时候有提到过，react在对比区别的时候是通过同一个父组件下的所有兄弟节点为一组进行新老对比的。这当中对比的细节才是整个diff算法最精粹的地方。
       react对待同一层级的代码只会进行三种操作，插入，删除，移动。我们可以理解为原本没有的组件，我们进行插入操作；新的变化之后消失的组件我们进行删除操作；一个组件新旧变化之后，位置发生偏移，则使用移动操作。
       具体的移动方案，大家可以看看大神的这篇知乎，里面讲的更多例子https://zhuanlan.zhihu.com/p/...
       而我直接在react这段的代码中增加注释，带大家一起看看react diff的详细逻辑

{
_updateChildren: function(nextNestedChildrenElements, transaction, context) {
  var prevChildren = this._renderedChildren; // 变更前的现有dom
  var nextChildren = this._reconcilerUpdateChildren(
    prevChildren, nextNestedChildrenElements, transaction, context
  ); // 待更新dom
  if (!nextChildren && !prevChildren) { // 二者有一个不存在，则退出方法
    return;
  }
  var name;
  var lastIndex = 0; // 这个值非常关键，用来决定移动位置
  var nextIndex = 0; // 节点指针，填充一个位置向后移一位
  for (name in nextChildren) { // 开始遍历新节点，与老节点做对比，这里的name可以理解为组件的key，唯一标志
    if (!nextChildren.hasOwnProperty(name)) {
      continue; // porto上的属性不要
    }
    var prevChild = prevChildren && prevChildren[name];
    var nextChild = nextChildren[name];
    if (prevChild === nextChild) { //看看老节点上面有没有相同的节点，如果存在就不再新建了
      // 移动节点
      this.moveChild(prevChild, nextIndex, lastIndex);
      lastIndex = Math.max(prevChild._mountIndex, lastIndex);//新的移动下标，移动的时候老节点和移动下标，哪个大取哪个
      prevChild._mountIndex = nextIndex; // 老节点下标直接移动到现有下标位置
    } else { // 老集合里面有相同名称节点，但是内容不同了，直接把老的删了，新建一个
      if (prevChild) {
        lastIndex = Math.max(prevChild._mountIndex, lastIndex);
        // 删除节点
        this._unmountChild(prevChild);
      }
      // 初始化并创建节点
      this._mountChildAtIndex(
        nextChild, nextIndex, transaction, context
      );
    }
    nextIndex++;
  }
  for (name in prevChildren) { // 全部都遍历完了，老节点中剩余的节点删除掉
    if (prevChildren.hasOwnProperty(name) &&
        !(nextChildren && nextChildren.hasOwnProperty(name))) {
      this._unmountChild(prevChildren[name]);
    }
  }
  this._renderedChildren = nextChildren; // 新节点完成
},
// 移动节点
moveChild: function(child, toIndex, lastIndex) {
  if (child._mountIndex < lastIndex) { // 如果当前新节点下标小于已移动下标，则不用移动
    this.prepareToManageChildren();
    enqueueMove(this, child._mountIndex, toIndex);
  }
},
// 创建节点
createChild: function(child, mountImage) {
  this.prepareToManageChildren();
  enqueueInsertMarkup(this, mountImage, child._mountIndex);
},
// 删除节点
removeChild: function(child) {
  this.prepareToManageChildren();
  enqueueRemove(this, child._mountIndex);
},

_unmountChild: function(child) {
  this.removeChild(child);
  child._mountIndex = null;
},

_mountChildAtIndex: function(
  child,
  index,
  transaction,
  context) {
  var mountImage = ReactReconciler.mountComponent(
    child,
    transaction,
    this,
    this._nativeContainerInfo,
    context
  );
  child._mountIndex = index;
  this.createChild(child, mountImage);
},
}

       就此，react虚拟dom和diff算法就介绍完了，读懂上面的代码，至少要知道，react中为什么尽量减少一个dom从最后移动到最前面的操作，就算是理解了。