数组的随机访问【简介】

【摘要】假如有人问你数组和链表的区别，也许你会回答："链表适合插入、删除操作，插入、删除的时间复杂度为 O(1)；数组适合查找，查找的时间复杂度为 O(1)"。然而实际上，这种表述是不准确的。数组确实是适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，用二分法查找，时间复杂度也是 O(logn)。正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。这是为什么呢，那么我们就进入本文的主讲核心内容：数组的随机访问，来一起了解。

（一）什么是数组？

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

关键点：线性表、连续的内存空间，相同类型的数据

问：啥是线性表？

答：线性表（Linear List），顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

问：连续的内存空间指的是什么？

答：计算机在分配内存空间的时候都会对应分配一个内存地址，连续的内存空间对应的是指连续的内存地址，计算机是通过访问内存地址会获取内存中的值。

问：为什么要是相同数据类型？

答：数据类型相同那么数据存储所占用内存大小一样。

正是因为这两个限制，它才有了一个堪称 "杀手锏" 的特性："随机访问"。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

（二）说到数据的访问，那你知道数组是如何实现根据下标随机访问数组元素的吗？

举个例子：一个长度为 10 的 int 类型数组 int[] a = new int[10]，计算机给数组 a 分配了一块连续内存空间 1000 ~ 1039。（这里 int 类型为 4 个字节），其中，内存块的首地址为 base_address = 1000.

当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

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

如 i = 2（第三个元素）：

1. a2_address = base_address + 2 * data_type_size = 1000 + 2 * 4 = 1008

其中 data_type_size 为数组中每个元素的大小

因为数组是连续存储的，所以根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，找出数据。

（三）为什么数组的下标都是从 0 开始？

若下标为 1 开始：获取第 3 个元素的值，1000 +（3-1）* 4（数据类型占用的内存）= 1008，计算得出第三个元素的内存地址的位置；

若下标从 0 开始：获取第 3 个元素的值，1000 + 2 * 4（数据类型占用的内存）= 1008，省去了一个减法的动作，提高了访问的效率。

今后如果再有人问起链表和数组的区别，那么一定要记得这样回答：数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

我要打赏