共计 4599 个字符，预计需要花费 12 分钟才能阅读完成。
前言
目前最流行的两大前端框架，React 和 Vue，都不约而同的借助 Virtual DOM 技术提高页面的渲染效率。那么，什么是 Virtual DOM？它是通过什么方式去提升页面渲染效率的呢？本系列文章会详细讲解 Virtual DOM 的创建过程，并实现一个简单的 Diff 算法来更新页面。本文的内容脱离于任何的前端框架，只讲最纯粹的 Virtual DOM。敲单词太累了，下文 Virtual DOM 一律用 VD 表示。
前三篇文章介绍了 VD 的基本概念，并讲解了如何利用 JSX 编译 HTML 标签，然后生成 VD，进而创建真实 dom，最后再利用 VD 更新页面的过程。以下是传送门：你不知道的 Virtual DOM（一）：Virtual Dom 介绍你不知道的 Virtual DOM（二）：Virtual Dom 的更新你不知道的 Virtual DOM（三）：Virtual Dom 更新优化
今天，我们继续在之前项目的基础上进行优化。用过 React 或者 Vue 的朋友都知道在渲染数组元素的时候，编译器会提醒加上 key 这个属性，那么 key 是用来做什么的呢？
key 的作用
在渲染数组元素时，它们一般都有相同的结构，只是内容有些不同而已，比如：
<ul>
<li>
<span> 商品：苹果 </span>
<span> 数量：1</span>
</li>
<li>
<span> 商品：香蕉 </span>
<span> 数量：2</span>
</li>
<li>
<span> 商品：雪梨 </span>
<span> 数量：3</span>
</li>
</ul>
可以把这个例子想象成一个购物车。此时如果想往购物车里面添加一件商品，性能不会有任何问题，因为只是简单的在 ul 的末尾追加元素，前面的元素都不需要更新：
<ul>
<li>
<span> 商品：苹果 </span>
<span> 数量：1</span>
</li>
<li>
<span> 商品：香蕉 </span>
<span> 数量：2</span>
</li>
<li>
<span> 商品：雪梨 </span>
<span> 数量：3</span>
</li>
<li>
<span> 商品：橙子 </span>
<span> 数量：2</span>
</li>
</ul>
但是，如果我要删除第一个元素，根据 VD 的比较逻辑，后面的元素全部都要进行更新的操作。dom 结构简单还好说，如果是一个复杂的结构，那页面渲染的性能将会受到很大的影响。
<ul>
<li>
<span> 商品：香蕉 </span>
<span> 数量：2</span>
</li>
<li>
<span> 商品：雪梨 </span>
<span> 数量：3</span>
</li>
<li>
<span> 商品：橙子 </span>
<span> 数量：2</span>
</li>
</ul>
有什么方式可以降低这种性能的损耗呢？
最直观的方法肯定是直接删除第一个元素然后其它元素保持不变了。但程序没有这么智能，可以像我们一样一眼就看出变化。程序能做到的是尽量少的修改元素，通过移动元素而不是修改元素来达到更新的目的。为了告诉程序要怎么移动元素，我们必须给每个元素加上一个唯一标识，也就是 key。
<ul>
<li key=”apple”>
<span> 商品：苹果 </span>
<span> 数量：1</span>
</li>
<li key=”banana”>
<span> 商品：香蕉 </span>
<span> 数量：2</span>
</li>
<li key=”pear”>
<span> 商品：雪梨 </span>
<span> 数量：3</span>
</li>
<li key=”orange”>
<span> 商品：橙子 </span>
<span> 数量：2</span>
</li>
</ul>
当把苹果删掉的时候，VD 里面第一个元素是香蕉，而 dom 里面第一个元素是苹果。当元素有 key 属性的时候，框架就会尝试根据这个 key 去找对应的元素，找到了就将这个元素移动到第一个位置，循环往复。最后 VD 里面没有第四个元素了，才会把苹果从 dom 移除。
代码实现
在上一个版本代码的基础上，主要的改动点是 diffChildren 这个函数。原来的实现很简单，递归的调用 diff 就可以了：
function diffChildren(newVDom, parent) {
// 获取子元素最大长度
const childLength = Math.max(parent.childNodes.length, newVDom.children.length);
// 遍历并 diff 子元素
for (let i = 0; i < childLength; i++) {
diff(newVDom.children[i], parent, i);
}
}
现在，我们要对这个函数进行一个大改造，让他支持 key 的查找：
function diffChildren(newVDom, parent) {
// 有 key 的子元素
const nodesWithKey = {};
let nodesWithKeyCount = 0;
// 没 key 的子元素
const nodesWithoutKey = [];
let nodesWithoutKeyCount = 0;
const childNodes = parent.childNodes,
nodeLength = childNodes.length;
const vChildren = newVDom.children,
vLength = vChildren.length;
// 用于优化没 key 子元素的数组遍历
let min = 0;
// 将子元素分成有 key 和没 key 两组
for (let i = 0; i < nodeLength; i++) {
const child = childNodes[i],
props = child[ATTR_KEY];
if (props !== undefined && props.key !== undefined) {
nodesWithKey[props.key] = child;
nodesWithKeyCount++;
} else {
nodesWithoutKey[nodesWithoutKeyCount++] = child;
}
}
// 遍历 vdom 的所有子元素
for (let i = 0; i < vLength; i++) {
const vChild = vChildren[i],
vProps = vChild.props;
let dom;
vKey = vProps!== undefined ? vProps.key : undefined;
// 根据 key 来查找对应元素
if (vKey !== undefined) {
if (nodesWithKeyCount && nodesWithKey[vKey] !== undefined) {
dom = nodesWithKey[vKey];
nodesWithKey[vKey] = undefined;
nodesWithKeyCount–;
}
}
// 如果没有 key 字段，则找一个类型相同的元素出来做比较
else if (min < nodesWithoutKeyCount) {
for (let j = 0; j < nodesWithoutKeyCount; j++) {
const node = nodesWithoutKey[j];
if (node !== undefined && isSameType(node, vChild)) {
dom = node;
nodesWithoutKey[j] = undefined;
if (j === min) min++;
if (j === nodesWithoutKeyCount – 1) nodesWithoutKeyCount–;
break;
}
}
}
// diff 返回是否更新元素
const isUpdate = diff(dom, vChild, parent);
// 如果是更新元素，且不是同一个 dom 元素，则移动到原先的 dom 元素之前
if (isUpdate) {
const originChild = childNodes[i];
if (originChild !== dom) {
parent.insertBefore(dom, originChild);
}
}
}
// 清理剩下的未使用的 dom 元素
if (nodesWithKeyCount) {
for (key in nodesWithKey) {
const node = nodesWithKey[key];
if (node !== undefined) {
node.parentNode.removeChild(node);
}
}
}
// 清理剩下的未使用的 dom 元素
while (min <= nodesWithoutKeyCount) {
const node = nodesWithoutKey[nodesWithoutKeyCount–];
if (node !== undefined) {
node.parentNode.removeChild(node);
}
}
}
代码比较长，主要是以下几个步骤：
将所有 dom 子元素分为有 key 和没 key 两组
遍历 VD 子元素，如果 VD 子元素有 key，则去查找有 key 的分组；如果没 key，则去没 key 的分组找一个类型相同的元素出来
diff 一下，得出是否更新元素的类型
如果是更新元素且子元素不是原来的，则移动元素
最后清理删除没用上的 dom 子元素
diff 也要改造一下，如果是新建、删除或者替换元素，返回 false。更新元素则返回 true：
function diff(dom, newVDom, parent) {
// 新建 node
if (dom == undefined) {
parent.appendChild(createElement(newVDom));
return false;
}
// 删除 node
if (newVDom == undefined) {
parent.removeChild(dom);
return false;
}
// 替换 node
if (!isSameType(dom, newVDom)) {
parent.replaceChild(createElement(newVDom), dom);
return false;
}
// 更新 node
if (dom.nodeType === Node.ELEMENT_NODE) {
// 比较 props 的变化
diffProps(newVDom, dom);
// 比较 children 的变化
diffChildren(newVDom, dom);
}
return true;
}
为了看效果，view 函数也要改造下：
const arr = [0, 1, 2, 3, 4];
function view() {
const elm = arr.pop();
// 用于测试能不能正常删除元素
if (state.num !== 9) arr.unshift(elm);
// 用于测试能不能正常添加元素
if (state.num === 12) arr.push(9);
return (
<div>
Hello World
<ul myText=”dickens”>
{
arr.map(i => (
<li id={i} class={`li-${i}`} key={i}>
第 {i}
</li>
))
}
</ul>
</div>
);
}
通过变换数组元素的顺序和适时的添加 / 删除元素，验证了代码按照我们的设计思路正确运行。
总结
本文基于上一个版本的代码，加入了对唯一标识（key）的支持，很好的提高了更新数组元素的效率。基于当前这个版本的代码还能做怎样的优化呢，敬请期待下一篇的内容。
P.S.: 想看完整代码见这里，如果有必要建一个仓库的话请留言给我：代码
