diff算法的作用
計(jì)算出Virtual DOM中真正變化的部分，并只針對(duì)該部分進(jìn)行原生DOM操作，而非重新渲染整個(gè)頁面。
傳統(tǒng)diff算法
通過循環(huán)遞歸對(duì)節(jié)點(diǎn)進(jìn)行依次對(duì)比，算法復(fù)雜度達(dá)到 O(n^3) ，n是樹的節(jié)點(diǎn)數(shù)，這個(gè)有多可怕呢？——如果要展示1000個(gè)節(jié)點(diǎn)，得執(zhí)行上億次比較。。即便是CPU快能執(zhí)行30億條命令，也 很難在一秒內(nèi) 計(jì)算出差異。
react的diff算法
diff算法是調(diào)和的具體實(shí)現(xiàn)。
調(diào)和：將Virtual DOM樹轉(zhuǎn)換成actual DOM樹的最少操作的過程 稱為 調(diào)和 。
diff策略
React用 三大策略 將O(n^3)復(fù)雜度 轉(zhuǎn)化為 O(n)復(fù)雜度
策略一（ tree diff ）：
Web UI中DOM節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作特別少，可以忽略不計(jì)。
策略二（ component diff ）：
擁有相同類的兩個(gè)組件 生成相似的樹形結(jié)構(gòu)，
擁有不同類的兩個(gè)組件 生成不同的樹形結(jié)構(gòu)。
策略三（ element diff ）：
對(duì)于同一層級(jí)的一組子節(jié)點(diǎn)，通過唯一id區(qū)分。
tree diff算法
（1）React通過updateDepth對(duì)Virtual DOM樹進(jìn)行 層級(jí)控制 。
（2）對(duì)樹分層比較，兩棵樹 只對(duì) 同一層次節(jié)點(diǎn) 進(jìn)行比較。如果該節(jié)點(diǎn)不存在時(shí)，則該節(jié)點(diǎn)及其子節(jié)點(diǎn)會(huì)被完全刪除，不會(huì)再進(jìn)一步比較。
（3）只需遍歷一次，就能完成整棵DOM樹的比較。
對(duì)于策略一，React 對(duì)樹進(jìn)行了分層比較，兩棵樹只會(huì)對(duì)同一層次的節(jié)點(diǎn)進(jìn)行比較。
只會(huì)對(duì)相同層級(jí)的 DOM 節(jié)點(diǎn)進(jìn)行比較，當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)不存在時(shí)，則該節(jié)點(diǎn)及其子節(jié)點(diǎn)會(huì)被完全刪除，不會(huì)用于進(jìn)一步的比較。
如果出現(xiàn)了 DOM 節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作。
如上圖這樣，A節(jié)點(diǎn)就會(huì)被直接銷毀了。
Diif 的執(zhí)行情況是：create A -> create C -> create D -> delete A
component diff
React對(duì)不同的組件間的比較，有三種策略
（1）同一類型的兩個(gè)組件，按原策略（層級(jí)比較）繼續(xù)比較Virtual DOM樹即可。
（2）同一類型的兩個(gè)組件，組件A變化為組件B時(shí)，可能Virtual DOM沒有任何變化，如果知道這點(diǎn)（變換的過程中，Virtual DOM沒有改變），可節(jié)省大量計(jì)算時(shí)間，所以 用戶 可以通過 shouldComponentUpdate() 來判斷是否需要 判斷計(jì)算。
（3）不同類型的組件，將一個(gè)（將被改變的）組件判斷為dirty component（臟組件），從而 替換 整個(gè)組件的所有節(jié)點(diǎn) 。
注意：如果組件D和組件G的結(jié)構(gòu)相似，但是 React判斷是 不同類型的組件，則不會(huì)比較其結(jié)構(gòu)，而是刪除 組件D及其子節(jié)點(diǎn)，創(chuàng)建組件G及其子節(jié)點(diǎn)。
element diff
當(dāng)節(jié)點(diǎn)處于同一層級(jí)時(shí)，diff提供三種節(jié)點(diǎn)操作： 刪除、插入、移動(dòng) 。
插入：組件 C 不在集合（A,B）中，需要插入
刪除：（1）組件 D 在集合（A,B,D）中，但 D的節(jié)點(diǎn)已經(jīng)更改，不能復(fù)用和更新，所以需要 刪除 舊的 D ，再創(chuàng)建新的。
（2）組件 D 之前在 集合（A,B,D）中，但集合變成新的集合（A,B）了，D 就需要被刪除。
移動(dòng)：組件D已經(jīng)在集合（A,B,C,D）里了，且集合更新時(shí)，D沒有發(fā)生更新，只是位置改變，如新集合（A,D,B,C），D在第二個(gè)，無須像傳統(tǒng)diff，讓舊集合的第二個(gè)B和新集合的第二個(gè)D 比較，并且刪除第二個(gè)位置的B，再在第二個(gè)位置插入D，而是 （對(duì)同一層級(jí)的同組子節(jié)點(diǎn)） 添加唯一key進(jìn)行區(qū)分，移動(dòng)即可。
element diff
當(dāng)節(jié)點(diǎn)處于同一層級(jí)時(shí)，diff提供三種節(jié)點(diǎn)操作： 刪除、插入、移動(dòng) 。
插入：組件 C 不在集合（A,B）中，需要插入
刪除：（1）組件 D 在集合（A,B,D）中，但 D的節(jié)點(diǎn)已經(jīng)更改，不能復(fù)用和更新，所以需要 刪除 舊的 D ，再創(chuàng)建新的。
（2）組件 D 之前在 集合（A,B,D）中，但集合變成新的集合（A,B）了，D 就需要被刪除。
移動(dòng)：組件D已經(jīng)在集合（A,B,C,D）里了，且集合更新時(shí)，D沒有發(fā)生更新，只是位置改變，如新集合（A,D,B,C），D在第二個(gè)，無須像傳統(tǒng)diff，讓舊集合的第二個(gè)B和新集合的第二個(gè)D 比較，并且刪除第二個(gè)位置的B，再在第二個(gè)位置插入D，而是 （對(duì)同一層級(jí)的同組子節(jié)點(diǎn)） 添加唯一key進(jìn)行區(qū)分，移動(dòng)即可。
移動(dòng)的條件：
- 對(duì)新集合中的節(jié)點(diǎn)進(jìn)行循環(huán)遍歷，新舊集合中是否存在相同節(jié)點(diǎn)
- nextIndex: 新集合中當(dāng)前節(jié)點(diǎn)的位置
- lastIndex: 訪問過的節(jié)點(diǎn)在舊集合中最右的位置（最大位置）
- If (child._mountIndex < lastIndex)
情形一：新舊集合中存在相同節(jié)點(diǎn)但位置不同時(shí)，如何移動(dòng)節(jié)點(diǎn)
（1）看著上圖的 B，React先從新中取得B，然后判斷舊中是否存在相同節(jié)點(diǎn)B，當(dāng)發(fā)現(xiàn)存在節(jié)點(diǎn)B后，就去判斷是否移動(dòng)B。
B在舊 中的index=1，它的lastIndex=0， 不滿足 index < lastIndex 的條件，因此 B 不做移動(dòng)操作。此時(shí)，一個(gè)操作是，lastIndex=(index,lastIndex)中的較大數(shù)=1.
注意：lastIndex有點(diǎn)像浮標(biāo)，或者說是一個(gè)map的索引，一開始默認(rèn)值是0，它會(huì)與map中的元素進(jìn)行比較，比較完后，會(huì)改變自己的值的（取index和lastIndex的較大數(shù)）。
（2）看著 A，A在舊的index=0，此時(shí)的lastIndex=1（因?yàn)橄惹芭c新的B比較過了）， 滿足index<lastIndex ，因此，對(duì)A進(jìn)行移動(dòng)操作，此時(shí) lastIndex=max(index,lastIndex)=1。
（3）看著D，同（1），不移動(dòng)，由于D在舊的index=3，比較時(shí)，lastIndex=1，所以改變lastIndex=max(index,lastIndex)=3
（4）看著C，同（2），移動(dòng)，C在舊的index=2，滿足index<lastIndex（lastIndex=3），所以移動(dòng)。
由于C已經(jīng)是最后一個(gè)節(jié)點(diǎn)，所以diff操作結(jié)束。
情形二：新集合中有新加入的節(jié)點(diǎn)，舊集合中有刪除的節(jié)點(diǎn)
（1）B不移動(dòng)，不贅述，更新l astIndex=1
（2）新集合取得 E，發(fā)現(xiàn)舊不存在，故 在lastIndex=1的位置 創(chuàng)建E ，更新lastIndex=1
（3）新集合取得C，C不移動(dòng)，更新lastIndex=2
（4）新集合取得A，A移動(dòng)，同上，更新lastIndex=2
（5） 新集合對(duì)比后，再對(duì)舊集合遍歷。判斷 新集合 沒有，但 舊集合 有的元素（如D，新集合沒有，舊集合有） ，發(fā)現(xiàn) D，刪除D，diff操作結(jié)束。
diff的不足與待優(yōu)化的地方
看圖的 D，此時(shí)D不移動(dòng)，但它的index是最大的，導(dǎo)致更新lastIndex=3，從而使得其他元素A,B,C的index<lastIndex，導(dǎo)致A,B,C都要去移動(dòng)。
理想情況是只移動(dòng)D，不移動(dòng)A,B,C。因此，在開發(fā)過程中，盡量減少類似將最后一個(gè)節(jié)點(diǎn)移動(dòng)到列表首部的操作，當(dāng)節(jié)點(diǎn)數(shù)量過大或更新操作過于頻繁時(shí)，會(huì)影響React的渲染性能。
