为什么前端一定要掌握数据结构?

683 阅读14分钟

原文链接:medium.com/siliconwat/…

简要

随着业务逻辑越来越多地从后端迁往前端,前端工程化方面的专业知识变得愈发重要。作为一名前端工程师,我们依赖于像 React 这样的视图库来提高工作效率。而视图库又依赖于像 Redux 这样的数据流工具来管理数据。React 和 Redux 共同遵循响应式设计模式,在该设计模式下,数据的更新将会导致对应 UI 的更新。后端越来越充当着简单的 API 服务器角色,提供数据的检索和更新接口。实际上,后端只是把数据库搬到了前端,期望前端来处理所有的数据控制器逻辑。微服务和 GraphQL 的日益流行证明了这一增长趋势。

现在,除了掌握 HTML 和 CSS 以外,前端工程师还应该掌握 JavaScript。因为客户端成了服务端的数据库“副本”,掌握常用的的数据结构变得至关重要。事实上,一个工程师的水平可以从 ta 知道何时及为何使用特定的数据结构的能力中得以体现。

Bad programmers worry about the code. Good programmers worry about data structures and their relationships.

糟糕的工程师考虑代码,优秀的工程师考虑数据结构及其对应关系。

— Linus Torvalds, Creator of Linux and Git

总的来说,基础的数据结构分三种:类似数组的栈和队列数据结构,它们的区别在于插入和删除条目的方式不同。具有节点的链表、树和图数据结构,这些节点保持着对其它节点的引用。依赖于哈希函数来保存和定位数据的哈希表。就复杂度而言,栈和队列是最简单的,可以用链表来构造。树和图是最复杂的,因为它们扩展了链表的概念。哈希表利用这些数据结构来高效的执行任务。就效率而言,链表最适合记录与存储数据,哈希表则最适合搜索与检索数据。

本文将依照“为什么(why)”与“何时(when)”的顺序来进行阐释说明,让我们开始吧!

栈(Stack)

可以说,Js 中最重要的栈就是调用栈(译者注:调用栈是 js 解释器追踪函数执行流的一种机制),在该栈中,无论何时执行函数,我们都会往栈中推入该函数的作用域。在编码中,它只是一个具有两个基本操作的数组:pushpoppush 将元素添加到数组的头部,而pop将它们从同一位置删除。换句话说,栈遵循“后进先出”的原则(LIFO)。

下面是栈的示例代码。请注意,我们可以颠倒栈的顺序:底部变为顶部,顶部变为底部。因此,我们可以使用数组的 unshiftshift 方法来分别代替 pushpop

codepen.io/thonly/pen/…

随着条目数的增加,push/pop将会比unshift/shift拥有更好的性能,因为后者的每个条目都需要重建索引,但前者不需要。

队列(Queue)

Js 是一门事件驱动型语言,它使得支持非阻塞操作成为可能。在内部,浏览器只管理一个线程来运行整个 Js 代码,它使用事件队列(event queue)将事件注册到队列中,然后使用事件循环(event loop)来监听被注册的事件。为了在单线程环境中支持异步操作(节省资源并增强 Web 体验),监听函数只有当调用栈为空时才会出队列并执行。Promise 就是基于这种事件驱动架构设计的,它允许用“同步模式”来执行不会阻塞其它操作的异步代码。

在编程中,队列仅仅是拥有两个主要操作方法的数组:Unshift将条目列入数组的尾部,而Pop则将它们从数组头部列出。换句话说,队列遵循“First in, First Out”的原则(FIFO)。如果颠倒方向,我们可以使用pushshift方法来替换unshiftpop方法。

队列的代码示例如下:

codepen.io/thonly/pen/…

链表(Linked List)

类似于数组,链表也是按照顺序存储数据元素。不同的是,链表保存指向其它元素的指针,而非索引。链表的第一个节点被称为头部节点,最后一个节点被称为尾部节点,在单链表中,每个检点只有一个指向下个节点的指针。在单链表里,头部节点是我们遍历剩余节点的的起点。在双链表中,每个节点还保留了指向上一个节点的指针。因此,我们也可以从尾部节点开始,“倒退遍历“到头部节点。

链表具有常量的插入和删除时间,因为我们只需更改指针即可。但在数组中执行相同的操作却需要线性时间,因为后续条目需要移位。此外,只要有空间,链表就可以增长。然而,即使是可以自动调整大小的“动态数组”在空间利用上也是出乎意料的昂贵。当然,事物总有权衡取舍。在链表中检索和编辑一个元素,我们需要遍历整个链表,这等同于线性时间。然而对于有索引的数组,这样的操作损失是微不足道的。

类似于数组,链表也可以进行栈的操作。该操作很简单,只需将头部作为插入和取出的唯一位置。链表也可以进行队列操作,这可以使用双向链表来实现,插入发生在尾部,删除发生在头部,反之亦然。对于大的数据而言,这种实现队列的方案比数组的性能更高,因为在数组的开始位置插入和移出元素,需要线性的时间来重新索引后续的每个元素。

链表数据结构在客户端和服务端都很有用。在客户端,像 Redux 这样的状态管理库就是以链表的形式构建它的中间件逻辑。当actionsdispatch时,它们通过管道从一个中间件传递到下一个中间件,直到所有的actions都到达reducers之前被访问。在服务端,像Express这样的 web 框架也以类似的逻辑构建它的中间件。当收到请求,请求通过管道一个接一个的传递下去,直到请求被发出。

双向链表的代码如下:

codepen.io/thonly/pen/…

树(Tree)

树类似于数组,区别在于它在层次结构中保留了对多个子节点的引用。换句话说,每个节点不止拥有一个父节点。DOM 树就是这样一种数据结构,它拥有一个 html 根节点,然后分成 head节点和 body 节点,这两个节点又进一步细分为多个你所熟悉的 html 标签。更深层面上,原型继承和 React 的组件也采用类似的树形结构。当然,作为DOM的内存表现形式,React 的虚拟 Dom也是一个树形结构。

二叉搜索树是特殊的,因为它拥有的子节点不能超过两个。左子节点的值必须小于或等于其父节点的值,而右子节点的值必须大于父节点的值。通过这种结构和平衡方式,我们可以在指数级时间内检索任何值,因为我们可以在每次迭代中忽略另一半分支。插入和删除的时间也是指数级的。此外最小值和最大值也可以很容易的在最左边和最右边的叶子节点中找到。

遍历树可以在垂直或水平过程中进行。在垂直方向的深度优先遍历(DFT)中,递归算法将会比迭代算法更加优雅。节点遍历可以按照前序遍历、中序遍历、后序遍历的方式进行。如果我们需要先访问根节点再探索叶子节点,我们应选择前序遍历。但如果我们需要先访问叶子节点再访问根节点,我们应选择后序遍历。顾名思义,中序遍历使我们可以按照顺序进行遍历。这种特性使二叉搜索树成为排序的最佳选择。

在水平方向上的广度优先遍历(BFT)中,迭代比递归更优雅。这需要使用一个队列来追踪每次迭代的所有子节点。这样一个队列所需的内存是微不足道的。然而,如果树的形状宽大于深,BFT 是比 DFT 更好的选择。此外,BFT 在任意两个节点之间采用的路径是可能的最短路径。

二叉搜索树的示例代码如下:

codepen.io/thonly/pen/…

图(Graph)

如果一个树可以自由的拥有多个父级节点,它将变为Graph(图)。将图中的节点连接在一起的边可以是有方向的,也可以是无方向的,可以是加权的,也可以是未加权的。同时具备方向和权重的边类似于矢量。

混合形式的多重继承和具有多对多关系的数据对象生成图形结构。社交网络和互联网本身也是图。自然界中最复杂的图是我们的人脑,神经网络试图复制人脑来赋予机器超级智能。

哈希表(Hash Table)

哈希表是一种类似于字典的结构,它将键与值进行配对。每个键值对在内存中的储存位置由哈希函数决定,该哈希函数接收一个 key ,然后返回它应该插入和检索的地址。如果两个或更多的 key 被转换成相同地址,可能会导致冲突。为了保持哈希函数的健壮性,getter 和 setter 方法应该预防到这些问题,来确保可以恢复所有的数据,并且不会覆盖任何数据,通常,链表可以提供最简单的解决方案。拥有巨大空间的哈希表也同样可以解决该问题。

如果我们知道我们的地址为整数序列,我们可以简单的使用数组来储存键值对。但对于更复杂的地址映射,我们可以使用MapsObjects。哈希表的插入和查找时间平均起来为常量级。但由于冲突和大小的调整,这一可以忽略的时间成本可能会增长到线性时间。然而在实践中,我们会假定我们的哈希函数足够智能,很少会发生冲突和大小调整,而且成本很低。如果键表示地址,则不需要哈希了,所以简单的对象字面量就足够了。当然,我们总会面临权衡取舍。键和值之间的简单对应以及键和地址之间的简单关联性牺牲了数据之间的联系。因此,哈希表布斯和储存数据。

如果在权衡对比之下更倾向于检索数据而非储存数据,则没有其它数据结构比哈希表更适合查找、插入、删除了。因此,哈希表的广泛使用不足为奇了。从数据库到服务端,再到客户端,哈希表,尤其是哈希函数,对应用程序的性能和安全性都是至关重要的。数据库的查询速度在很大程度上依赖于按序保持对指定记录的索引表。这样,二分查找可以实现指数级的查找速度,这对大型数据是一个巨大的性能优势。

在客户端和服务端,大多数流行库都利用内存来使性能最大化。通过哈希表保持对输入和输出的记录,函数对同一个输入只会运行一次。流行的Reselect库就是利用此缓存策略来优化启用Redux的应用程序中的mapStateToProps函数。事实上,在幕后,JavaScript 引擎也利用被称为堆(heap)的哈希表来储存所有我们创建的变量和基本类型,通过调用栈来访问它们。

互联网本身也依赖哈希算法来安全运行。互联网的架构理念是任何计算机都可以通过互连的网络与任何其他计算机通信。每当一个设备连入到互联网,它将成为数据流流经的路由器。然而,这是一把双刃剑。分散的架构意味着数据在中继传输中被任意设备监听和篡改。MD5SHA256等哈希函数在防止这种中间人攻击方面起着关键作用。HTTPS 之所以安全就是因为这些哈希函数的使用。

受互联网的启发,区块链技术寻求在协议层面上将网络的结构进行公开。通过使用哈希函数为每个数据块创建一个不可变的指纹,并将整个数据库公布在网络上以供任何人查看和贡献。从结构上来说,区块链只是哈希密码的二叉树单链表。哈希是如此神秘,以至于任何人都可以公开的创建和更新金融交易数据库!令人难以置信的是其创造金融的能力。这曾经只可能是政府和中央银行的事情,现在,任何人可以安全的创建ta自己的货币了!这是以太币和比特币的前瞻创造。

随着数据库越来越走向开放,对能够抽象出所有低级密码复杂度的前端工程师的需求也变得更加复杂。在未来,主要的区别将是用户体验。

哈希表的示例代码如下:

codepen.io/thonly/pen/…

结论

随着业务逻辑越来越多的从服务端转移到客户端,前端对于数据层的应用变得至关重要。对数据层的合理管理需要熟练掌握其所需要的数据结构。没有一种数据结构能完美的契合任意应用场景,因为一个方面的优化往往意味着另一方面的遗漏。有些数据结构在数据储存方面效率更高,而有些数据结构在数据检索性能更高。通常,优化总伴随着牺牲。在极端情况下,链表最适合储存,并且可以转化为堆、栈(线性时间)。另一方面,没有其它数据结构可以匹敌哈希表的检索速度(常量时间)。树结构性能介于中间位置(对数时间),只有图形结构才能描绘自然界最复杂的结构: 人脑(多项式时间)。拥有辨别时间和清晰表达何时及为何使用哪种数据结构的技能是牛逼前端工程师的标志。

这些数据结构的示例随处可见。从数据库,到服务器,再到客户端,甚至 js 引擎本身,这些数据结构将芯片上本质只是开和关的”开关“具体化为逼真的”对象“。虽然只是一个个数据,但这些数据对社会的影响是巨大的。你之所以能自由、安全的阅读这篇文章,这证明了internet令人敬畏的体系结构及数据结构。然而,这仅仅是个开始。未来十年,人工智能和去中心化的区块链将重新定义人类的意义,以及如何管理我们的生活。存在主义的洞察力和去中心化制度将是最终成熟的互联网的特征。