diffing算法是React实现增量渲染的关键。当state或props更新时，render()函数被调用来渲染新的组件。React需要一种方法来高效地渲染，即尽可能复用组件，而不是推倒重来。

树上编辑距离算法（太复杂了看不懂）提供了一种在O(n³)复杂度(n是树上元素个数)内得到所需的最少状态转移数的方法。而这一复杂度对于React的实时性要求是不可接受的。

React基于两个简化实现了O(n)的diffing算法：

1.两棵树的根标签不同，则两棵树不同（即使子节点都相同）；

2.可以通过手动指定key属性来标识不同的节点。

diffing算法的关键在于使用虚拟节点(Vnode)，尽量不创建真实节点；并使用新旧头尾四个指针来进行双向匹配，非常酷

以下是diffing算法的（极简版）实现与测试样例。

  1 export function patch(oldVnode, newVnode) {
  2     if (newVnode.text && newVnode.children && newVnode.children.length) {
  3         throw new Error('text and children cannot both exist')
  4     }
  5     if (!oldVnode.sel) { //old node is a DOM,wrap it
  6         oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode)
  7     }
  8     if (isSame(oldVnode, newVnode)) {
  9         patchVnode(oldVnode, newVnode)
 10     } else {
 11         //replace the old node with new one
 12         let newDOM = createElement(newVnode);
 13         if (oldVnode.elm) {
 14             oldVnode.elm.parentNode.insertBefore(newDOM, oldVnode.elm)
 15         }
 16         oldVnode.elm.parentNode.removeChild(oldVnode.elm)
 17     }
 18 }
 19 
 20 function patchVnode(oldVnode, newVnode) {
 21     if (oldVnode === newVnode) {
 22         return
 23     }
 24     newVnode.elm = oldVnode.elm
 25     if (newVnode.text) {
 26         if (newVnode.text !== oldVnode.text) {
 27             oldVnode.elm.innerText = newVnode.text
 28         }
 29     } else {
 30         if (oldVnode.text) {
 31             oldVnode.elm.innerText = null
 32             for (let child of newVnode.children) {
 33                 oldVnode.elm.appendChild(createElement(child))
 34             }
 35         } else {
 36             //both old and new nodes has children,do the diffing!
 37             diff(oldVnode.elm, oldVnode.children, newVnode.children)
 38         }
 39     }
 40 }
 41 
 42 // the main diffing algorithm
 43 function diff(parent, olds, news) {
 44     //use four pointers
 45     let new1 = 0
 46     let old1 = 0
 47     let new2 = news.length - 1
 48     let old2 = olds.length - 1
 49     let old1Vnode = olds[new1]
 50     let old2Vnode = olds[old2]
 51     let new1Vnode = news[old1]
 52     let new2Vnode = news[new2]
 53     let oldKeyMap = {}
 54     while (new1 <= new2 && old1 <= old2) {
 55         //skip all undefined
 56         if (!old1Vnode) old1Vnode = olds[++old1]
 57         else if (!old2Vnode) old2Vnode = olds[--old2]
 58         else if (!new1Vnode) new1Vnode = news[++new1]
 59         else if (!new2Vnode) new2Vnode = news[--new2]
 60         //four shortcuts
 61         else if (isSame(old1Vnode, new1Vnode)) {
 62             patchVnode(old1Vnode, new1Vnode)
 63             old1Vnode = olds[++old1]
 64             new1Vnode = news[++new1]
 65         } else if (isSame(old2Vnode, new2Vnode)) {
 66             patchVnode(old2Vnode, new2Vnode)
 67             old2Vnode = olds[--old2]
 68             new2Vnode = news[--new2]
 69         } else if (isSame(old1Vnode, new2Vnode)) {
 70             patchVnode(old1Vnode, new2Vnode)
 71             parent.insertBefore(old1Vnode.elm, old2Vnode.elm.nextSibling)
 72             old1Vnode = olds[++old1]
 73             new2Vnode = news[--new2]
 74         } else if (isSame(old2Vnode, new1Vnode)) {
 75             patchVnode(old2Vnode, new1Vnode)
 76             parent.insertBefore(old2Vnode.elm, old1Vnode.elm)
 77             old2Vnode = olds[--old2]
 78             new1Vnode = news[++new1]
 79         } else {
 80             //use a map to record key to OldIdx
 81             //if all shortcuts failed, use the map to locate the next Vnode(new1Vnode)
 82             for (let i = old1; i <= old2; i++) {
 83                 let k = olds[i]?.key
 84                 if (k) {
 85                     oldKeyMap[k] = i
 86                 }
 87             }
 88             let idxInOld = oldKeyMap[new1Vnode.key]
 89             if (idxInOld) {
 90                 //an existing node. move it to the right place
 91                 let toRemoved = olds[idxInOld]
 92                 if (toRemoved.sel !== new1Vnode.sel) {
 93                     parent.insertBefore(createElement(new1Vnode), old1Vnode.elm)
 94                 } else {
 95                     patchVnode(toRemoved, new1Vnode)
 96                     olds[idxInOld] = undefined
 97                     parent.insertBefore(toRemoved.elm, old1Vnode.elm)
 98                 }
 99             } else {
100                 //a brand-new node
101                 parent.insertBefore(createElement(new1Vnode), old1Vnode.elm)
102             }
103             new1Vnode = news[++new1]
104         }
105     }
106     if (new1 <= new2) {
107         let before = news[new2 + 1] ? news[new2 + 1].elm : null
108         for (let i = new1; i <= new2; i++) {
109             parent.insertBefore(createElement(news[i]), before)
110         }
111     }
112     if (old1 <= old2) {
113         for (let i = old1; i <= old2; i++) {
114             if (olds[i]) {
115                 parent.removeChild(olds[i].elm)
116             }
117         }
118     }
119 }
120 
121 // convert virtualDOM to DOM recursively
122 function createElement(vnode) {
123     let dom = document.createElement(vnode.sel);
124     //if is textNode
125     if (vnode.text && !(vnode.children && vnode.children.length)) {
126         dom.innerText = vnode.text
127     } else if (Array.isArray(vnode.children) && vnode.children.length) {
128         for (let ch of vnode.children) {
129             let childDOM = createElement(ch);
130             dom.appendChild(childDOM)
131         }
132     }
133     vnode.elm = dom
134     return dom
135 }
136 
137 export function h(sel, data, children) {
138     if (arguments.length !== 3) {
139         throw new Error('#arg error')
140     }
141     if (isPrimitive(children)) {
142         return vnode(sel, data, undefined, children.toString(), undefined)
143     } else if (Array.isArray(children)) {
144         let c = []
145         for (let i = 0; i < children.length; i++) {
146             if (isPrimitive(children[i])) {
147                 children[i] = vnode(undefined, undefined, undefined, children[i], undefined)
148             }
149             c.push(children[i])
150         }
151         return vnode(sel, data, c, undefined, undefined)
152     } else if (typeof children === 'object' && children.sel) {
153         return vnode(sel, data, [children], undefined, undefined)
154     }
155     throw new Error('unexpected args')
156 }
157 
158 function isPrimitive(obj) {
159     return typeof obj === 'string' ||
160         typeof obj === 'number' ||
161         obj instanceof String ||
162         obj instanceof Number
163 }
164 
165 function vnode(sel, data, children, text, elm) {
166     let key = data?.key
167     return {sel, data, children, text, elm, key}
168 }
169 
170 function isSame(oldVnode, newVnode) {
171     return oldVnode.sel === newVnode.sel && oldVnode.key === newVnode.key
172 }

测试（欢迎捉虫）：

 1 let container = document.querySelector('#container');
 2 let vnode = h('ul',{},[
 3     h('li',{key:'A'},'A'),
 4     h('li',{key:'B'},'B'),
 5     h('li',{key:'C'},'C'),
 6     h('li',{key:'D'},'D'),
 7     h('li',{key:'E'},'E'),
 8 ])
 9 
10 patch(container,vnode)
11 
12 let vnode2 = h('ul',{},[
13     h('li',{key:'D'},'D'),
14     h('li',{key:'E'},'E'),
15     h('li',{key:'G'},'G'),
16     h('span',{key:'F'},'F'),
17     h('li',{key:'A'},'A'),
18     h('span',{key:'C'},'C'),
19 
20 ])
21 patch(vnode,vnode2)
22 
23 let vnode3 = h('ul',{},[
24     h('li',{},'啦啦啦'),
25     h('li',{},[
26         h('div',{},'div11'),
27         h('div',{},'div222')
28     ])
29 ])
30 patch(vnode2,vnode3)