先来一张Dan的帅照~
带你彻底读懂React VDOM DIFF，什么叫彻底，就是原理 源码 手写。
VDOM
在React官网中，对VDOM的描述如下：
狭义一点来说，VDOM在数据形式上就是个js对象，一个描述了DOM节点的js对象。但是我们最终需要的是能够呈现在页面上的DOM，因此最终我们还需要根据VDOM来同步DOM。问题来了，同步DOM？DOM可是用户直观看到的东西，如果大动作更新DOM，那用户的看到的页面可能会延迟更新甚至出现闪烁状态，会造成用户体验极差。那怎么优化呢？
我们可不可以通过计算从而以最低成本来更新DOM页面，可以！其实这个计算的过程就是所谓的VDOM DIFF，也是协调的核心。
VDOM DIFF
React和Vue中都用到了VDOM，但是因为结构不同，因此都有自己的DIFF实现方式，但其实背后大同小异。今天我们先单独来说说React VDOM DIFF。
fiber
了解React VDOM DIFF，首先要清楚React中的VDOM的实现形式是fiber，一个链表，这是和Vue VDOM数据结构上最大的不同，也是造成React和Vue的VDOM DIFF算法不同的一个重要原因。
下图是fiber的结构图：
因为fiber就是VDOM的实现形式，因此从数据形式上来说，fiber就是个对象，源码中的fiber属性较多，下面是我简化之后定义的创建fiber的函数：
代码语言：javascript复制export function createFiber(vnode, returnFiber) {
const fiber = {
// 数据类型，原生标签的type是字符串，函数组件的type则是函数
type: vnode.type,
// 定义数据唯一性的字符串key
key: vnode.key,
props: vnode.props,
// 原生标签 DOM
// class组件 实例
stateNode: null,
// 第一个子fiber
child: null,
// 下一个兄弟fiber
sibling: null,
return: returnFiber,
// 标记fiber任务类型，节点插入、更新、删除
flags: Placement,
index: null,
// old fiber
alternate: null,
};
// 判断tag，判断fiber任务节点类型
const { type } = vnode;
if (isStr(type)) {
// 原生标签
fiber.tag = HostComponent;
} else if (isFn(type)) {
// 函数组件、类组件
fiber.tag = type.prototype.isReactComponent
? ClassComponent
: FunctionComponent;
} else if (isUndefined(type)) {
fiber.tag = HostText;
fiber.props = { children: vnode };
} else {
fiber.tag = Fragment;
}
return fiber;
}节点类型
React中存在多种组件类型，如函数组件、类组件、原生标签、文本节点等等，不同组件的主要的差异性在于组件本身的处理，如函数组件要执行函数本身，类组件是执行实例的render函数（初次渲染还要先创建实例），但是这些组件都有个共同的特点，就是协调的时候先协调自己，然后再协调子组件。
协调节点本身
这个很简单，就是判断节点是否可以复用，在React中，节点复用必须同时满足三大条件：1. 同一层级 2. 组件类型相同 3. key相同。
首先说同一层级下，如下图所示，上面的G节点和下面的G节点就不能复用，因为层级不同。当然如果你非要复用，那么找G节点就需要遍历整棵树，而实际项目中，跨层级变更节点的场景实在太少，因此跨层级复用节点实在不划算。
再说类型，实际项目中很少出现组件类型都变了，但是组件还是同一个的场景，如果还要再继续往下遍历，成本太高，覆盖场景太多，这个买卖不划算，因此不做考虑~
最后来说key，key是一个字符串，相当于组件在当前层级下的唯一id，因为同一层级下，组件类型也经常相同，那这个时候再区分节点，就需要一个唯一的key了。好了，顺便我们解决一道面试题了，key是用于判断是否可以复用新老VDOM节点的，那这个值必须得唯一且稳定的，如果你的key变来变去的，比如用Date.now()定义，那怎么复用节点呢。
协调子节点
React中的协调子节点包括节点的初次渲染以及更新，但是其实背后执行的函数式同一个，都是ChildReconciler，只是传参不同：
代码语言：javascript复制export const reconcileChildFibers = ChildReconciler(true);
export const mountChildFibers = ChildReconciler(false);ChildReconciler是一个wrapper function，核心函数是这个wrapper function返回的reconcileChildFibers，reconcileChildFibers做的事情就是判断新节点newChild的类型，再决定如何协调。
协调过程参见下面源码片段中的4条规则，其中单个子节点非常好理解，因为没有位置移动方面考虑，直接比较类型即可，文本也很好懂，直接替换即可。难点在于2.2与2.3，如果newChild是数组，那么我们需要考虑节点的位置变化，这个很麻烦，接下来我们重点说newChild为数组的情况。2.3是newChild为迭代函数的情况，和2.2算法是一样的，我们接下来只说2.2。
代码语言：javascript复制function ChildReconciler(shouldTrackSideEffects) {
//前面源码片段很长，此处省略一万字...
// 执行协调子节点的函数
function reconcileChildFibers(
returnFiber: Fiber, // 父fiber
currentFirstChild: Fiber | null, // 老的子fiber，初次渲染为null
newChild: any, // 新子节点
lanes: Lanes,
): Fiber | null {
const isUnkeyedTopLevelFragment =
typeof newChild === 'object' &&
newChild !== null &&
newChild.type === REACT_FRAGMENT_TYPE &&
newChild.key === null;
if (isUnkeyedTopLevelFragment) {
// 1. 如果是没有的key的Fragment，则本层忽略，直接下一层
// 因为Fragment最多只有一个key属性，如果连这个都没有，那没法判断是否复用，用户本意就是当个假父级，因此不需要进入diff
newChild = newChild.props.children;
}
// 2. 如果newChild是对象
if (typeof newChild === 'object' && newChild !== null) {
// 2.1 单个节点：子节点或者是传送门或者是lazy组件，1比1对比即可
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE:
// 单个子节点，1比1对比即可
return placeSingleChild(
reconcileSingleElement(
returnFiber,
currentFirstChild,
newChild,
lanes,
),
);
case REACT_PORTAL_TYPE:
// 传送门，1比1对比即可
return placeSingleChild(
reconcileSinglePortal(
returnFiber,
currentFirstChild,
newChild,
lanes,
),
);
case REACT_LAZY_TYPE:
// lazy组件，1比1对比即可
if (enableLazyElements) {
const payload = newChild._payload;
const init = newChild._init;
// TODO: This function is supposed to be non-recursive.
return reconcileChildFibers(
returnFiber,
currentFirstChild,
init(payload),
lanes,
);
}
}
if (isArray(newChild)) {
// 2.2. 如果是数组，麻烦大了，因为要考虑节点位置的变化，具体我后面详细说
return reconcileChildrenArray(
returnFiber,
currentFirstChild,
newChild,
lanes,
);
}
// 2.3. 迭代器函数，算法同reconcileChildrenArray
if (getIteratorFn(newChild)) {
return reconcileChildrenIterator(
returnFiber,
currentFirstChild,
newChild,
lanes,
);
}
// 2.4 不是以上类型，抛出异常
throwOnInvalidObjectType(returnFiber, newChild);
}
if (
(typeof newChild === 'string' && newChild !== '') ||
typeof newChild === 'number'
) {
// 3. 文本节点，直接替换
return placeSingleChild(
reconcileSingleTextNode(
returnFiber,
currentFirstChild,
'' newChild,
lanes,
),
);
}
// Remaining cases are all treated as empty.
// 4. 新节点不满足以上条件，则把剩下的老节点全部删除
return deleteRemainingChildren(returnFiber, currentFirstChild);
}
return reconcileChildFibers;
}当新子节点是数组
当新子节点为数组的时候，我们调用的是reconcileChildrenArray这个函数.
注意：组件的初次渲染与更新，调用的都是下面这个函数！还记得ChildReconciler这个函数吧，这个函数接受true代表组件更新，接收false代表组件初次渲染，在下面的函数内部，这个true或者false是通过shouldTrackSideEffects标记的~
接下来下面的代码我写出了非常详细的注释，来看一下吧~
代码语言：javascript复制function reconcileChildrenArray(
returnFiber: Fiber, // 父fiber
currentFirstChild: Fiber | null, // 老的第一个子fiber
newChildren: Array<*>, // 新子节点数组
lanes: Lanes,
): Fiber | null {
// 本函数要做的事情就是diff新老vdom，在尽可能多的复用老vdom的情况下生成新的vdom，即fiber结构，并返回新的第一个子fiber，
// 这个新的子fiber就是resultingFirstChild
let resultingFirstChild: Fiber | null = null;
// 记录上一个newFiber
// 因为fiber.sibling是指向下一个fiber，但是在构建过程中下一个fiber得到下一轮才能构建完成，因此要完成fiber与sibling的关系，
// 就要把上一轮的fiber记录下来，通过previousNewFiber.sibling来完成fiber与sibling的关联~
let previousNewFiber: Fiber | null = null;
// 老的第一个子fiber
let oldFiber = currentFirstChild;
// 记录上次插入节点的位置，以此判断节点是否需要移动
let lastPlacedIndex = 0;
// newChildren是数组，newIdx就是遍历数组用的下标
let newIdx = 0;
// 记录下一个oldFiber的值
let nextOldFiber = null;
//! step 1: 新老VDOM都是从左边开始遍历，按位比较，如果节点可以复用，那么都往后移一位，否则中止本轮循环
// 注意下面这个for，只有oldFiber不是null才可以进入，因此初次渲染是跳过这个for的
for (; oldFiber !== null && newIdx < newChildren.length; newIdx ) {
// oldFiber的下标大于新的，本轮循环中止
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else {
// 记录下一个oldFiber
nextOldFiber = oldFiber.sibling;
}
// updateSlot会比较oldFiber与newChildren[newIdx]的key，相等的话初步复用，不相等返回null
const newFiber = updateSlot(
returnFiber,
oldFiber,
newChildren[newIdx],
lanes,
);
if (newFiber === null) {
// 不能复用
if (oldFiber === null) {
// 如果oldFiber是null，本轮oldFiber没法用，用下一个试试
oldFiber = nextOldFiber;
}
// 还记得刚进来本for的规则么，按照位置比较，不能复用则中止本for
break;
}
if (shouldTrackSideEffects) {
// 更新阶段，但是没有
if (oldFiber && newFiber.alternate === null) {
// oo. 匹配得到的newFiber没有alternate，还是没法复用
deleteChild(returnFiber, oldFiber);
}
}
// 把newFiber插入到链表中，更新位置，同时根据上次的插入位置，判断newFiber是否需要移动位置
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
// previousNewFiber记录上个fiber，如果previousNewFiber为空，证明是头结点，则赋值给resultingFirstChild即可。
resultingFirstChild = newFiber;
} else {
// 上个fiber的sibling是本次的fiber
previousNewFiber.sibling = newFiber;
}
// 更新previousNewFiber，毕竟本次的fiber是下轮循环的上个fiber了
previousNewFiber = newFiber;
// 更新oldFiber
oldFiber = nextOldFiber;
}
//! step2: 如果newIdx === newChildren.length，证明经过上轮for，新节点已经遍历完了，那么如果还有剩下的老节点，删除即可
if (newIdx === newChildren.length) {
// We've reached the end of the new children. We can delete the rest.
deleteRemainingChildren(returnFiber, oldFiber);
if (getIsHydrating()) {
const numberOfForks = newIdx;
pushTreeFork(returnFiber, numberOfForks);
}
return resultingFirstChild;
}
//! step3: 如果老节点没了，新节点还有，那么新节点逐个新增即可。初次渲染走的就是这里
// 如果满足本条件，那么后面step4和step5都不用经历了，毕竟没有老节点了，没什么好比较的了
if (oldFiber === null) {
// If we don't have any more existing children we can choose a fast path
// since the rest will all be insertions.
for (; newIdx < newChildren.length; newIdx ) {
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) {
continue;
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
// TODO: Move out of the loop. This only happens for the first run.
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
if (getIsHydrating()) {
const numberOfForks = newIdx;
pushTreeFork(returnFiber, numberOfForks);
}
return resultingFirstChild;
}
//! step4: 走到现在，新老节点都还有，最麻烦的地方来了，也是React Diff的核心
// 经过上面的步骤，走到这里的新老vdom都是乱序的，因此接下来遍历新的vdom的时候，需要考虑的事情是如何去老fiber链表里找某个key对应的节点
// 因为老的fiber链表是单链表，所以如果通过循环的方式去遍历是比较慢的，总不能每次找节点都遍历一次链表吧
// 可以把老fiber链表生成一个字典，方便接下来的快速查找以及删除字典中节点的操作（关于删除，等下举例子）
// 生成字典的话，我们可以选择Object或者Map，但是考虑到效率，此处React选择的是Map，背后深究的话可以比较下Object与Map，Map的背后是哈希表，在多节点增删改查的场景下，效率会更高
// Add all children to a key map for quick lookups.
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
// Keep scanning and use the map to restore deleted items as moves.
/**
* 如果下面这段解释你能看明白，那接下来的代码就很清楚了
举例：接下来新老vdom的情况：
old: a b c
new: b c
old已经是map了，因此接下来可以遍历new，比如找到b和c，那么这个时候我们就知道a要被删除，问题是怎么记录下来要删除的节点呢？
其实这个时候我们可以这样，通过遍历new，去old中找new有的节点，比如找到b复用之后，再把b从old的map中删除，c也是同样操作。
这样的话，遍历完new之后，old的map里只剩下了a，这个时候我们再把这个map剩余的节点全部删除就行了。
*/
//
// 代码实现：
for (; newIdx < newChildren.length; newIdx ) {
// 去map里找能复用的节点
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
if (newFiber !== null) {
// 找到了，删掉map中的节点
if (shouldTrackSideEffects) {
if (newFiber.alternate !== null) {
existingChildren.delete(
newFiber.key === null ? newIdx : newFiber.key,
);
}
}
// 后面是构建fiber的过程，与前面的一样，不再多余解释了
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
}
//! step5: 经历过step4之后，发现老节点中还有没被复用的，全部删除即可
if (shouldTrackSideEffects) {
existingChildren.forEach(child => deleteChild(returnFiber, child));
}
if (getIsHydrating()) {
const numberOfForks = newIdx;
pushTreeFork(returnFiber, numberOfForks);
}
return resultingFirstChild;
}经过上面的源码阅读，我们来总结一下：
首先明确下数据结构：新vdom是数组，即newChildren；老vdom是fiber单链表，即oldFiber。
1. 新老VDOM都是从左边开始遍历的，按位置比较，即第i个老vdom和第i个新vdom比较，如果节点可以复用，那么先复用，然后新老vdom都往后移一位，否则就中止本轮循环。
2. 如果经过step1，新节点已经遍历完了，那么如果还有剩下的老节点，删除即可。
3. 如果经过step1，老节点没了，新节点还有，那么新节点逐个新增即可。初次渲染走的就是这里。
4. 走到现在，新老节点都还有，但是是乱序的。因此可以把oldFiber单链表做成Map，即existingChildren，接下来遍历newChildren，找到能复用的fiber，就复用并且从existingChildren删除这个fiber。
5. 经历过step4之后，发现老节点existingChildren中还有没被复用的，全部删除即可。
对比React 与Vue的 VDOM DIFF
这个问题太常见了，我就遇到了八百次了。回到这个问题的时候，其实重点就在于新子节点是数组的时候，因为单个节点的处理方式都一样，但是如果新子节点是数组，React和Vue的处理是有些许不同的。
首先，根本上在于数据结构的不同，因为Vue的多个新子节点时候，老子节点就是数组，而React中则是单链表。而数组是可以双向查找的，但是单链表却不可以，这就造成了第一个区别，就是Vue中都是从双向按照位置查找节点复用，但是React却只能从左边按照位置查找复用。
其次，React与Vue中为了节点的方便查找，都用到了Map这个结构，只是React是通过老子节点创建了一个Map，而Vue则是通过新子节点创建了Map。
最后，React中的遍历更循规蹈矩一些，而Vue中则通过最长递增子序列计算出了最小次数的节点移动路径。
如果你想要React与Vue的VDOM DIFF的思维导图，那么关注本公众号，回复”diff“即可获取~
总结
今天我们说完了React VDOM DIFF，也对比了下Vue VDOM DIFF，尽管它们俩不少共同点，但是Vue VDOM DIFF多了个寻找最小递增子序列的过程，稍微复杂，关于Vue VDOM DIFF的具体文章可以查看本公众号”bubucuo“，也可以去b站搜”前端bubucuo“空间的讲解视频。
如果你想要React与Vue的VDOM DIFF的代码，那么关注本公众号，回复”diff代码“即可获取~
