什么是 Diffing Algorithm（差异算法）？

What is diffing algorithm?

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: medium

分类: Virtual DOM, Reconciliation

标签: diffing algorithm, reconciliation, O(n) heuristic, key

参考答案摘要

答案 React 需要使用算法来找出如何高效地更新 UI，使其匹配最新的组件树。差异算法（diffing algorithm）会生成将一棵树转换为另一棵树所需的最少操作数。 不过，如果使用通用算法，其复杂度可能达到 O(n³) （n 为元素数量）。在这种情况下，渲染 1000 个元素需要约十亿次比较，成本过高。 因此，React 基于两个假设实现了一个启发式的 O(n) 算法： 不同类型的两个元素...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。