40行代码实现React核心Diff算法

　　Diff算法的设计思路
　　试想，Diff算法需要考虑多少种情况呢？大体分三种，分别是：
　　节点属性变化，比如：更新前ullikey0classNamebefore0lilikey11liul更新后ullikey0classNameafter0lilikey11liul节点增删，比如：更新前ullikey00lilikey11lilikey22liul更新后情况1新增节点ullikey00lilikey11lilikey22lilikey33liul更新后情况2删除节点ullikey00lilikey11liul节点移动，比如：更新前ullikey00lilikey11liul更新后ullikey11lilikey00liul
　　该如何设计Diff算法呢？考虑到只有以上三种情况，一种常见的设计思路是：
　　首先判断当前节点属于哪种情况如果是增删，执行增删逻辑如果是属性变化，执行属性变化逻辑如果是移动，执行移动逻辑
　　按这个方案，其实有个隐含的前提不同操作的优先级是相同的。但在日常开发中，节点移动发生较少，所以Diff算法会优先判断其他情况。
　　基于这个理念，主流框架（React、Vue）的Diff算法都会经历多轮遍历，先处理常见情况，后处理不常见情况。
　　所以，这就要求处理不常见情况的算法需要能给各种边界case兜底。
　　换句话说，完全可以仅使用处理不常见情况的算法完成Diff操作。主流框架之所以没这么做是为了性能考虑。
　　本文会砍掉处理常见情况的算法，保留处理不常见情况的算法。
　　这样，只需要40行代码就能实现Diff的核心逻辑。
　　Demo介绍
　　首先，我们定义虚拟DOM节点的数据结构：
　　typeFlagPlacementDeletion；interfaceNode｛key：string；flag？：Flag；index？：number；｝
　　key是node的唯一标识，用于将节点在变化前、变化后关联上。
　　flag代表node经过Diff后，需要对相应的真实DOM执行的操作，其中：
　　Placement对于新生成的node，代表对应DOM需要插入到页面中。对于已有的node，代表对应DOM需要在页面中移动Deletion代表node对应DOM需要从页面中删除
　　index代表该node在同级node中的索引位置
　　注：本Demo仅实现为node标记flag，没有实现根据flag执行DOM操作。
　　我们希望实现的diff方法，接收更新前与更新后的NodeList，为他们标记flag：typeNodeListNode〔〕；functiondiff（before：NodeList，after：NodeList）：NodeList｛。。。代码｝
　　比如对于：更新前constbefore〔｛key：a｝〕更新后constafter〔｛key：d｝〕diff（before，after）输出〔｛key：d，flag：Placement｝，｛key：a，flag：Deletion｝〕
　　｛key：d，flag：Placement｝代表d对应DOM需要插入页面。
　　｛key：a，flag：Deletion｝代表a对应DOM需要被删除。
　　执行后的结果就是：页面中的a变为d。
　　再比如：更新前constbefore〔｛key：a｝，｛key：b｝，｛key：c｝，〕更新后constafter〔｛key：c｝，｛key：b｝，｛key：a｝〕diff（before，after）输出〔｛key：b，flag：Placement｝，｛key：a，flag：Placement｝〕
　　由于b之前已经存在，｛key：b，flag：Placement｝代表b对应DOM需要向后移动（对应parentNode。appendChild方法）。abc经过该操作后变为acb。
　　由于a之前已经存在，｛key：a，flag：Placement｝代表a对应DOM需要向后移动。acb经过该操作后变为cba。
　　执行后的结果就是：页面中的abc变为cba。
　　Diff算法实现
　　核心逻辑包括三步：
　　遍历前的准备工作遍历after遍历后的收尾工作functiondiff（before：NodeList，after：NodeList）：NodeList｛constresult：NodeList〔〕；。。。遍历前的准备工作for（leti0；iafter。length；i）｛。。。核心遍历逻辑｝。。。遍历后的收尾工作returnresult；｝遍历前的准备工作
　　我们将before中每个node保存在以node。key为key，node为value的Map中。
　　这样，以O（1）复杂度就能通过key找到before中对应node：
　　保存结果constresult：NodeList〔〕；将before保存在map中constbeforeMapnewMapstring，Node（）；before。forEach（（node，i）｛node。indexi；beforeMap。set（node。key，node）；｝）遍历after
　　当遍历after时，如果一个node同时存在于before与after（key相同），我们称这个node可复用。
　　比如，对于如下例子，b是可复用的：
　　更新前constbefore〔｛key：a｝，｛key：b｝〕更新后constafter〔｛key：b｝〕
　　对于可复用的node，本次更新一定属于以下两种情况之一：
　　不移动移动
　　如何判断可复用的node是否移动呢？
　　我们用lastPlacedIndex变量保存遍历到的最后一个可复用node在before中的index：
　　遍历到的最后一个可复用node在before中的indexletlastPlacedIndex0；
　　当遍历after时，每轮遍历到的node，一定是当前遍历到的所有node中最靠右的那个。
　　如果这个node是可复用的node，那么nodeBefore与lastPlacedIndex存在两种关系：
　　注：nodeBefore代表该可复用的node在before中的对应node
　　nodeBefore。indexlastPlacedIndex
　　代表更新前该node在lastPlacedIndex对应node左边。
　　而更新后该node不在lastPlacedIndex对应node左边（因为他是当前遍历到的所有node中最靠右的那个）。
　　这就代表该node向右移动了，需要标记Placement。
　　nodeBefore。indexlastPlacedIndex
　　该node在原地，不需要移动。
　　遍历到的最后一个可复用node在before中的indexletlastPlacedIndex0；for（leti0；iafter。length；i）｛constafterNodeafter〔i〕；afterNode。indexi；constbeforeNodebeforeMap。get（afterNode。key）；if（beforeNode）｛存在可复用node从map中剔除该可复用nodebeforeMap。delete（beforeNode。key）；constoldIndexbeforeNode。indexasnumber；核心判断逻辑if（oldIndexlastPlacedIndex）｛移动afterNode。flagPlacement；result。push（afterNode）；continue；｝else｛不移动lastPlacedIndexoldIndex；｝｝else｛不存在可复用node，这是一个新节点afterNode。flagPlacement；result。push（afterNode）；｝遍历后的收尾工作
　　经过遍历，如果beforeMap中还剩下node，代表这些node没法复用，需要被标记删除。
　　比如如下情况，遍历完after后，beforeMap中还剩下｛key：a｝：更新前constbefore〔｛key：a｝，｛key：b｝〕更新后constafter〔｛key：b｝〕
　　这意味着a需要被标记删除。
　　所以，最后还需要加入标记删除的逻辑：beforeMap。forEach（node｛node。flagDeletion；result。push（node）；｝）；