关于virtual dom实现视图更新中的时间复杂度的问题

React通过virtual dom来实现高效的视图更新。基本原理是用纯js对象模拟dom树，每当更新时，根据组件们的render方法计算出新的虚拟dom树，并与此前的虚拟dom树作diff，得到一个patch（差异补丁），最后映射到真实dom树上完成视图更新。而两棵树的完全的 diff 算法是一个时间复杂度为 O(n^3) 的问题。但是在前端当中，很少出现跨越层级移动DOM元素的情况，所以React采用了简化的diff算法，只会对virtual dom中同一个层级的元素进行对比，这样算法复杂度就可以达到 O(n)。

样例分析

由于React采用的diff算法是对新旧虚拟dom树同层级的元素挨个比较，碰到循环输出的元素时会有一些问题，比如列表。先来看一个例子：

1
2
3
4
5
6
7
8
9
10
11
// 旧v-dom
<ul>
  <li>first</li>
  <li>second</li>
</ul>
// 新v-dom
<ul>
  <li>zero</li>
  <li>first</li>
  <li>second</li>
</ul>

React在diff两棵树时，发现原来的两个li元素都与新v-dom中对应位置上的两个li元素不同，就会对其修改，并向真实dom树中插入新的second节点。实际上，我们可能只是进行了在first之前插入新zero节点的操作，而现在进行了额外的修改操作。
React官方文档提示我们应该使用key属性来解决上述问题。key是一个字符串，用来唯一标识同父同层级的兄弟元素。当React作diff时，只要子元素有key属性，便会去原v-dom树中相应位置（当前横向比较的层级）寻找是否有同key元素，比较它们是否完全相同，若是则复用该元素，免去不必要的操作。
延续第一个例子，如果每个li元素都有key属性：

1
2
3
4
5
6
7
8
9
10
11
// 旧v-dom
<ul>
  <li key="1">first</li>
  <li key="2">second</li>
</ul>
// 新v-dom
<ul>
  <li key="0">zero</li>
  <li key="1">first</li>
  <li key="2">second</li>
</ul>

日常开发中

代码举例,key属性常与map结合在一起。

1
2
3
4
5
6
{
    constPhone && constPhone.completed && constPhone.data ?
    constPhone.data.map((item, index) => <option key={index} value={item.country_code}>
    +{item.country_code}
    </option>) : null
}

参考资料：React中key的必要性与使用