React Diff算法

假设在 Real DOM 中存在下面这几个兄弟节点：【A、B、C、D、E、F、G】

Virtual Dom中的节点为：【D、A、G、F、K、E】

Diff算法过程：

遍历 Virtual DOM

1. 首先，第1个节点除非要被移除，否则不会被移动，于是首节D不动

2. 遍历到节点A，在Real Dom中节点A移动到节点D之后（使用DOM元素的insertBefore方法），这是第1次操作DOM 此时Real DOM为【B、C、D、A、E、F、G】

3. 遍历到节点G，由于在Real DOM 中节点G在节点A（上一个遍历到的节点）之后，与 Virtual DOM 顺序相同，因此不动 此时Real DOM为【B、C、D、A、E、F、G】

4. 遍历到节点F，由于在 Real DOM 中节点F在节点G（上一个遍历到的节点）之前，与 Virtual DOM 顺序不同，因此我们把节点F移动到节点G之后。这是第2次操作DOM 此时 Real DOM 为 【B、C、D、A、E、G、F】

5. 遍历到节点K，在 Real DOM 中不存在K节点，我们创建它，并放在节点F（上一个遍历到的节点）之后。这是第3次操作DOM 此时 Real DOM 为 【B、C、D、A、E、G、F、K】

6. 遍历到节点E，由于节点K（上一个遍历到的节点）是新创建的节点，因此我们直接把节点E移动到节点K之后。这是第4次操作DOM 此时 Real DOM 为 【B、C、D、A、G、F、K、E】

遍历real Dom

// virtual Dom【D、A、G、F、K、E】 // Real DOM 为 【B、C、D、A、G、F、K、E】

1. 移除节点B和节点C。第5、6次操作DOM

Real DOM 为【D、A、G、F、K、E】

于是，如果不考虑节点的移除和创建，我们可以推导出什么样的重新排序对这套 DOM Diff 算法最不利。最不利的结果无非就是除了首个节点外，其它所有节点都需要移动，对于有 N 个节点的数组，总共移动了 N-1 次。

例子1：考虑这个序列【A、B、C、D】，如果想变成【D、C、B、A】，应该是什么样的过程：

1. 节点D是首个节点，不执行移动。

2. 节点C移动到节点D后面：【A、B、D、C】；

3. 节点B移动到节点C后面：【A、D、C、B】；

4. 节点A移动到节点B后面：【D、C、B、A】。

dom-diff一共3步，正是 N-1。所以，可以确定的是，如果末尾的节点移动到了首位，就会引起最不利的 DOM Diff 结果。

例子2：这个序列【A、B、C、D】，变成【D、A、B、C】。我们一眼看上去就知道，只要把节点D移动到首位就可以了，但是我们看 React 它会怎么做：

1. 节点D是首个节点，不执行移动。

2. 节点A移动到节点D后面：【B、C、D、A】；

3. 节点B移动到节点A后面：【C、D、A、B】；

4. 节点C移动到节点B后面：【D、A、B、C】。

dom-diff还是 N-1，可见首个节点不执行移动这个特性，导致了只要把末尾节点移动到首位，就会引起 N-1 这种最坏的 DOM Diff 过程，所以大家要尽可能避免这种重排序。