摘要：的做法比較簡單，它會先刪除整個(gè)子樹，然后再重新創(chuàng)建一遍。同樣道理，當(dāng)節(jié)點(diǎn)改為節(jié)點(diǎn)時(shí)，整棵子樹也會被刪掉，節(jié)點(diǎn)會重新創(chuàng)建。更新為和中較大的。到此為止，整個(gè)源碼解讀系列先告一段落了，后會有期。

歡迎關(guān)注我的公眾號睿Talk，獲取我最新的文章：

React 是一個(gè)十分龐大的庫，由于要同時(shí)考慮 ReactDom 和 ReactNative ，還有服務(wù)器渲染等，導(dǎo)致其代碼抽象化程度很高，嵌套層級非常深。閱讀 React 源碼是一個(gè)非常艱辛的過程，在學(xué)習(xí)過程中給我?guī)椭畲蟮木褪沁@個(gè)系列文章。作者對代碼的調(diào)用關(guān)系梳理得非常清楚，而且還有配圖幫助理解，非常值得一讀。站在巨人的肩膀之上，我嘗試再加入自己的理解，希望對有志于學(xué)習(xí) React 源碼的讀者帶來一點(diǎn)啟發(fā)。

本系列文章基于 React 15.4.2 ，以下是本系列其它文章的傳送門：
React 源碼深度解讀（一）：首次 DOM 元素渲染 - Part 1
React 源碼深度解讀（二）：首次 DOM 元素渲染 - Part 2
React 源碼深度解讀（三）：首次 DOM 元素渲染 - Part 3
React 源碼深度解讀（四）：首次自定義組件渲染 - Part 1
React 源碼深度解讀（五）：首次自定義組件渲染 - Part 2
React 源碼深度解讀（六）：依賴注入
React 源碼深度解讀（七）：事務(wù) - Part 1
React 源碼深度解讀（八）：事務(wù) - Part 2
React 源碼深度解讀（九）：單個(gè)元素更新
React 源碼深度解讀（十）：Diff 算法詳解

React 在比較新舊 2 棵虛擬 DOM 樹的時(shí)候，會同時(shí)考慮兩點(diǎn)：

盡量少的創(chuàng)建 / 刪除節(jié)點(diǎn)，多使用移動節(jié)點(diǎn)的方式

比較次數(shù)要盡量少，算法要足夠的快

如果只考慮第一點(diǎn)，算法的時(shí)間復(fù)雜度要達(dá)到 O(n3) 的級別。也就是說對于一個(gè)有 1000 個(gè)節(jié)點(diǎn)的樹，要進(jìn)行 10 億次的比較，這對于前端應(yīng)用來說是完全不可接受的。因此，React 選用了啟發(fā)式的算法，將時(shí)間復(fù)雜度控制在 O(n) 的級別。這個(gè)算法基于以下 2 個(gè)假設(shè)：

如果 2 個(gè)節(jié)點(diǎn)的類型不一樣，以這 2 個(gè)節(jié)點(diǎn)為根結(jié)點(diǎn)的樹會完全不同

對于多次 render 中結(jié)構(gòu)保持不變的節(jié)點(diǎn)，開發(fā)者會用一個(gè) key 屬性標(biāo)識出來，以便重用

另外，React 只會對同一層的節(jié)點(diǎn)作比較，不會跨層級比較，如圖所示：

Diff 使用的是深度優(yōu)先算法，當(dāng)遇到下圖這樣的情況：

最高效的算法應(yīng)該是直接將 A 子樹移動到 D 節(jié)點(diǎn)，但這樣就涉及到跨層級比較，時(shí)間復(fù)雜度會陡然上升。React 的做法比較簡單，它會先刪除整個(gè) A 子樹，然后再重新創(chuàng)建一遍。結(jié)合到實(shí)際的使用場景，改變一個(gè)組件的從屬關(guān)系的情況也是很少的。

同樣道理，當(dāng) D 節(jié)點(diǎn)改為 G 節(jié)點(diǎn)時(shí)，整棵 D 子樹也會被刪掉，E、F 節(jié)點(diǎn)會重新創(chuàng)建。

對于列表的 Diff，節(jié)點(diǎn)的 key 有助于節(jié)點(diǎn)的重用：

如上圖所示，當(dāng)沒有 key 的時(shí)候，如果中間插入一個(gè)新節(jié)點(diǎn)，Diff 過程中從第三個(gè)節(jié)點(diǎn)開始的節(jié)點(diǎn)都是刪除舊節(jié)點(diǎn)，創(chuàng)建新節(jié)點(diǎn)。當(dāng)有 key 的時(shí)候，除了第三個(gè)節(jié)點(diǎn)是新創(chuàng)建外，第四和第五個(gè)節(jié)點(diǎn)都是通過移動實(shí)現(xiàn)的。

在了解了總體的 Diff 策略后，我們來近距離的審視源碼。先更新示例代碼，注意 li 元素沒有使用 key ：

class App extends Component {
  constructor(props) {
    super(props);
    this.state = {
      data : ["one", "two"],
    };

    this.timer = setInterval(
      () => this.tick(),
      5000
    );
  }

  tick() {
    this.setState({
      data: ["new", "one", "two"],
    });
  }

  render() {
    return (
      

      {
        this.state.data.map(function(val, i) {
          return 
{ val }
;
        })
      }
      
    );
  }
}

export default App;

元素變化如下圖所示，5 秒后會新增一個(gè) new 元素。

我們跳過前面的邏輯，直接來看 Diff 的代碼

_updateRenderedComponent: function (transaction, context) {
    var prevComponentInstance = this._renderedComponent;
    // 之前的 Virtual DOM
    var prevRenderedElement = prevComponentInstance._currentElement;
    // 最新的 Virtual DOM
    var nextRenderedElement = this._renderValidatedComponent();

    var debugID = 0;
    if (__DEV__) {
        debugID = this._debugID;
    }

    if (shouldUpdateReactComponent(prevRenderedElement,
            nextRenderedElement)) {
        ReactReconciler.receiveComponent(
            prevComponentInstance,
            nextRenderedElement,
            transaction,
            this._processChildContext(context)
        );
    } else {
        ...
    }
},

// shouldUpdateReactComponent.js
function shouldUpdateReactComponent(prevElement, nextElement) {
    var prevEmpty = prevElement === null || prevElement === false;
    var nextEmpty = nextElement === null || nextElement === false;
    if (prevEmpty || nextEmpty) {
        return prevEmpty === nextEmpty;
    }

    var prevType = typeof prevElement;
    var nextType = typeof nextElement;
    if (prevType === "string" || prevType === "number") {
        return (nextType === "string" || nextType === "number");
    } else {
        return (
            nextType === "object" &&
            prevElement.type === nextElement.type &&
            prevElement.key === nextElement.key
        );
    }
}

_updateRenderedComponent方法位于 ReactCompositeComponent 內(nèi)。它先獲取新、舊 2 個(gè) Virtual DOM，然后通過shouldUpdateReactComponent判斷節(jié)點(diǎn)類型是否相同。在我們的例子里，跟節(jié)點(diǎn)都是 ul 元素，因此跳過中間的層級后，會走到 ReactDOMComponent 的 updateComponent 方法。他會更新屬性和子元素，更新屬性部分上一篇文章已經(jīng)講清楚了，下面看看更新子元素部分。最終會調(diào)用 ReactMultiChild 的 _updateChildren ：

_updateChildren: function (nextNestedChildrenElements, transaction, context) {
    ...
    
    var nextChildren = this._reconcilerUpdateChildren(
                prevChildren,
                nextNestedChildrenElements,
                mountImages,
                removedNodes,
                transaction,
                context
            );
            
    ...
    
    for (name in nextChildren) {
        if (!nextChildren.hasOwnProperty(name)) {
            continue;
        }
        var prevChild = prevChildren && prevChildren[name];
        var nextChild = nextChildren[name];
        if (prevChild === nextChild) {
            updates = enqueue(
                updates,
                this.moveChild(prevChild, lastPlacedNode,
                    nextIndex, lastIndex)
            );
            lastIndex = Math.max(prevChild._mountIndex,
                lastIndex);
            prevChild._mountIndex = nextIndex;
        } else {
            if (prevChild) {
                // Update `lastIndex` before `_mountIndex` gets unset by unmounting.
                lastIndex = Math.max(prevChild._mountIndex,
                    lastIndex);
                // The `removedNodes` loop below will actually remove the child.
            }
            // The child must be instantiated before it"s mounted.
            updates = enqueue(
                updates,
                this._mountChildAtIndex(
                    nextChild,
                    mountImages[nextMountIndex],
                    lastPlacedNode,
                    nextIndex,
                    transaction,
                    context
                )
            );
            nextMountIndex++;
        }
        nextIndex++;
        lastPlacedNode = ReactReconciler.getHostNode(nextChild);
    }
    // Remove children that are no longer present.
    for (name in removedNodes) {
        if (removedNodes.hasOwnProperty(name)) {
            updates = enqueue(
                updates,
                this._unmountChild(prevChildren[name],
                    removedNodes[name])
            );
        }
    }
    if (updates) {
        processQueue(this, updates);
    }
    this._renderedChildren = nextChildren;
},

_reconcilerUpdateChildren: function (
    prevChildren,
    nextNestedChildrenElements,
    mountImages,
    removedNodes,
    transaction,
    context
) {
    var nextChildren;
    var selfDebugID = 0;
    
    nextChildren = flattenChildren(nextNestedChildrenElements,
        selfDebugID);
        
    ReactChildReconciler.updateChildren(
        prevChildren,
        nextChildren,
        mountImages,
        removedNodes,
        transaction,
        this,
        this._hostContainerInfo,
        context,
        selfDebugID
    );
    return nextChildren;
},

在開始 Diff li 元素之前，它會先調(diào)用_reconcilerUpdateChildren去更新 li 元素的子元素，也就是文本。在函數(shù)中調(diào)用了flattenChildren方法，將數(shù)組轉(zhuǎn)換成對象：

function flattenSingleChildIntoContext(
    traverseContext: mixed,
    child: ReactElement < any > ,
    name: string,
    selfDebugID ? : number,
): void {
    // We found a component instance.
    if (traverseContext && typeof traverseContext === "object") {
        const result = traverseContext;
        const keyUnique = (result[name] === undefined);
        
        if (keyUnique && child != null) {
            result[name] = child;
        }
    }
}

function flattenChildren(
    children: ReactElement < any > ,
    selfDebugID ? : number,
): ? {
    [name: string]: ReactElement < any >
} {
    if (children == null) {
        return children;
    }
    var result = {};

    traverseAllChildren(children, flattenSingleChildIntoContext, result);   
    
    return result;
}

// traverseAllChildren.js
function traverseAllChildren(children, callback, traverseContext) {
    if (children == null) {
        return 0;
    }

    return traverseAllChildrenImpl(children, "", callback, traverseContext);
}

function traverseAllChildrenImpl(
    children,
    nameSoFar,
    callback,
    traverseContext
) {
    var type = typeof children;

    if (type === "undefined" || type === "boolean") {
        // All of the above are perceived as null.
        children = null;
    }

    if (children === null ||
        type === "string" ||
        type === "number" ||
        // The following is inlined from ReactElement. This means we can optimize
        // some checks. React Fiber also inlines this logic for similar purposes.
        (type === "object" && children.$$typeof === REACT_ELEMENT_TYPE)) {
        callback(
            traverseContext,
            children,
            // If it"s the only child, treat the name as if it was wrapped in an array
            // so that it"s consistent if the number of children grows.
            nameSoFar === "" ? SEPARATOR + getComponentKey(children, 0) :
            nameSoFar
        );
        return 1;
    }

    var child;
    var nextName;
    var subtreeCount = 0; // Count of children found in the current subtree.
    var nextNamePrefix = nameSoFar === "" ? SEPARATOR : nameSoFar +
        SUBSEPARATOR;

    if (Array.isArray(children)) {
        for (var i = 0; i < children.length; i++) {
            child = children[i];
            nextName = nextNamePrefix + getComponentKey(child, i);
            subtreeCount += traverseAllChildrenImpl(
                child,
                nextName,
                callback,
                traverseContext
            );
        }
    }
    
    ...

    return subtreeCount;
}

function getComponentKey(component, index) {
    // Do some typechecking here since we call this blindly. We want to ensure
    // that we don"t block potential future ES APIs.
    if (component && typeof component === "object" && component.key != null) {
        // Explicit key
        return KeyEscapeUtils.escape(component.key);
    }
    // Implicit key determined by the index in the set
    return index.toString(36);
}

flattenSingleChildIntoContext作為flattenChildren的回調(diào)函數(shù)，會作用在每一個(gè)數(shù)組元素上，構(gòu)造一個(gè)對象（result）。對象的 key 是通過getComponentKey這個(gè)方法生成的，可以看到如果沒有定義 key 屬性，則默認(rèn)會用數(shù)組的 index 作為 key 。最終構(gòu)造出來的對象是這個(gè)樣子的：

然后就會調(diào)用ReactChildReconciler.updateChildren方法，去更新 li 的文本和創(chuàng)建新的 li 元素。

updateChildren: function (
    prevChildren,
    nextChildren,
    mountImages,
    removedNodes,
    transaction,
    hostParent,
    hostContainerInfo,
    context,
    selfDebugID // 0 in production and for roots
) {
    if (!nextChildren && !prevChildren) {
        return;
    }
    var name;
    var prevChild;
    for (name in nextChildren) {
        if (!nextChildren.hasOwnProperty(name)) {
            continue;
        }
        prevChild = prevChildren && prevChildren[name];
        var prevElement = prevChild && prevChild._currentElement;
        var nextElement = nextChildren[name];
        
        if (prevChild != null &&
            shouldUpdateReactComponent(prevElement, nextElement)) {
            ReactReconciler.receiveComponent(
                prevChild, nextElement, transaction, context
            );
            nextChildren[name] = prevChild;
        } else {
            if (prevChild) {
                removedNodes[name] = ReactReconciler.getHostNode(
                    prevChild);
                ReactReconciler.unmountComponent(prevChild, false);
            }
            // The child must be instantiated before it"s mounted.
            var nextChildInstance = instantiateReactComponent(
                nextElement, true);
            nextChildren[name] = nextChildInstance;
            // Creating mount image now ensures refs are resolved in right order
            // (see https://github.com/facebook/react/pull/7101 for explanation).
            var nextChildMountImage = ReactReconciler.mountComponent(
                nextChildInstance,
                transaction,
                hostParent,
                hostContainerInfo,
                context,
                selfDebugID
            );
            mountImages.push(nextChildMountImage);
        }
    }
    // Unmount children that are no longer present.
    for (name in prevChildren) {
        if (prevChildren.hasOwnProperty(name) &&
            !(nextChildren && nextChildren.hasOwnProperty(name))) {
            prevChild = prevChildren[name];
            removedNodes[name] = ReactReconciler.getHostNode(
                prevChild);
            ReactReconciler.unmountComponent(prevChild, false);
        }
    }
},

在更新 li 前，會根據(jù) key 去取上一次 render 對應(yīng)的元素prevChild = prevChildren && prevChildren[name]。以第 0 個(gè)元素為例，prevElement 為 ReactElement[3]（ key 為‘.0’），而 nextElement 為 ReactElement[2]，因此會調(diào)用ReactReconciler.receiveComponent來更新文本元素，過程與上一篇文章一樣。

當(dāng)遍歷到最后一個(gè) li ，由于沒有 prevChild，會創(chuàng)建一個(gè)新的實(shí)例。

再回到 ReactMultiChild 的 _updateChildren 方法，這時(shí)nextChildren已經(jīng)創(chuàng)建好，開始遍歷：

_updateChildren: function (nextNestedChildrenElements, transaction, context) {
    ...
    
    var nextChildren = this._reconcilerUpdateChildren(
                prevChildren,
                nextNestedChildrenElements,
                mountImages,
                removedNodes,
                transaction,
                context
            );
            
    ...
    
    for (name in nextChildren) {
        if (!nextChildren.hasOwnProperty(name)) {
            continue;
        }
        var prevChild = prevChildren && prevChildren[name];
        var nextChild = nextChildren[name];
        if (prevChild === nextChild) {    ------------------------------------ 1）
            updates = enqueue(
                updates,
                this.moveChild(prevChild, lastPlacedNode,
                    nextIndex, lastIndex)
            );
            lastIndex = Math.max(prevChild._mountIndex,
                lastIndex);
            prevChild._mountIndex = nextIndex;
        } else {                          ------------------------------------ 2）
            if (prevChild) {
                // Update `lastIndex` before `_mountIndex` gets unset by unmounting.
                lastIndex = Math.max(prevChild._mountIndex,
                    lastIndex);
                // The `removedNodes` loop below will actually remove the child.
            }
            // The child must be instantiated before it"s mounted.
            updates = enqueue(
                updates,
                this._mountChildAtIndex(
                    nextChild,
                    mountImages[nextMountIndex],
                    lastPlacedNode,
                    nextIndex,
                    transaction,
                    context
                )
            );
            nextMountIndex++;
        }
        nextIndex++;
        lastPlacedNode = ReactReconciler.getHostNode(nextChild);
    }
    // Remove children that are no longer present.
    for (name in removedNodes) {
        if (removedNodes.hasOwnProperty(name)) {
            updates = enqueue(
                updates,
                this._unmountChild(prevChildren[name],
                    removedNodes[name])
            );
        }
    }
    if (updates) {
        processQueue(this, updates);
    }
    this._renderedChildren = nextChildren;
},

前面 2 個(gè) li 元素會走到分支 1），第三個(gè)元素會到分支 2）,創(chuàng)建新的 li 元素，過程與上一篇的類似。

例子改一下，加入 key：

class App extends Component {
    constructor(props) {
        super(props);
        this.state = {
            data: ["one", "two"]
        };

        this.timer = setTimeout(() => this.tick(), 5000);
    }

    tick() {
        this.setState({
            data: ["new", "one", "two"]
        });
    }

    render() {
        return (
            

                {
                    this.state.data.map(function (val, i) {
                         return 
{ val }
;
                    })
                }
            
        );
    }
}

流程與無 key 類似，不再贅述。flattenChildren后的對象是這個(gè)樣子的：

由于使用了 key ，ReactChildReconciler.updateChildren不再需要更新 text 了，只需要?jiǎng)?chuàng)建一個(gè)新的實(shí)例。

然后到 ReactMultiChild 的 _updateChildren ：

_updateChildren: function (nextNestedChildrenElements, transaction, context) {
    ...
    
    for (name in nextChildren) {
        if (!nextChildren.hasOwnProperty(name)) {
            continue;
        }
        var prevChild = prevChildren && prevChildren[name];
        var nextChild = nextChildren[name];
        if (prevChild === nextChild) {    ------------------------------------ 1）
            updates = enqueue(
                updates,
                this.moveChild(prevChild, lastPlacedNode,
                    nextIndex, lastIndex)
            );
            lastIndex = Math.max(prevChild._mountIndex,
                lastIndex);
            prevChild._mountIndex = nextIndex;
        } else {                          ------------------------------------ 2）
            if (prevChild) {
                // Update `lastIndex` before `_mountIndex` gets unset by unmounting.
                lastIndex = Math.max(prevChild._mountIndex,
                    lastIndex);
                // The `removedNodes` loop below will actually remove the child.
            }
            // The child must be instantiated before it"s mounted.
            updates = enqueue(
                updates,
                this._mountChildAtIndex(
                    nextChild,
                    mountImages[nextMountIndex],
                    lastPlacedNode,
                    nextIndex,
                    transaction,
                    context
                )
            );
            nextMountIndex++;
        }
        nextIndex++;
        lastPlacedNode = ReactReconciler.getHostNode(nextChild);
    }
    // Remove children that are no longer present.
    for (name in removedNodes) {
        if (removedNodes.hasOwnProperty(name)) {
            updates = enqueue(
                updates,
                this._unmountChild(prevChildren[name],
                    removedNodes[name])
            );
        }
    }
    if (updates) {
        processQueue(this, updates);
    }
    this._renderedChildren = nextChildren;
},

匹配第一個(gè)元素的時(shí)候，會到分支 2），后面 2 個(gè)元素都是走分支 1）。

有 key 跟沒 key 相比，減少了 2 次文本元素的更新，提高了效率。

再來考慮更復(fù)雜的情況：

假設(shè)要做上圖的變化，再來分析下源碼：

_updateChildren: function (nextNestedChildrenElements, transaction, context) {
    ...
    
    var nextIndex = 0;
    var lastIndex = 0;
    var nextMountIndex = 0;
    var lastPlacedNode = null;
            
    for (name in nextChildren) {
        if (!nextChildren.hasOwnProperty(name)) {
            continue;
        }
        var prevChild = prevChildren && prevChildren[name];
        var nextChild = nextChildren[name];
        if (prevChild === nextChild) {    ------------------------------------ 1）
            updates = enqueue(
                updates,
                this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex)
            );
            lastIndex = Math.max(prevChild._mountIndex, lastIndex);
            prevChild._mountIndex = nextIndex;
        } else {                          ------------------------------------ 2）
            if (prevChild) {
                // Update `lastIndex` before `_mountIndex` gets unset by unmounting.
                lastIndex = Math.max(prevChild._mountIndex, lastIndex);
                // The `removedNodes` loop below will actually remove the child.
            }
            // The child must be instantiated before it"s mounted.
            updates = enqueue(
                updates,
                this._mountChildAtIndex(
                    nextChild,
                    mountImages[nextMountIndex],
                    lastPlacedNode,
                    nextIndex,
                    transaction,
                    context
                )
            );
            nextMountIndex++;
        }
        nextIndex++;
        lastPlacedNode = ReactReconciler.getHostNode(nextChild);
    }
    ...
},

moveChild: function (child, afterNode, toIndex, lastIndex) {
    // If the index of `child` is less than `lastIndex`, then it needs to
    // be moved. Otherwise, we do not need to move it because a child will be
    // inserted or moved before `child`.
    if (child._mountIndex < lastIndex) {
        return makeMove(child, afterNode, toIndex);
    }
},

這里要先搞清楚 3 個(gè) index：

nextIndex：遍歷 nextChildren 時(shí)候的 index，每遍歷一個(gè)元素加 1

lastIndex：上一次從 prevChildren 中取出來元素時(shí)，這個(gè)元素在 prevChildren 中的 index

_mountIndex：元素在數(shù)組中的位置

下面我們來走一遍流程：

nextChildren 的第一個(gè)元素是 B ，在 prevChildren 中的位置是 1（_mountIndex），nextIndex 和 lastIndex 都是 0。節(jié)點(diǎn)移動的前提是_mountIndex < lastIndex，因此 B 不需要移動。lastIndex 更新為 _mountIndex 和 lastIndex 中較大的：1 。nextIndex 自增：1；

nextChildren 的第二個(gè)元素是 A ，在 prevChildren 中的位置是 0（_mountIndex），nextIndex 和 lastIndex 都是 1。這時(shí)_mountIndex < lastIndex，因此將 A 移動到 lastPlacedNode (B)的后面 。lastIndex 更新為 _mountIndex 和 lastIndex 中較大的：1 。nextIndex 自增：2；

nextChildren 的第三個(gè)元素是 D ，中 prevChildren 中的位置是 3（_mountIndex），nextIndex 是 2 ，lastIndex 是 1。這時(shí)不滿足_mountIndex < lastIndex，因此 D 不需要移動。lastIndex 更新為 _mountIndex 和 lastIndex 中較大的：3 。nextIndex 自增：3；

nextChildren 的第四個(gè)元素是 C ，中 prevChildren 中的位置是 2（_mountIndex），nextIndex 是 3 ，lastIndex 是 3。這時(shí)_mountIndex < lastIndex，因此將 C 移動到 lastPlacedNode (D)的后面。循環(huán)結(jié)束。

觀察整個(gè)過程，移動的原則是將原來的元素往右邊移，通過 lastIndex 來控制。在 lastIndex 左邊的，就往 lastIndex 的右邊移動；在 lastIndex 左邊的，不需要?jiǎng)印?/p> 六、總結(jié)

本文詳細(xì)講解了 Diff 過程中 key 的作用以及復(fù)用節(jié)點(diǎn)的移動原則，并結(jié)合源碼做了深入的討論。到此為止，整個(gè) React 源碼解讀系列先告一段落了，后會有期。