22剖析前端中的数据结构应用场景

上一讲我们使用 JavaScript 实现了几种常见的数据结构。事实上，前端领域到处体现着数据结构的应用，尤其随着需求的复杂度上升，前端工程师越来越离不开数据结构。React、Vue 这些设计精巧的框架，在线文档编辑系统、大型管理系统，甚至一个简单的检索需求，都离不开数据结构的支持。是否能够掌握这个难点内容，将是进阶的重要考量。

这一讲，我们就来解析数据结构在前端中的应用场景，以此来帮助大家加深理解，做到灵活应用。

堆栈和队列的应用

关于栈和队列的实际应用比比皆是：

浏览器的历史记录，因为回退总是回退“上一个”最近的页面，它需要遵循栈的原则；

类似浏览器的历史记录，任何 Undo/Redo 都是一个栈的实现；

在代码中，广泛应用的递归产生的调用栈，同样也是栈思想的体现，想想我们常说的“栈溢出”就是这个道理；

同上，浏览器在抛出异常时，常规都会抛出调用栈信息；

在计算机科学领域应用广泛，如进制转换、括号匹配、栈混洗、表达式求值等；

队列的应用更为直观，我们常说的宏任务/微任务都是队列，不管是什么类型的任务，都是先进先执行；

后端也应用广泛，如消息队列、RabbitMQ、ActiveMQ 等，能起到延迟缓冲的功效。

另外，与性能话题相关，HTTP 1.1 有一个队头阻塞的问题，而原因就在于队列这样的数据结构的特点。具体来说，在 HTTP 1.1 中，每一个链接都默认是长链接，因此对于同一个 TCP 链接，HTTP 1.1 规定：服务端的响应返回顺序需要遵循其接收到相应的顺序。但这样存在一个问题：如果第一个请求处理需要较长时间，响应较慢，将会“拖累”其他后续请求的响应，这是一种队头阻塞。

HTTP 2 采用了二进制分帧和多路复用等方法，同域名下的通信都在同一个连接上完成，在这个连接上可以并行请求和响应，而互不干扰。

在框架层面，堆栈和队列的应用更是比比皆是。比如 React 的 Context 特性，参考以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


import React from "react";
const ContextValue = React.createContext();
export default function App() {
  return (
    <ContextValue.Provider value={1}>
      <ContextValue.Consumer>
        {(value1) => (
          <ContextValue.Provider value={2}>
            <ContextValue.Consumer>
              {(value2) => (
                <span>
                  {value1}-{value2}
                </span>
              )}
            </ContextValue.Consumer>
          </ContextValue.Provider>
        )}
      </ContextValue.Consumer>
    </ContextValue.Provider>
  );
}

对于以上代码，React 内部就是通过一个栈结构，在构造 Fiber 树时的 beginWork 阶段，将 Context.Provider 数据状态入栈（此时 value1：1 和 value2：2 分别入栈），在 completeWork 阶段，将栈中的数据状态出栈，以供给 Context.Consumer 消费。关于 React 源码中，栈的实现，你可以参考这部分源码。

链表的应用

React 的核心算法Fiber 的实现就是链表。React 最早开始使用大名鼎鼎的 Stack Reconciler 调度算法，Stack Reconciler 调度算法最大的问题在于：它就像函数调用栈一样，递归地、自顶向下进行 diff 和 render 相关操作，在 Stack Reconciler 执行的过程中，该调度算法始终会占据浏览器主线程。也就是说在此期间，用户的交互所触发的布局行为、动画执行任务都不会得到立即响应，从而影响用户体验。

因此 React Fiber 将渲染和更新过程进行了拆解，简单来说，就是每次检查虚拟 DOM 的一小部分，在检查间隙会检查“是否还有时间继续执行下一个虚拟 DOM 树上某个分支任务”，同时观察是否有更优先的任务需要响应。如果“没有时间执行下一个虚拟 DOM 树上某个分支任务”，且某项任务有更高优先级，React 就会让出主线程，直到主线程“不忙”的时候继续执行任务。

React Fiber 的实现也很简单，它将 Stack Reconciler 过程分成块，一次执行一块，执行完一块需要将结果保存起来，根据是否还有空闲的响应时间（requestIdleCallback）来决定下一步策略。当所有的块都已经执行完，就进入提交阶段，这个阶段需要更新 DOM，它是一口气完成的。

以上是比较主观的介绍，下面我们来看更具体的实现。

为了达到“随意中断调用栈并手动操作调用栈”，React Fiber 专门用于 React 组件堆栈调用的重新实现，也就是说一个 Fiber 就是一个虚拟堆栈帧，一个 Fiber 的结构类似：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


function FiberNode(
  tag: WorkTag,
  pendingProps: mixed,
  key: null | string,
  mode: TypeOfMode,
) {
  // Instance
  // ...
  this.tag = tag;                       
  // Fiber
  this.return = null;
  this.child = null;
  this.sibling = null;
  this.index = 0;
  this.ref = null;
  this.pendingProps = pendingProps;
  this.memoizedProps = null;
  this.updateQueue = null;
  this.memoizedState = null;
  this.dependencies = null;
  // Effects
  // ...
  this.alternate = null; 
}

这么看Fiber 就是一个对象，通过 parent、children、sibling 维护一个树形关系，同时 parent、children、sibling 也都是一个 Fiber 结构，FiberNode.alternate 这个属性来存储上一次渲染过的结果，事实上整个 Fiber 模式就是一个链表。React 也借此，从依赖于内置堆栈的同步递归模型，变为具有链表和指针的异步模型了。

具体的渲染过程：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


 function renderNode(node) {
   // 判断是否需要渲染该节点，如果 props 发生变化，则调用 render
   if (node.memoizedProps !== node.pendingProps) {
      render(node)
   }
   // 是否有子节点，进行子节点渲染
   if (node.child !== null) {
      return node.child
   // 是否有兄弟节点，进行兄弟点渲染
   } else if (node.sibling !== null){
      return node.sibling
   // 没有子节点和兄弟节点
   } else if (node.return !== null){
      return node.return
   } else {
      return null
   }
}
function workloop(root) {
   nextNode = root
   while (nextNode !== null && (no other high priority task)) {
      nextNode = renderNode(nextNode)
   }
}

注意在 Workloop 当中，while 条件 nextNode !== null && (no other high priority task) ，这是描述 Fiber 工作原理的关键伪代码。

下面我们换个角度再次说明。

在 Fiber 之前，React 递归遍历虚拟 DOM，在遍历过程中找到前后两颗虚拟 DOM 的差异，并生成一个 Mutation。这种递归遍历有一个局限性：每次递归都会在栈中添加一个同步帧，因此无法将遍历过程拆分为粒度更小的工作单元，也就无法暂停组件的更新，并在未来的某段时间恢复更新。

如何不通过递归的形式去遍历呢？基于链表的 Fiber 模型应运而生。最早的原始模型你可以在 2016 年的 issue 中找到。另外，React 中的 Hooks，也是通过链表这个数据结构实现的。

树的应用

从应用上来看，我们前端开发离不开的 DOM 就是一个树状结构；同理，不管是 React 还是 Vue 的虚拟 DOM 也都是树。

上文中我们提到了 React Element 树和 Fiber 树，React Element 树其实就是各级组件渲染，调用 React.createElement 返回 React Element 之后（每一个 React 组件，不管是 class 组件或 functional 组件，调用一次 render 或执行一次 function，就会生成 React Element 节点）的总和。

React Element 树和 Fiber 树是在 reconciler 过程中，相互交替，逐级构造进行的。这个生成过程，就采用了 DFS 遍历，主要源码位于 ReactFiberWorkLoop.js 中。我这里进行简化，你可以清晰看到 DFS 过程：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


function workLoopSync() {
  // 开始循环
  while (workInProgress !== null) {
    performUnitOfWork(workInProgress);
  }
}
function performUnitOfWork(unitOfWork: Fiber): void {
  const current = unitOfWork.alternate;
  let next;
  // beginWork 阶段，向下遍历子孙组件
  next = beginWork(current, unitOfWork, subtreeRenderLanes);
  if (next === null) {
    // completeUnitOfWork 是向上回溯树阶段
    completeUnitOfWork(unitOfWork);
  } else {
    workInProgress = next;
  }
}

另外，React 中，当 context 数据状态改变时，需要找出依赖该 context 数据状态的所有子节点，以进行状态变更和渲染。这个过程，也是一个 DFS，源码你可以参考 ReactFiberNewContext.js。

继续树的应用这个话题，上一讲中我们介绍了二叉搜索树，这里我们来介绍字典树这个概念，并说明其应用场景。

字典树（Trie）是针对特定类型的搜索而优化的树数据结构。典型的例子是 AutoComplete（自动填充），也就是说它适合实现“通过部分值得到完整值”的场景。因此字典树也是一种搜索树，我们有时候也叫作前缀树，因为任意一个节点的后代都存在共同的前缀。当然，更多基础概念需要你提前了解。

我们总结一下它的特点：

字典树能做到高效查询和插入，时间复杂度为 O(k)，k 为字符串长度；

但是如果大量字符串没有共同前缀，就很耗内存，你可以想象一下最极端的情况，所有单词都没有共同前缀时，这颗字典树会是什么样子；

字典树的核心就是减少不必要的字符比较，提高查询效率，也就是说用空间换时间，再利用共同前缀来提高查询效率。

除了我们刚刚提到的 AutoComplete 自动填充的情况，字典树还有很多其他应用场景：

搜索

分类

IP 地址检索

电话号码检索

字典树的实现也不复杂，我们可以一步步来，首先实现一个字典树上的节点，如下代码：

1
2
3
4
5
6
7
8


class PrefixTreeNode {
  constructor(value) {
    // 存储子节点
    this.children = {}
    this.isEnd = null
    this.value = value
  }
}

一个字典树继承 PrefixTreeNode 类，如下代码：

1
2
3
4
5


class PrefixTree extends PrefixTreeNode {
  constructor() {
    super(null)
  }
}

我们可以通过下述方法实现：

addWord：创建一个字典树节点，如下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


addWord(str) {
    const addWordHelper = (node, str) => {
          // 当前 node 不含当前 str 开头的目标
        if (!node.children[str[0]]) {
            // 以当前 str 开头的第一个字母，创建一个 PrefixTreeNode 实例
            node.children[str[0]] = new PrefixTreeNode(str[0])
            if (str.length === 1) {
                node.children[str[0]].isEnd = true
            } 
            else if (str.length > 1) {
                addWordHelper(node.children[str[0]], str.slice(1))
            }
        }
    }
    
    addWordHelper(this, str)
}

predictWord：给定一个字符串，返回字典树中以该字符串开头的所有单词，如下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


predictWord(str) {
    let getRemainingTree = function(str, tree) {
      let node = tree
      while (str) {
        node = node.children[str[0]]
        str = str.substr(1)
      }
      return node
    }
    // 该数组维护所有以 str 开头的单词
    let allWords = []
    let allWordsHelper = function(stringSoFar, tree) {
      for (let k in tree.children) {
        const child = tree.children[k]
        let newString = stringSoFar + child.value
        if (child.endWord) {
          allWords.push(newString)
        }
        allWordsHelper(newString, child)
      }
    }
    let remainingTree = getRemainingTree(str, this)
    if (remainingTree) {
      allWordsHelper(str, remainingTree)
    }
    return allWords
}

至此，我们实现了一个字典树的数据结构。

总结

这一讲，我们针对上一讲中的经典数据结构，结合前端应用场景进行了逐一分析。我们能够看到，无论是框架还是业务代码，都离不开数据结构的支持。数据结构也是计算机编程领域中一个最基础也是最重要的概念，它既是重点，也是难点。

本讲内容总结如下：

说到底，数据结构的真正意义在于应用，这里给大家留一个思考题，你还在哪些场景看见过数据结构呢？欢迎在留言区和我分享你的观点。

下一讲，我们就正式进入前端架构设计的实战部分，这也是本专栏的核心环节，是对之前所学知识的综合运用和设计，请继续保持学习！

-– ### 精选评论

文章目录