按照這個方案，其實有壹個隱含的前提——不同操作的優先級是相同的。但是在日常開發中，節點移動發生的比較少，所以Diff算法會優先考慮其他情況。
基於這個概念，主流框架(React，Vue)的Diff算法都會經過多輪遍歷，先處理常見情況，再處理不常見情況。
因此，這就要求處理異常情況的算法需要能夠覆蓋各種邊界情況。
換句話說，僅通過使用處理異常情況的算法來完成Diff運算是完全可能的。主流框架出於性能原因不會這麽做。
本文將處理常見情況的算法砍掉，保留處理異常情況的算法。
這樣實現Diff的核心邏輯只需要40行代碼。
首先，我們定義虛擬DOM節點的數據結構:
Key是節點的唯壹標識符，用於關聯更改前後的節點。
Flag表示節點需要在Diff之後對相應的real DOM執行的操作，其中:
Index表示節點在同壹級別的索引位置。
註意:本演示只實現為壹個節點標誌，不根據標誌實現DOM操作。
我們想要實現的diff方法在更新前後接收節點列表，並用flag:
例如，對於:
{ key:“D”，flag:“Placement”}表示D對應DOM需要插入的頁面。
{ key:“A”，flag:“Deletion”}表示需要刪除A對應的DOM。
執行後的結果是:頁面中的A變成了d。
另壹個例子是:
因為B之前存在，{ key:“B”，flag:“Placement”}表示B對應的DOM需要後移(對應parentNode.appendChild的方法)。手術後Abc變成acb。
由於A之前存在，{ key:“A”，flag:“Placement”}表示A對應的DOM需要後移。這次手術後Acb變成了cba。
實現後的結果是頁面中的abc變成了cba。
核心邏輯包括三個步驟:
我們將每個節點保存在壹個映射中，用node.key作為鍵，node作為值。
這樣，在復雜度為O(1)的情況下，before中對應的節點可以通過key找到:
當遍歷after時，如果壹個節點同時存在於before和after中(鍵相同)，我們稱之為可重用。
例如，在下面的例子中，b是可重用的:
對於可重用節點，這種更新必須屬於以下兩種情況之壹:
如何判斷可復用節點是否移動？
我們使用lastPlacedIndex變量來保存之前遍歷的最後壹個可重用節點的索引:
之後遍歷時，每輪遍歷的節點必須是當前遍歷的所有節點中最右邊的節點。
如果該節點是可重用節點，則nodeBefore和lastPlacedIndex之間有兩種關系:
註意:nodebefore表示before中可重用節點的對應節點。
這意味著在更新之前，該節點位於lastPlacedIndex的相應節點的左側。
更新後，該節點不在lastPlacedIndex對應的節點的左邊(因為它是當前遍歷的所有節點中最右邊的節點)。
這意味著節點已經向右移動，需要標記為放置。
節點已就位，不需要移動。
遍歷後，如果beforeMap中還有節點剩余，則意味著這些節點無法重用，需要標記並刪除。
例如，在遍歷after之後，beforeMap中還剩下{key: 'a'}:
這意味著需要標記和刪除A。
所以，最後，我們需要添加標簽刪除的邏輯: