React列表diff原理

[phenomLi]

最近因为一个可视化的项目，被导师要求去了解一些树形结构渲染相关的东西（还要做每周报告我的天）。其中有一个需求就是寻找两棵树差异的，这让我想起了React的diff算法。说起来都有好久没有去了解前端相关的东西了，现在看起来都有种与时代脱节的感觉。

React的diff其实大致就是虚拟DOM树的递归遍历，我在之前的issue已经写过虚拟DOM相关的东西了，但是当时只介绍了diff的大致思想流程，没有提到某些细节的方面，就比如今天要介绍的内容：React是如何做列表的diff的。

基本思想

列表diff换句话来说就是要找出两个线性结构的差异，如数组A是如何通过最少基本操作变成数组B的，而基本操作包括移动，插入和删除。其实要高效地找出两个线性结构的差异不是一件简单的事情，通常情况下，假如有两个数组，旧数组（原数组）元素为 A、B、C、D，新数组（目标数组）元素为B、A、D、C：

为了从旧数组得到新数组，我们对新旧数组进行diff，发现B不等于A，然后就会创建B然后插入，并删除A节点，以此类推，创建并插入 A、D、C，然后移除B、C、D。
但是，这些元素其实都没有发生改变，仅仅是位置上发生了变化，却要进行一大堆的繁琐低效的创建插入删除等操作，这在大量数据下，是不可取的。

显然，由于新旧数组的元素只发生了移动，这些移动的元素我们可以对其进行复用，也就是只需要找出哪些元素需要移动，然后对其进行移动操作即可。React使用的是一种最右访问位置算法，这种算法的思想是：遍历新数组，查看新数组元素在旧数组中的下标，如果当前访问的元素比之前访问过的所有元素在旧数组的下标的最大值（也就是最靠右）要小，那么便可判断该元素是需要移动的。看起来很复杂，其实可以这么理解：在新数组中，访问过的元素的下标肯定要比当前访问的元素的下标要小，但是在旧数组中，当前访问的这个元素的下标却比之前访问的某个元素在旧数组中的下标要小，那么这个元素肯定被移动了。

同时，因为React需要复用元素，那么便需要确定新旧数组中哪一个元素是同一个元素，因此React建议在渲染列表时最好给列表元素添加key属性以提高diff的性能：

若没有key属性，React会像上面例子一样做暴力的diff，而有了key属性后，React就可以按照算法优雅地diff了：

新旧数组和上面例子一致，只不过每个节点都加上了唯一的key，通过这个Key发现新旧数组里面其实全部都是相同的元素，只不过位置发生了改变。因此就无需进行元素的创建、插入、删除等操作了，只需要将旧树当中节点的位置进行移动就可以了。React给出的diff结果为：B、D不做操作，A、C进行移动操作。

首先，react会去循环整个新的数组：

1. 从新数组中取到B，然后去旧数组中判断是否存在相同的B，确认B存在后，再去判断是否要移动：
   B在旧数组中的index = 1，有一个游标叫做lastindex。默认lastindex = 0，然后会把旧数组的index和游标作对比来判断是否需要移动，如果index < lastindex ，那么就做移动操作，在这里B的index = 1，不满足于 index < lastindex,所以就不做移动操作，然后游标lastindex更新，取max(index, lastindex) ，这里就是lastindex = 1

2. 然后遍历到A，A在旧数组中的index = 0，此时的游标lastindex = 1，满足index < lastindex，所以对A需要移动到对应的位置，此时lastindex = max(index, lastindex) = 1

3. 然后遍历到D，D在旧数组中的index = 3，此时游标lastindex = 1，不满足index < lastindex，所以D保持不动。lastindex = max(index, lastindex) = 3

4. 然后遍历到C，C在旧数组中的index = 2，此时游标lastindex = 3，满足 index < lastindex，所以C移动到对应位置。C之后没有节点了，diff就结束了

以上主要分析新旧数组中元素相同但位置不同的情景，仅对元素进行位置移动的情况，如果新集数组中有新加入的元素且旧数组存在需要删除的节点，那么 React diff 又是如何对比运作的呢？
这便简单很多了：

• 在遍历新数组时，发现当前访问的元素不存在于旧数组，便可判断该元素需要插入

• 在遍历完成新数组后，再遍历一次旧数组，若发现某个元素不存在于新数组的，便可判断该元素需要删除

算法实现

/**
 * diff函数
 * @param {any} newList 新数组
 * @param {any} oldList 旧数组
 */
const diff = function(newList, oldList) {
    // lastIndex：即访问过元素的最右下标
    let lastIndex = 0;

    // 遍历新数组
    for(let i = 0, len = newList.length; i < len; i++) {
        // 查找当前元素在旧数组的下标
        let index = getIndex(newList[i], oldList);

        // 若该元素在旧数组中存在
        if(index !== -1) {
            // 若该元素在旧数组的下标小于最右下标lastIndex
            if(index < lastIndex) {
                // 移动元素：from index to i
                move(newList[i], i, index);
            }

            // 更新lastIndex，取index和lastIndex的较大者
            lastIndex = Math.max(index, lastIndex);
        }
        // 若该元素不在旧数组，说明这是个新加入元素
        else {
            // 插入元素：append to i
            append(newList[i], i);
        }
    }

    // 遍历旧数组
    for(let i = 0, len = oldList.length; i < len; i++) {
        // 若发现当前元素在新数组中不存在，说明这个元素需要移除
        if(getIndex(oldList[i], newList) === -1) {
            // 移除元素：remove from i
            remove(oldList[i], i);
        }
    }
}

/**
 * 找出元素在数组的下标，找不到返回-1
 * @param {T} item 要找的元素
 * @param {Array<T>} list 目标数组
 */
const getIndex = function(item, list) {
    // 对比key
    return list.findIndex(i => i.key === item.key);
}

由于我们只是演示算法，所以基本操作只需简单输出效果即可，move，append，remove函数简单实现代码如下：

const move = function(item, newPos, oldPos) {
    console.log(`${item.val} move from ${oldPos} to ${newPos}`);
}


const append = function(item, pos) {
    console.log(`${item.val} append on ${pos}`);
}


const remove = function(item, pos) {
    console.log(`${item.val} delete on ${pos}`);
}

测试结果：

---EOF---