数组

在计算机中,数组是最常见的数据结构,对于一些非科班出身的同学,可能对数据结构的认识就到数组为止了。数组是编程语言中的内建类型,一般来说效率很高。

定义

数组是一个储存元素的线性集合(collection)。元素可以通过索引来任意存取,这个索引通常来说是数字,用来计算元素之间的存储位置的偏移量。与其他编程语言不同,JavaScript 中数组的长度可随时改变,并且其数据在内存中也可以不连续。刚刚说了通常这个索引是数字,聪明的你已经发现了,在 Javascript 中,通过字符串依然可以访问对应的元素。

const a = [1, 2, 3];
a['1'] // 2

实际上,Javascript 中的数组是一种比较特殊的对象,用来计算元素之间偏移量的索引是该对象的属性,索引可能是整数。因为在 Javascript 中,对象的属性名必须是字符串,这些数字索引被转化为字符串类型。

Object.keys(a); // ["0", "1", "2"]

因此,Javascript 中的数组,严格地来说应该被称作对象,因此在日常的开发中,它有很多属性和方法可以在编程时使用,譬如上面使用的 Object.keys。

创建数组

const a = new Array(3);
const b = ['A', 'B', 'C'];
b.length // 3

通常来说第二种比较常用。和其他编程语言一样,JS 中的数组也是有序的,并且从 0 开始编号,通过对应的索引可以直接访问到对应的元素。

b[0] // A
b[2] // C

通过索引来替换相应的元素

b[0] = 'D'
b[0] // D

JS 数组中的元素可以是任何类型

const a = ['A', { name: 'B' }, () => 'C']
a[0] // A
a[1].name // B
a[2]() // C

操作数组

  • push

在尾部插入元素

const a = ['A', 'B'];
a.push('C');
a // ['A', 'B', 'C']
  • pop

取出最后一个元素并返回

const a = ['A', 'B'];
a.pop(); // B
a // ['A']
  • shift 取出第一个元素并返回

    const a = ['A', 'B'];
    a.shift(); // A
    a // ['B']
  • unshift

在头部添加元素

const a = ['B'];
a.unshift('A');
a // ['A', 'B']

通过对比 push、pop 和 shift、unshift 我们发现,push 和 pop 是作用于数组尾部的方法,而 shift 和 unshift 是作用于数组头部的方法。

不同之处

上面提到,JS 的数组和其他编程语言的不太一样,它是一种特殊的对象,是对象的扩展,提供了特殊的方法来处理有序的数据集合以及 length 属性。但从本质上来说,它仍然是一个对象。

const a = [];
a.age = 1;
a.age // 1

因为数组是基于对象来实现,所以在对象可以搞的事情,在数组上也能搞。但是这个 JS 引擎会发现,我们在像使用常规对象一样使用数组,那么针对数组的优化就不再适用了,可能会带来性能问题。

下面是关于使用 JS 数组的教科书式的反例:

  • 随意给数组添加属性: arr.name = 'Arr'

  • 制造断层

    const a = [];
    a[0] = 1;
    a[10] = 10;

所以虽然 JS 中的数组可以是不连续的结构,但是我们在使用的时候还是要按照常规套路出牌,不然建议直接使用常规对象 {}

关于性能

上面说到在使用数组的时候,要保证数组内容的连续性,会导致插入和删除的效率比较低。

我们先来看下插入的时候发生了什么。

假设数组的长度为 nn,现在我们需要将一个元素插入到第i i 个位置,有新元素要加入,其他的元素就要挪地方,我们需要把第in i~n 的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢?

如果在数组的尾部插入,那么其他元素都不用动,时间复杂度就是 O(1){\mathcal{O}(1)}。如果运气比较差,刚好要从头部插入,这样一来所有的元素都要往后挪,此时的时间复杂度为O(n){\mathcal{O}(n)}。得到平均的时间复杂度为(1+2+3+...+n)/n=O(n)(1 + 2 + 3 + ... + n) / n = \mathcal{O}(n)

数组的元素越多,插入的位置越靠前,也就意味着需要花费更多的时间。

再来看删除操作,和插入类似,如果删除数组末尾的元素,时间复杂度为 O(1){\mathcal{O}(1)}。如果删除头部的元素,时间复杂度为 O(n){\mathcal{O}(n)},平均的时间复杂度也为 O(n){\mathcal{O}(n)}

综上,数组最大的特点就是支持随机访问,但插入、删除操作的效率也因此受到影响,平均情况时间复杂度为 O(n){\mathcal{O}(n)}

如何实现

先来看 V8 中关于数组的源码:

src/objects/js-array.h

// The JSArray describes JavaScript Arrays
// Such an array can be in one of two modes:
// - fast, backing storage is a FixedArray and length <= elements.length();
// Please note: push and pop can be used to grow and shrink the array.
// - slow, backing storage is a HashTable with numbers as keys.
class JSArray: public JSObject {
public:
// [length]: The length property.
DECL_ACCESSORS(length, Object)
// Number of element slots to pre-allocate for an empty array.
static const int kPreallocatedArrayElements = 4;
};

观察代码我们发现,JS 的数组,继承了 JSObject,所以说 JS 的数组是一个特殊的对象。因此也不难解释,JS 的数组有那么的“骚操作”了,可以存放任意不同类型的值,它的内部也是 k-v 的储存形式。

从源码中的注释来看,数组有两种储存模式:Fast 和 Slow。

  • Fast:快速的存储结构是 FixedArray ,并且数组长度 <= elements.length();快速的根据索引来直接定位,pushpop 操作会对数组进行动态的扩容和缩容

  • Slow:慢速的基于 Hash 表来实现

下面我们来具体看下 FastElementsSlowElements 如何实现。

  • 快数组(FastElements)

FixedArray 是一种线性的存储方式。创建的新空数组,默认的存储方式是快数组,在 pushpop 时会进行对应的扩容和缩容。

  • 慢数组(SlowElements)

慢数组以哈希表的形式来储存在内存中,不用开辟大块连续的存储空间,节省了内存,它的效率比快数组要低。

快与慢之间如何转变

  • 快 --> 慢

首先来看源码中判断是否需要转为慢数组部分的代码:

从代码中可以看出,当出现以下情况时,会转变为慢数组:

插入的 index - 当前的capacity >= kMaxGap(1024) 时,也就是至少有了 1024 个断层,会转变为慢数组
新容量 >= 3 * 扩容后的容量 * 2
  • 慢 --> 快

我们知道了什么时候快数组会转为慢数组,也大概可以猜到什么时候慢数组会转为快数组,为了严谨起见,我们还是看一下源码。

各有千秋

快数组以空间换时间,申请了连续内存,提高效率,但是比较占内存。

慢数组以时间换空间,不需要申请连续的空间,节省了内存,但是效率较低。

本章节分为 4 个部分:

  • Part 1

    • 翻转整数

    • 只出现一次的数字

    • 两数之和

    • 旋转图像

  • Part 2

    • 从排序数组中删除重复项

    • 加一

    • 买股票的最佳时机

    • 移动零

  • Part 3

    • 两个数组的交集

    • 一周中的第几天

    • 有效的数独

    • 除资深以外数组的乘积

    • 存在重复元素

  • Part 4

    • 字谜分组

    • 三数之和

    • 无重复字符的最长子串

    • 矩阵置零

    • 递增的三元子序列

阅读完本章节,你将有以下收获:

  • 熟悉 JavaScript 中数组的常见操作,插入、删除、迭代、排序等。

  • 能够解决一些数组相关的算法题。