关于前端:比较JavaScript中的数据结构数组与对象

作者：Vivek Bisht
译者：前端小智
起源：blog
挪动端浏览：https://mp.weixin.qq.com/s/nbYsKonWtLNK95jMd4dY-A

有幻想，有干货，微信搜寻 【大迁世界】 关注这个在凌晨还在刷碗的刷碗智。

本文 GitHub https://github.com/qq449245884/xiaozhi 已收录，有一线大厂面试残缺考点、材料以及我的系列文章。

在编程中，如果你想持续深刻，数据结构是咱们必须要懂的一块，学习 / 了解数据结构的动机可能会有所不同，一方面可能是为了面试，一方面可能单单是为了进步本人的技能或者是我的项目须要。无论动机是什么，如果不晓得什么是数组构造及何时应用利用字们，那学数据结构是一项繁琐且无趣的过程 😵

这篇文章探讨了什么时候应用它们。在本文中，咱们将学习数组和对象。咱们将尝试通过应用 Big O notation 来了解何时抉择一种数据结构。

Big O notation 大零符号个别用于形容算法的复杂程度，比方执行的工夫或占用内存（磁盘）的空间等，特指最坏时的情景。

数组

数组 是应用最宽泛的数据结构之一。数组中的数据以有序的形式进行结构化，即数组中的第一个元素存储在索引 0 中，第二个元素存储在索引 1 中，依此类推。JavaScript 为咱们提供了一些内置的数据结构，数组就是其中之一 👌

在 JavaScript 中，定义数组最简略的办法是：

let arr = []

下面的代码行创立了一个动静数组（长度未知），为了理解如何将数组的元素存储在内存中，咱们来看一个示例：

let arr = ['John', 'Lily', 'William', 'Cindy']

在下面的示例中，咱们创立一个蕴含一些人名的数组。内存中的名称按以下形式存储：

为了了解数组是如何工作的，咱们须要执行一些操作：

增加元素：

在 JavaScript 数组中，咱们有不同形式在数组结尾，开关以及特定索引处增加元素。

在数组的开端增加一个元素：

JavaScript 中的数组有一个默认属性 length，它示意数组的长度。除了 length 属性外，JS 还提供了 push() 办法。应用这个办法，咱们能够间接在最初增加一个元素。

arr.push('Jake')

那么这个命令的复杂度是多少呢? 咱们晓得，在默认状况下，JS 提供了 length 属性，push()相当于应用以下命令:

arr[arr.length - 1] = 'Jake'

因为咱们总是能够拜访数组的长度属性，所以无论数组有多大，在开端增加一个元素的复杂度总是O(1) 👏。

在数组的结尾增加一个元素：

对于此操作，JavaScript 提供了一个称为 unshift() 的默认办法，此办法将元素增加到数组的结尾。

let arr = ['John', 'Lily', 'William', 'Cindy']
arr.unshift('Robert')
console.log(arr) // ['Robert', 'John', 'Lily', 'William', 'Cindy']

unshift办法复杂度如同和 push 办法的复杂度一样：O(1)，因为咱们只是在后面增加一个元素。事实并非如此，让咱们看一下应用 unshift 办法时会产生什么：

在上图中，当咱们应用 unshift 办法时，所有元素的索引应该 减少 1 。这里咱们的数组个数比拟少，看不出存在的问题。设想一下应用一个相当长的数组，而后，应用 unshift 这样的办法会导致提早，因为咱们必须挪动数组中每个元素的索引。因而，unshift操作的复杂度为O(n) 😋。

如果要解决较大长度的数组，请明智地应用 unshift 办法。在特定索引处增加元素，咱们能够 splice() 办法，它的语法如下：

splice(startingIndex, deleteCount, elementToBeInserted)

因为咱们要增加一个元素，所以 deleteCount 将为0。例如，咱们想要在数组索引为 2 的中央新加一个元素，能够这么用：

let arr = ['John', 'Lily', 'William', 'Cindy']
arr.splice(2, 0, 'Janice')
console.log(arr)
// ['John', 'Lily', 'Janice', 'William', 'Cindy']

你感觉这个操作的复杂性是多少? 在下面的操作中，咱们在索引 2 处增加了元素，因而，在索引 2 之后的所有后续元素都必须减少或挪动 1(包含之前在索引 2 处的元素)。

能够察看到，咱们不是在挪动或递增所有元素的索引，而是在索引 2 之后递增元素的索引。这是否意味着该操作的复杂度为 `O(n/2)？不是 😮。依据 Big O 规定，常量能够从复杂性中删除，而且，咱们应该思考最坏的状况。因而，该操作的复杂度为O(n) 😳。

删除元素：

就像增加元素一样，删除元素能够在不同的地位实现，在开端、开始和特定索引处。

在数组的开端删除一个元素：

像 push()一样，JavaScript 提供了一个默认办法pop()，用于删除 / 删除数组开端的元素。

let arr = ['Janice', 'Gillian', 'Harvey', 'Tom']
arr.pop()
console.log(arr)
// ['Janice', 'Gillian', 'Harvey']

arr.pop()
console.log(arr)
// ['Janice', 'Gillian']

该操作的复杂度为O(1)。因为，无论数组有多大，删除最初一个元素都不须要扭转数组中任何元素的索引。

在数组的结尾删除一个元素：

JavaScript 提供了一个默认办法shift() 的默认办法，此办法删除数组的第一个元素。

let arr = ['John', 'Lily','William','Cindy']
arr.shift()
console.log(arr) // ['Lily','William','Cindy']
arr.shift()
console.log(arr);// ['William','Cindy'] 

从下面咱们很容易能够看出 shift()操作的复杂度为O(n)，因为删除第一个元素后，咱们必须将所有元素的索引移位或减量1。

在特定索引处删除:

对于此操作，咱们再次应用 splice() 办法，不过这一次，咱们只应用前两个参数，因为咱们不打算在该索引处增加新元素。

let arr = ['Apple', 'Orange', 'Pear', 'Banana','Watermelon']
arr.splice(2,1)
console.log(arr) // ['Apple', 'Orange', 'Banana','Watermelon']

与用 splice 增加元素操作相似，在此操作中，咱们将递加或挪动索引 2 之后的元素索引，所以复杂度是O(n)。

查找元素：

查找只是拜访数组的一个元素，咱们能够通过应用方括号符号 (例如: arr[4]) 来拜访数组的元素。

你认为这个操作的复杂性是什么？咱们通过一个例子来演示一下：

let fruits = ['Apple', 'Orange', 'Pear']

后面咱们曾经看到，数组的所有元素都按顺序存储，并且始终分组在一起。因而，如果执行 fruits[1]，它将通知计算机找到名为fruits 的数组并获取第二个元素（数组从索引 0 开始）。

因为它们是按顺序存储的，因而计算机不用查看整个内存即可找到该元素，因为所有元素按程序分组在一起，因而它能够间接在 fruits 数组外部查看。因而，数组中的查找操作的复杂度为 O(1)。

咱们曾经实现了对数组的基本操作，咱们先来小结一下什么时候能够应用数组：

当你要执行像 push()(在开端增加元素) 和pop()(从开端删除元素)这样的操作时，数组是适合的，因为这些操作的复杂度是O(1)。

除此之外，查找操作能够在数组中十分快地执行。

应用数组时，执行诸如在特定索引处或在结尾增加 / 删除元素之类的操作可能会十分慢，因为它们的复杂度为O(n)。

对象

像数组一样，对象也是最罕用的数据结构之一。对象是一种 哈希表，容许咱们存储键值对，而不是像在数组中看到的那样将值存储在编号索引处。

定义对象的最简略办法是：

let obj1 = {}

事例：

let student = {
    name: 'Vivek',
    age: 13,
    class: 8
}

来看一下下面的对象是如何存储在内存中的：

能够看到，对象的键 - 值对是 随机存储 的，不像数组中所有元素都存储在一起。这也是数组与对象的次要区别，在对象中，键 - 值对随机存储在内存中。

咱们还看到有一个 哈希函数 (hash function)。那么这个哈希函数做什么呢？哈希函数从对象中获取每个键，并生成一个哈希值，而后将此哈希值转换为 地址空间，在该地址空间中存储键值对。

例如，如果咱们向学生对象增加以下键值对：

student.rollNumber = 322

rollNumber键通过哈希函数，而后转换为存储键和值的地址空间。当初咱们曾经对对象如何存储在内存有了根本的理解，让咱们来执行一些操作。

增加

对于对象，咱们没有独自的办法将元素增加到后面或前面，因为所有的键 - 值对都是随机存储的。只有一个操作是向对象增加一个新的键值对。

事例：

student.parentName = 'Narendra Singh Bisht'

从上图中咱们能够得出结论，这个操作的复杂性总是O(1)，因为咱们不须要扭转任何索引或操作对象自身，咱们能够间接增加一个键 - 值对，它被存储在一个随机的地址空间。

删除

与增加元素一样，对象的删除操作非常简单，复杂度为O(1)。因为，咱们不用在删除时更改或操作对象。

delete student.parentName

查找

查找的复杂度O(1)，因为在这里，咱们也只是借助键来拜访值。拜访对象中的值的一种办法：

student.class

在对象中增加，删除和查找的复杂度为 O(1)??? 那么咱们能够得出结论，咱们应该每次都应用对象而不是数组吗？答案是不。只管对象很棒，然而在应用对象时须要思考一些小的状况，就是 哈希碰撞(Hash Collisions)。在应用对象时，并非始终应解决此状况，但理解该状况有助于咱们更好地了解对象。

那么什么是 哈希碰撞?

当咱们定义一个对象时，咱们的计算机会在内存中为该对象调配一些空间。咱们须要记住，咱们内存中的空间是无限的，因而有可能两个或更多键值对可能具备雷同的地址空间，这种状况称为 哈希碰撞。为了更好地了解它，咱们看一个例子：

假如为上面的对象调配了 5 块空间

咱们察看到两个键值对存储在雷同的地址空间中。怎么会这样？当哈希函数返回一个哈希值，该哈希值转换为多个键的雷同地址空间时，就会产生这种状况。因而，多个 key 被映射到雷同的地址空间。因为哈希碰撞，增加和拜访对象值的复杂度为O(n)，因为要拜访特定值，咱们可能必须遍历各种键值对。

哈希碰撞 并不是咱们每次应用对象时都须要解决的货色。这只是一个非凡的状况，该状况也阐明了对象不是完满的数据结构。

除了 * 哈希碰撞，应用对象时还必须留神另一种状况。JS 为咱们提供了一个内置的 keys() 办法，用于遍历对象的键。

咱们能够将此办法利用于任何对象，例如：object1.keys()。keys()办法遍历对象并返回所有键。只管此办法看起来很简略，但咱们须要理解对象中的键值对是随机存储在内存中的，因而，遍历对象的过程变得较慢，这与遍历按程序将它们分组在一起的数组不同。

总结一下，当咱们想执行诸如增加，删除和拜访元素之类的操作时，能够应用对象，然而在应用对象时，咱们须要审慎地遍历对象，因为这可能很耗时。除了进行遍历外，咱们还应该了解，有时因为 哈希碰撞，拜访对象操作的复杂度可能会变为O(n)。

代码部署后可能存在的 BUG 没法实时晓得，预先为了解决这些 BUG，花了大量的工夫进行 log 调试，这边顺便给大家举荐一个好用的 BUG 监控工具 Fundebug。

原文：https://blog.soshace.com/comparing-data-structures-in-javascript-arrays-vs-objects/

交换

有幻想，有干货，微信搜寻 【大迁世界】 关注这个在凌晨还在刷碗的刷碗智。

本文 GitHub https://github.com/qq449245884/xiaozhi 已收录，有一线大厂面试残缺考点、材料以及我的系列文章。