谈谈你对diff算法的理解（diffing算法）

一、基础

Diff算法实现的是最小量更新虚拟DOM。这句话虽然简短，但是涉及到了两个核心要素：虚拟DOM、最小量更新。

1.虚拟DOM

虚拟DOM指的就是将真实的DOM树构造为js对象的形式，从而解决浏览器操作真实DOM的性能问题。

例如：如下DOM与虚拟DOM之间的映射关系

2.最小量更新

Diff的用途就是在新老虚拟DOM之间找到最小更新的部分，从而将该部分对应的DOM进行更新。

二、整个流程

Diff算法真的很美，整个流程如下图所示：

1. 首先比较一下新旧节点是不是同一个节点(可通过比较sel(选择器)和key(唯一标识)值是不是相同)，不是同一个节点则进行暴力删除(注：先以旧节点为基准插入新节点，然后再删除旧节点)。
2. 若是同一个节点则需要进一步比较

完全相同，不做处理

新节点内容为文本，直接替换完事

新节点有子节点，这个时候就要仔细考虑一下了:若老节点没有子元素，则直接清空老节点，将新节点的子元素插入即可;若老节点有子元素则就需要按照上述的更新策略老搞定了(记住更新策略，又可以吹好几年了，666666)。

三、实战

光说不练假把式，下面直接输出diff算法的核心内容。

3.1 patch函数

Diff算法的入口函数，主要判断新旧节点是不是同一个节点，然后交由不同的逻辑进行处理。

1. exportdefaultfunctionpatch(oldVnode,newVnode){
2. //判断传入的第一个参数，是DOM节点还是虚拟节点
3. if(oldVnode.sel===''||oldVnode.sel===undefined){
4. //传入的第一个参数是DOM节点，此时要包装成虚拟节点
5. oldVnode=vnode(oldVnode.tagName.toLowerCase(),{},[],undefined,oldVnode);
6. }
8. //判断oldVnode和newVnode是不是同一个节点
9. if(oldVnode.key===newVnode.key&&oldVnode.sel===newVnode.sel){
10. //是同一个节点，则进行精细化比较
11. patchVnode(oldVnode,newVnode);
12. }
13. else{
14. //不是同一个节点，暴力插入新的，删除旧的
15. letnewVnodeElm=createElement(newVnode);
17. //将新节点插入到老节点之前
18. if(oldVnode.elm.parentNode&&newVnodeElm){
19. oldVnode.elm.parentNode.insertBefore(newVnodeElm,oldVnode.elm);
20. }
21. //删除老节点
22. oldVnode.elm.parentNode.removeChild(oldVnode.elm);
23. }
24. }

3.2 patchVnode函数

该函数主要负责精细化比较，通过按照上述流程图中的逻辑依次判断属于哪一个分支，从而采取不同的处理逻辑。(思路清晰，算法太牛了)

1. exportdefaultfunctionpatchVnode(oldVnode,newVnode){
2. //判断新旧vnode是否是同一个对象
3. if(oldVnode===newVnode){
4. return;
5. }
6. //判断vnode有没有text属性
7. if(newVnode.text!==undefined&&(newVnode.children===undefined||newVnode.children.length===0)){
8. console.log('新vnode有text属性');
9. if(newVnode.text!==oldVnode.text){
10. oldVnode.elm.innerText=newVnode.text;
11. }
12. }
13. else{
14. //新vnode没有text属性，有children
15. console.log('新vnode没有text属性');
16. //判断老的有没有children
17. if(oldVnode.children!==undefined&&oldVnode.children.length>0){
18. //老的有children，新的也有children
19. updateChildren(oldVnode.elm,oldVnode.children,newVnode.children);
20. }
21. else{
22. //老的没有children，新的有children
23. //清空老的节点的内容
24. oldVnode.elm.innerHTML='';
25. //遍历新的vnode的子节点，创建DOM，上树
26. for(leti=0;i<newVnode.children.length;i++){
27. letdom=createElement(newVnode.children[i]);
28. oldVnode.elm.appendChild(dom);
29. }
30. }
31. }
32. }

3.3 updateChildren函数

核心函数，主要负责旧虚拟节点和新虚拟节点均存在子元素的情况，按照比较策略依次进行比较，最终找出子元素中变化的部分，实现最小更新。对于该部分，涉及到一些指针，如下所示：

1. 旧前指的就是更新前虚拟DOM中的头部指针
2. 旧后指的就是更新前虚拟DOM中的尾部指针
3. 新前指的就是更新后虚拟DOM中的头部指针
4. 新后指的就是更新后虚拟DOM中的尾部指针

按照上述的更新策略，上述旧虚拟DOM更新为新虚拟DOM的流程为：

1. 命中“新后旧前”策略，然后将信后对应的DOM节点(也就是节点1)移动到旧后节点(节点3)后面，然后旧前节点指针下移，新后节点指针上移。
2. 仍然命中“新后旧前”策略，做相同的操作，将节点2移动到旧后节点(节点3)后面，下移旧前节点，上移新后节点。
3. 命中“新前旧前”策略，DOM节点不变，旧前和新前节点均下移。
4. 跳出循环，移动结束。

1. exportdefaultfunctionupdateChildren(parentElm,oldCh,newCh){
2. //旧前
3. letoldStartIdx=0;
4. //新前
5. letnewStartIdx=0;
6. //旧后
7. letoldEndIdx=oldCh.length-1;
8. //新后
9. letnewEndIdx=newCh.length-1;
10. //旧前节点
11. letoldStartVnode=oldCh[0];
12. //旧后节点
13. letoldEndVnode=oldCh[oldEndIdx];
14. //新前节点
15. letnewStartVnode=newCh[0];
16. //新后节点
17. letnewEndVnode=newCh[newEndIdx];
19. letkeyMap=null;
21. while(oldStartIdx<=oldEndIdx&&newStartIdx<=newEndIdx){
22. //略过已经加undefined标记的内容
23. if(oldStartVnode==null||oldCh[oldStartIdx]===undefined){
24. oldStartVnode=oldCh[++oldStartIdx];
25. }
26. elseif(oldEndVnode==null||oldCh[oldEndIdx]===undefined){
27. oldEndVnode=oldCh[--oldEndIdx];
28. }
29. elseif(newStartVnode==null||newCh[newStartIdx]===undefined){
30. newStartVnode=newCh[++newStartIdx];
31. }
32. elseif(newEndVnode==null||newCh[newEndIdx]===undefined){
33. newEndVnode=newCh[--newEndIdx];
34. }
35. elseif(checkSameVnode(oldStartVnode,newStartVnode)){
36. //新前与旧前
37. console.log('新前与旧前命中');
38. patchVnode(oldStartVnode,newStartVnode);
39. oldStartVnode=oldCh[++oldStartIdx];
40. newStartVnode=newCh[++newStartIdx];
41. }
42. elseif(checkSameVnode(oldEndVnode,newEndVnode)){
43. //新后和旧后
44. console.log('新后和旧后命中');
45. patchVnode(oldEndVnode,newEndVnode);
46. oldEndVnode=oldCh[--oldEndIdx];
47. newEndVnode=newCh[--newEndVnode];
48. }
49. elseif(checkSameVnode(oldStartVnode,newEndVnode)){
50. console.log('新后和旧前命中');
51. patchVnode(oldStartVnode,newEndVnode);
52. //当新后与旧前命中的时候，此时要移动节点，移动新后指向的这个节点到老节点旧后的后面
53. parentElm.insertBefore(oldStartVnode.elm,oldEndVnode.elm.nextSibling);
54. oldStartVnode=oldCh[++oldStartIdx];
55. newEndVnode=newCh[--newEndIdx];
56. }
57. elseif(checkSameVnode(oldEndVnode,newStartVnode)){
58. //新前和旧后
59. console.log('新前和旧后命中');
60. patchVnode(oldEndVnode,newStartVnode);
61. //当新前和旧后命中的时候，此时要移动节点，移动新前指向的这个节点到老节点旧前的前面
62. parentElm.insertBefore(oldEndVnode.elm,oldStartVnode.elm);
63. oldEndVnode=oldCh[--oldEndIdx];
64. newStartVnode=newCh[++newStartIdx];
65. }
66. else{
67. //四种都没有命中
68. //制作keyMap一个映射对象，这样就不用每次都遍历老对象了
69. if(!keyMap){
70. keyMap={};
71. for(leti=oldStartIdx;i<=oldEndIdx;i++){
72. constkey=oldCh[i].key;
73. if(key!==undefined){
74. keyMap[key]=i;
75. }
76. }
77. }
78. //寻找当前这项（newStartIdx）在keyMap中的映射的位置序号
79. constidxInOld=keyMap[newStartVnode.key];
80. if(idxInOld===undefined){
81. //如果idxInOld是undefined表示踏实全新的项，此时会将该项创建为DOM节点并插入到旧前之前
82. parentElm.insertBefore(createElement(newStartVnode),oldStartVnode.elm);
83. }
84. else{
85. //如果不是undefined，则不是全新的项，则需要移动
86. constelmToMove=oldCh[idxInOld];
87. patchVnode(elmToMove,newStartVnode);
88. //把这项设置为undefined，表示已经处理完这项了
89. oldCh[idxInOld]=undefined;
90. //移动
91. parentElm.insertBefore(elmToMove.elm,oldStartVnode.elm);
92. }
93. //指针下移，只移动新的头
94. newStartVnode=newCh[++newStartIdx];
95. }
96. }
98. //循环结束后，处理未处理的项
99. if(newStartIdx<=newEndIdx){
100. console.log('new还有剩余节点没有处理，要加项，把所有剩余的节点插入到oldStartIdx之前');
101. //遍历新的newCh，添加到老的没有处理的之前
102. for(leti=newStartIdx;i<=newEndIdx;i++){
103. //insertBefore方法可以自动识别null，如果是null就会自动排到队尾去
104. //newCh[i]现在还没有真正的DOM，所以要调用createElement函数变为DOM
105. parentElm.insertBefore(createElement(newCh[i]),oldCh[oldStartIdx].elm);
106. }
107. }
108. elseif(oldStartIdx<=oldEndIdx){
109. console.log('old还有剩余节点没有处理，要删除项');
110. //批量删除oldStart和oldEnd指针之间的项
111. for(leti=oldStartIdx;i<=oldEndIdx;i++){
112. if(oldCh[i]){
113. parentElm.removeChild(oldCh[i].elm);
114. }
115. }
116. }
117. }

原文链接：https://mp.weixin.qq.com/s/RKbOTFAJJ7VEpAJdUI3iTA

如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）

您的姓名 *

身份证号码 *

手机号码 *

选择地区 *

详细地址 *

留言备注 *