在前端领域中，接触到 Diff 算法基本上是基于现在的前端框架，如 React、Vue 等，目前的框架基本上都用到了 Diff 和 V-dom，而 Diff 算法作为 V-dom 的加速器，在提高性能方面有极其重要的作用，在每次的 update 都能高效的渲染新的 UI 界面，使得大家不用在关心渲染方面上的问题，只需要专注于界面和业务需求；
前端框架上的 Diff 算法和传统的 Diff 有一点区别，因为框架上有针对使用场景的策略和处理，以下只通过对比和理解传统 Diff 算法来去理解现在 React 的 Diff 在 React 中的处理；
传统 Diff 算法
传统 Diff 算法本质是计算一棵树形结构转换成另一棵树形结构的最少操作，React 本身是借助 Virtual DOM + Diff 使得它与传统的 Dom 操作有了极大的突破，但 React 的是在传统上的处理，所以我们现在先看看传统的 Diff 算法；
传统的 Diff 算法，操作包括替换、插入、删除，在对比时的复杂度为 o(n**3)。要了解它的复杂度，首先看一下下面例子
首先看计算 字符串 neigevor 与 Neigevoir 的编辑距离(Edit-Distance)
n -> N Neigevor
r -> i Neigevoi
add r Neigevoir
编辑距离 = 3
同理对于 dom 这类的对象来说也是一样，由替换、插入、删除，但相对来说比只只有 Edit-Distance 复杂;
例如：
before after
A A
/ \ / \
B D => B D
/ \
C E
\
C
B delete C
D add E
D add C
直观感受虽然只是做了 3 步，但是对于计算机来说需要对两个树进行遍历；
o(n**3) 的由来
为何遍历两个树，不能只用 before 遍历，即可 o(n)？
如果直接 before 来遍历，遇到 B 删除 C，D 的时候增加 E-C，看起来的确是，但 after 的可能性是无限的，如果变成：
before after
A E
/ \ / \
B D => A F
/ / \
C B D
/
C
再以 before 来遍历，这样遍历的时候直接就变成直接生成整个 after 结果，这样不违背了 Diff 的原则（最少操作）；
下图为例，能否只要生成 E 后将 A Tree 加入，再加 G 和 F 即可?
即便如此也是需要两个树嵌套遍历进行查询
before after
A E
/ \ / \
B D => A F
/ / \
C B D
/
C
/
G
以 A 为例，是否 A 需要遍历完整整个 after 1.在 after 中遇到 A，break 去执行 B 的遍历，可能出现遍历到 C 的时候，C-G 这样的情况，break 就无法清楚 G 节点； 2.只判断父子节点，难保 F 一边可能也出现 before；
所以当需要进行获取不同的节点时就需要 o(n**2)的时间复杂度；
获取差异后处理差异点是否 o(n2)+ o(n)或边找边处理直接 o(n2)?
还是以 A 为例：
- 在遍历 E 的时候，因为 A 的父节点为 Null，E 的也是 Null，并且 A!==E 所以直接生成；
- 遍历到 A 的时候，存在 Edit 的问题，需要清楚是删除或是插入等操作；
- 所以需要遍历 A 的下一层子节点，发现都是 B-D，所以 A 不用操作；
- 类推，当 before 的 C 在 after 中遍历到 C 的时候，同样需要看子节点，所以插入一个 G； 所以是 O(n**3);
简单点的理解就是时找到差异 o(n2)，然后寻找差异进行 edit 的是 o(n)，所以是 o(n3);
React 的 Diff
如果有100个元素，在一次改变后就需要1000000的计算量，这对于前端来说肯定爆炸，
但100个元素在前端来说也不是那么罕见，例如列表等；所以直接用传统的Diff来去处理意义不是特别大，
可能还不一定有直接重新渲染来的直接，需要在传统的Diff上进行改造；
在不看 React 官方的优化前，其实我们也在了解 Diff 的过程中也遇到和理解的优化点；
1. 在遍历查询差异节点时，只用一个作为基础 o(n)，上文说了会导致全部渲染，但实际这样的情况极少数发生；
A、因为 Dom 的处理很少跨层级去移动，大部分都是 appendChild、removeChild 或者改变 Child 的内容；
B、组件化，使得 Dom 更容易同级比对，不用考虑跨级；
2. 即是减少一层遍历，也只是从 o(n3)变成 o(n2)，所以还需要在操作节点的方面上处理，不用在遍历查找差异；
A、因为同级比对，所以不进行对最优操作进行遍历，只需要考虑是不是该节点有改变；
B、优化遍历过程中，部分并未进行改变的节点，可以不用再向下遍历；
目前来看已经有了不少改进，但是当父节点不变，子节点位置改变时，按上面说的会直接删除生成，也并不是好的处理方式；
before after
A A
/ \ / \
B C => C B
最终其实需要做成的就是直接移动位置即可，下面有说到解决方法；
所以我们再来看看，React 官方的假设基础：
- 两个不同类型的元素会产生出不同的树；
- 开发者可以通过 key prop 来暗示哪些子元素在不同的渲染下能保持稳定；
React 的策略
同层级对比(Tree Diff)
只对比前后树同层级的差异，直接新增或者删除；
before after
A D
/ \ /
B C => A
/ \
B C
after里面的元素全部都重新生成；
比对不同类型的元素(Component Diff)
如果节点为不同类型的元素时，直接进行删除然后重新创建新的元素，进而它的子节点即使和原先的子节点是一样也需要重新创建；
before after
<ConponentA /> => <ConponentB />
ConponentA 与ConponentB 的元素皆为 <div>test</div>，也是需要重新生成；
比对同一类型的元素(Element Diff)
before after
<ConponentA /> => <ConponentA />
在前后元素类型相同后，进行 ElementDiff 的对比；
1. 当节点为相同类型的元素时，如果只是改变属性子节点没有任何变化时，仅比对及更新有改变的属性；
<div className="before" title="stuff" /> => <div className="after" title="stuff" />
所以只需要修改 DOM 元素上的 className 属性
2. 当节点为相同类型的元素时，子节点有变化，如位置、数目等，则会进行插入、删除、移动等操作；
before after
<div> <div>
<span>1</span> <span>1</span>
<span>2</span> <span>2</span>
</div> <span>3</span>
</div>
在遍历完1和2的对比之后插入一个3即可；
key 的重要性
key 可以理解为身份标志，所以必须要保持唯一和稳定；
1. 防止错误的操作，减少性能消耗；
before after
<div> <div>
<span key="1">1</span> <span key="3">3</span>
<span key="2">2</span> <span key="1">1</span>
</div> <span key="2">2</span>
</div>
通过 key 可以发现1和2节点都是相同的节点，只需要移动插入3然后移动1、2即可；
避免之前文中说的的问题，删除重新而不是移动；
2. 减少Diff时间
React 是不会给组件增加 Key，但是增加 key 属性的节点，组件实例会基于它们的 key 来决定是否更新以及复用，
在 key 相等的时候会认为同一元素，不需要进行过多的 diff，只需要判断属性是否变化，而 key 不同则会销毁重新生成；
key 的注意点
//父组件
state = [{id: 1}]
<div>
<button onClick={setState([{id:2}, {id: 1})]} >在列表头插入元素</button>
{ state.map((value,inedx) => (<Item id={value.id} key={index} />)) }
</div>
//Item组件
<div>
<span>{props.id}</span>
<input type="text" />
</div>
在 <input id="1"> 输入 test 后，点击按钮插入元素时，会出现在 <input id="1"> 的 value(test) 出现在 <input id="2">
before after
<Item id="1" key="0" /> <Item id="2" key="0" />
<Item id="1" key="1" />
原因值因为 key，key 相等导致 id:1 和 id:2 当成相等，所以进行属性判断。
所以 before 的 <Item> 只修改了 props.id，而不是在前面插入一个 Item，只是1变成2，再加一个1。
如果 key 是数组下标，那么修改顺序时会修改当前的 key，导致非受控组件的 state（比如 input）可能相互篡改导致无法预期的变动。
所以在数组遍历的时候不建议用 index 当 key 使用
Diff 注意点
- 减少直接对原生 Dom 的操作，保证 Dom 结构的稳定；（Tree Diff）
- 常出现的元素，只做 Class 的隐藏显示，不直接影响 Dom 结构处理；(Tree Diff)
- 避免 Dom 节点过多，可以使用灵活使用、Css 等处理；(Tree Diff)
- 尽量处理好子元素相同的组件，实现同类型的扩展；（Component Diff）
- 处理好 key，确保稳定而且唯一；(Element Diff)
- 处理好 shouldComponentUpdate，减少被动 diff；（Element Diff）
- 处理好数组等大数据显示，如 1000 条时只显示能显示的数目既可以，不需要一次显示；(如 react-virtualized)；
- 减少列表元素中，元素移动过多；（Element Diff）
简单点总结就是简单（Dom，数据）、唯一(key，类型)、稳定(操作 dom，列表元素)；