【数据结构与算法】三、数组
文章目录
什么是数组?
数组是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。
线性表就是数据排成一条线一样的结构,每个线性表上的数据只有前和后两个方向,如数组、链表、队列、栈等;非线性表中,数据之间并不是简单的前后关系,如树、堆、图等。
数组属于线性表的顺序存储表示,通常称为顺序表。其特点是,逻辑上相邻的数据元素,其物理次序也是相邻的。
因为数组存储的是相同类型的数据,每个元素长度是固定的,再加上数组使用了连续的内存空间,所以数组具有_随机访问_的特性。
由于计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据,
所以这里以一个长度为 10 的 int 类型的数组 int[]a = new int[10] 来举例:
计算机给数组 a 分配了一块连续内存空间,记首地址为 base_address;
假设数组中每个元素的占用的内存大小为 data_type_size,
当计算机需要随机访问数组中的某个元素时,它会通过寻址公式计算出该元素存储的内存地址:a[i]_address = base_address + i * data_type_size
由于数组的随机访问的特性,所以数组数据结构适合查找,当根据下标进行随机访问的时候,时间复杂度为 O( 1 )。
此处需要注意的是,数组查找的时间复杂度为 O( n ),随机访问的时间复杂度才是 O( 1 )。
低效的插入和删除
由于数组使用的是连续的内存,所以会导致插入和删除操作比较低效。
插入
假设数组长度为 n,如果需要将一个新数据插入到数组的第 k 个位置,就需要将数组中第 k~n 的元素按照顺序依次往后平移一位,然后将新数据放到空出来的 k 这个位置上。
如果运气好,是在数组的末尾插入元素,就不需要移动数据了,这时候的时间复杂度为 O( 1 );如果运气不好,需要在数组的开头插入元素,所有的数据都需要往后移动,这时候的时间复杂度为 O( n );因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为 ( 1 + 2 + 3 + ... + n )/n = O( n )。
如果数组中的数据是有序的,我们在插入一个新元素的时候,避免不了大规模的数据搬移;
但是如果数组是无序的、只是作为存储容器使用,可以将新元素直接插入数组尾部,避免数据搬移。
利用这个思想,可以将时间复杂度降为 O( 1 )。
删除
跟插入类似,如果要删除第 k 个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了。
同样,如果删除数组末尾的数据,最好情况时间复杂度为 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 的标记清除算法就是基于此思想实现的。
数组访问越界问题
访问数组的本质其实就是访问一段连续的内存,只要数组通过偏移计算得到的内存地址是可用的,那么程序就不会报错。
在 C 语言中,只要不是访问受限的内存,所有的内存空间都是可以自由访问的。
假设有一个数组 a[3],数组内元素只能通过 a[0]、a[1]、a[2] 寻址访问到;
如果此时访问 a[3],根据前面的寻址公式,a[3]也会被定位到某块内存地址上,
但是此地址不在数组 a 内,这就造成了数组越界的问题。
但是这样情况下,一般都会出现莫名其妙的逻辑错误,debug 的难度非常大。
很多计算机病毒就是利用到了代码中的数组越界可以访问非法地址的漏洞,来攻击系统。
但是不是所有的语言都像 C 一样,把数组越界检查交给程序员来做。比如 Java,如果在数组 a[3] 中访问 a[3],就会抛出 java.lang.ArrayIndexOutOfBoundsException。
高级编程语言中,容器能否完全代替数组?
针对数组类型,很多高级编程语言都提供了容器类,如 Java 中的 ArrayList。
在项目开发中,什么时候适合用数组,什么时候适合用容器呢?
以 Java 的 ArrayList 为例,ArrayList 对比数组最大的优势,就是可以将很多数组操作的细节封装起来,比如数组插入、删除时的数据搬移等。另外一个优势,就是支持动态扩容。
数组本身在定义的时候,需要预先指定大小,因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组,当第 11 个数据需要存储到数组中时,我们就需要重新分配一块更大的空间,将原来的数据复制过去,再将新的数据插入。
如果使用 ArrayList,就完全可以不用关心底层的扩容逻辑。每次空间不够用时,它都会自动扩容。
需要注意的是,扩容操作涉及内存申请和数据搬移,比较耗时,所以如果能事先确定需要存储的数据大小,最好在创建 ArrayList 的时候指定数据大小。
但是这是不是意味着数组就无用武之地了?答案是否定的。
- Java 中的 ArrayList 无法存储基本类型,比如 int、long,需要封装为 Integer、Long;而自动装箱、拆箱又有一定的性能损耗,所以如果特别关注性能,或者希望使用基本类型,则可以使用数组。
- 如果数据大小事先已知,并且对数据的操作非常简单,用不到 ArrayList 提供的大部分方法,也可以直接使用数组。
- 当要表示多维数组时,用数组会更直观。
- 对于业务开发,直接使用容器就够了,省时省力,损耗的一点性能完全不会影响到系统整体的性能。但是如果是做一些非常底层的开发,性能的优化需要做到极致,数组就会成为首选。
为什么大多数数组要从 0 开始编号?
从数组的内存模型上和寻址公式看,“下标”最确切的定义应该是“偏移(offset)”。
如果用 a 表示数组的首地址,a[0] 就是偏移量为 0 的位置,也就是首地址,a[k] 就是偏移为 k 个 type_size 的位置,所以 a[k] 的内存地址计算:a[k]_address = base_address + k * type_size
假如数组从 1 开始编号,那我们计算 a[k] 的内存地址,就变为:a[k]_address = base_address + (k-1) * type_size
这样的结果,对于 CPU 来说,就是每次随机访问数组元素都多了一次减法指令。
数组作为非常基础的数据结构,通过下标随机访问数组元素又是非常基础的编程操作,效率的优化就要尽可能做到极致,所以为了减少一次减法操作,数组选择了从 0 开始编号,而不是 1。
另外还有历史原因。当初 C 语言设计者用 0 开始计数数组下标,之后的 Java 等高级语言都效仿了 C 语言,或者说是为了减少 C 语言程序员学习 Java 的成本,因此继续沿用了从 0 开始计数的习惯。实际上,还有很多语言不是从 0 开始计数的,比如 Matlab;还有一些语言支持负数下标,比如 Python。
思考
此处摘用 杰杰 同学的回答:
JVM 的标记清除算法
大多数主流虚拟机采用可达性分析算法来判断对象是否存活。在标记阶段,会遍历所有 GC ROOTS,将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后,清理工作才会开始。
不足:
- 效率问题。标记和清理效率都不高,但是当知道只有少数垃圾产生时会很高效。
- 空间问题。会产生不连续的内存空间碎片。
二维数组内存寻址
对于 m * n 的数组, a[ i ][ j ] (i < m, j < n) 的地址为:
a[i][j]_address = base_address + ( i * n + j ) * type_size
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论