Appearance
数组
什么是数组
基本每种编程语言都有数组这种数据结构。
数组是一种线性表结构,在内存里,是一组连续的内存空间,用来存储一组类型相同的数据。
在定义里,有几个关键词:
- 线性表:
顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。
而与它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。
- 连续的内存空间和类型相同的数据
有了这两个限制,数组有一个超级特性:随机访问。但是有利也有弊,这两个限制,也让数组的很多操作变得非常低效,比如,插入和删除的时候,为了保持连续性,就需要大量的数据搬移。
随机访问
数组是一组连续的内存空间,并存储类型相同的数据。所以只要知道被分配的内存的首地址,就可以通过地址偏移随机访问数组的元素,这就是数组杀手锏的特性随机访问。
那数组是怎么做到随机访问的?
以一个长度为 10 的 int 类型数组为例 int[] a = new int[10]
,计算机给数组 a[10]
分配了一块连续的内存空间 1000 ~ 10039,其中首地址为 base_address = 1000。
我们知道计算机会给每个内存分配一个地址,通过地址来访问内存中的数据。当计算机要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素的内存地址:
a[i]_address = base_address + i * data_type_size
其中 data_type_size 表示数组中每个元素的大小。数组中存储的是 int 类型数据,所以 data_type_size 就为 4 个字节。
这就实现了随机访问,时间复杂度为 O(1)。
但是,这并不是说数组查找的时间复杂是 O(1),即使排好序的数组,使用二分查找,时间复杂度也是 O(logn)。
低效的插入和删除
由于数组的内存是连续的,为了保证连续性,插入和删除这两个操作都比较低效。
插入
假设,数组的长度为 n,现在将一个数据插入到第 k 个位置,为了把第 k 个位置腾出来给新的数据,那就需要将第 k ~ n 的这部分数据都顺序的往后挪一位。那时间时间复杂度是多少呢?
如果在数组的尾部插入元素,那么不需要移动数据了,这个时候的时间复杂是 O(1);如果是在开头插入元素,那么需要把所有的数据依次的往后移一位,所以最坏的时间复杂度是 O(n);因为每个位置插入元素的概率是一样的,所以平均时间复杂度就是 (1+2+...+n)/n = O(n)。
如果数组是有序的,那么插入新元素的时候,就必须按照上面的方式移动 k 之后的数据。
但是,如果数组中的数据没有任何规律,数组只是当作一个存储数据的集合。这种情况下,要将某个数据插入到第 k 个位置,为了避免大规模的数据搬移,一个简单的方法就是,直接将第 k 位数据搬移到数组元素的最后,把新元素直接放入到第 k 个位置。
删除
和插入类似,如果要删除第 k 个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了。
如果删除的是数组尾部的数据,那最好时间复杂度是 O(1);如果删除的是开头位置,则最坏情况时间复杂是 O(n);平均情况时间复杂度是 O(n)。
在某些场景下,并不一定要最求数组中数据的连续性,那么我们将多次删除的操作集中在一次执行,就可以提高删除效率了。
例如,有一个数组 a[10]
,依次删除前 3 个元素。为了避免后面的元素被搬移 3 次,每次删除的时候,不进行真正的数据搬移,只是记录数据已经被删除。当数组没有更多空间的时候,这触发一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。
这也是标记清除垃圾回收算法的核心思想。
数组长度和内存大小
在平常的代码中,很多时候,定义一个数组时我们没有指定长度,会给我们分配多少的内存空间呢?以及内存不够的时候如何处理呢?
参考这篇博客从Chrome源码看JS Array的实现,浏览器给我们的初始内存空间为 4,当往第存储第 5 个值的时候,将进行自动扩容。
new_capacity = old_capacity /2 + old_capacity + 16
申请一块更大的内存,把老的数据拷贝过去,然后再将新的数据插入。
js
var arr = [];
for (let i = 0; i < 100; i++) {
arr[i] = i * i;
}
不过值得注意的是,扩容操作涉及内存的申请和数据搬移,是比较耗时的。所以如果事先知道要存储的数据大小,最好在创建数组的时候指定数据大小。
js
var arr = new Array(100);
for (let i = 0; i < 100; i++) {
arr[i] = i * i;
}
复杂度
- 读取:O(1)
- 插入:最好时间复杂度为 O(1),最坏时间复杂度为 O(n),平均时间复杂度为 O(n)
- 删除:最好时间复杂度为 O(1),最坏时间复杂度为 O(n),平均时间复杂度为 O(n)