数组

问题:为什么数组下标是从0开始,而不是从1开始;

什么是数组?

数组是一种线性表数据结构,它用一组连续的内存空间来存储一组相同类型的数据

线性表结构:数据排成一条线一样的结构,每个线性表上最多只有前和后两个方向,除数组外,链表、队列、栈也是线性结构。

非线性结构:比如:二叉树、图、堆等,在非线性结构中,数据之间并不是简单的前后关系。

连续的内存空间和相同类型的数据:正式因为这两个特性,才有了它的一大特性:“随机访问”;缺点:在数组中要进行删除或者插入操作需要进行大量的迁移工作,效率低下;

关于数组的随机访问:例如一个长度为10int类型的数组 int a[] = new int[10];在下图中,计算机给数组 a[10]分配了一块儿连续的内存空间 1000~1039;其中,内存的首地址 base_address=1000

我们知道,计算机会给每一个内存单元分配一个地址,通过地址来访问到内存中存储的数据;当计算机需要随机访问数组中的元素时,会根据如下的公式找出该元素存储的内存地址:

1
a[i]_address = base_address + i * data_type_size

其中 data_type_size表示数据中每个元素的大小。在当前例子中存储的为 int 类型,所以 data_type_size的大小为 4

“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

低效的插入和删除

插入操作

假设数组arr的长度为n,现在我们要在数组arr的第k个位置插入一个元素,为了把 k这个位置腾出来给新的元素,那么我们需要把 k~n这部分元素都顺序往后移一位。

如果是插入到数组的末尾,那么我们就不需要对移动数据,这时候时间复杂度为O(1)。如果在数组的开头插入元素,那所有的数据都要往后移一位,这时候的时间复杂度为O(n)。那么平均复杂度则为O(n)

如果我们插入的元素是有序的,那么我们就必须按照上边的操作依次将数组往后移动一位。但是如果数组中的元素没有任何规律,数组只是被当做一个存储数据的集合。在这种情况下,如果想要将某个数据插入到k这个位置,为了避免大量的数据迁移,最简单的方法就是,直接将第k位的元素放到最后,把要插入的元素直接放到k的位置。

例如:现有数组 a[10]存储了五个元素:a、b、c、d、e;我们现在要将元素x插入到第三个位置,我们只需要把c放到a[5],将a[2]赋值为x即可;最终得到的数组中的元素为:a、b、x、d、e、c;利用这种处理技巧,在特定场景下,在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)

删除操作

和插入操作类似,当我们要删除数组中的某个元素时,要对数据进行搬移操作,不然数据中间会出现空洞,内存就不连续了;

和插入类似,如果删除数组末尾的数据,则最好情况时间复杂度为 O(1);如果删除开头的数据,则最坏情况时间复杂度为 O(n);平均情况时间复杂度也为 O(n)

实际上,在某些特殊场景下,我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行,删除的效率是不是会提高很多呢?

例如:数组 a[10] 中存储了 8 个元素:a,b,c,d,e,f,g,h。现在,我们要依次删除 a,b,c 三个元素;为了避免 d,e,f,g,h 这几个数据会被搬移三次,我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据,只是记录数据已经被删除。当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。

这是 JVM 标记清除垃圾回收算法的核心思想

解题开篇

现在我们来思考开篇的问题:为什么大多数编程语言中,数组要从 0 开始编号,而不是从 1 开始呢?

从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。前面也讲到,如果用 a 来表示数组的首地址,a[0] 就是偏移为 0 的位置,也就是首地址,a[k] 就表示偏移 kdata_type_size 的位置,所以计算 a[k] 的内存地址只需要用这个公式:

1
a[k]_address = base_address + k * data_type_size

但是,如果数组从 1 开始计数,那我们计算数组元素 a[k] 的内存地址就会变为:

1
a[k]_address = base_address + (k - 1) * data_type_size

对比两个公式,我们不难发现,从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。

数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从 0 开始编号,而不是从 1 开始。

思考:

  1. JVM 的标记清除垃圾回收算法的核心理念。
  2. 前面我提到一维数组的内存寻址公式,思考、类比一下,二维数组的内存寻址公式是怎样的呢?

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×