数据结构与算法：2.数组

小鱼儿 2023-07-22 09:01 82阅读 0赞

### 文章目录 ###

*   *   *  算法：2.数组
         *   *  线性表：
             *  连续的内存空间和相同类型的数据
             *   *  如何实现随机访问？
                 *  低效的插入和删除：
                 *  容器能否完全替代数组？
             *  数组为何从0开始？

### 算法：2.数组 ###

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

关键词：线性表，连续内存空间

#### 线性表： ####

每个线性表上的数据最多只有前和后两个方向。除了数组，链表、队列、栈等也是线性表结构。

而与它相对立的概念是**非线性表**，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center][]

#### 连续的内存空间和相同类型的数据 ####

这两个限制，使数组具有很牛的特性：“随机访问”。但有利就有弊，这两个限制也让数组的删除、插入变得很低效。为了保证连续性，删除和插入时，就需要做大量的数据搬移工作。

##### 如何实现随机访问？ #####

长度为10的int数组 int a\[ \] =new int \[10\] 。假如在计算机内存分配连续空间1000~1039，如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 1][]

其中，内存块的首地址为 base\_address = 1000。已知，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：  
 a \[ i \] \_ a d d r e s s = b a s e \_ a d d r e s s + i ∗ d a t a \_ t y p e \_ s i z e a\[ i \]\\\_address = base\\\_address + i \* data\\\_type\\\_size a\[i\]\_address=base\_address\+i∗data\_type\_size  
其中 data\_type\_size 表示数组中每个元素的大小。int是 4 个字节。

特别纠正一个“错误”，面试经典话术“链表适合插入、删除，时间复杂度 O(1)；数组适合查找，查找时间复杂度为 O(1)”。数组是适合查找操作，但是即便是排好序的数组，你用二分查找，时间复杂度也是 O(logn)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

##### 低效的插入和删除： #####

插入操作： 长度为 n的数组，在 第k 位置插入元素。为了腾出第K位置，意味着需要将第 k～n 这部分的元素都顺序地往后挪一位。末位插入O(1)，首位插入O(n)，平均（1+2+3+…+n）/n=O(n)。

数组元素值有序时，只能逐个挪位置；数组元素无序时，插入K位置，为了避免k~n的数据搬移，一个简单的办法：直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。复杂度立降为O(1)，快排算法就用到该技巧。

删除操作：为了保证内存连续，不留空洞，删除第K位置元素，k~n元素统统前移。复杂度同插入，也为O(n)。

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

如下图，要删除前三个元素abc

![数组删除][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 2]

为了避免 d，e，f，g，h 会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

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

##### 容器能否完全替代数组？ #####

以Java中ArrayList举例， ArrayList可以将很多数组操作的**细节封装**起来。如数组增删元素时的搬移等。另外**支持动态扩容**。数组本身在定义的时必须预先指定大小，方便分配连续的内存空间。如申请了大小为 10 的数组，当存储第 11 个数据时，就需重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。

而ArrayList 已经帮我们实现好了扩容逻辑。每次存储空间不够的时候，自动1.5x扩容。原始容量为10，其扩容公式：oldCapacity + (oldCapacity >> 1)

扩容操作涉及内存申请和数据搬移，是比较耗时的。如果事先能确定需要存储的数据大小，最好**在创建 ArrayList 的时候事先指定数据大小**。

比如要从数据库中取出 10000 条数据放入 ArrayList。事先指定list大小可以省掉很多次内存申请和数据搬移的耗时操作。

List<UserInfo> list = new ArrayList(10000);
    for (int i = 0; i < 10000; ++i) { 
      list.add(xxx);
    }

何时用到数组？

1.  Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
2.  如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
3.  当要表示多维数组时，用数组往往会更加直观。比如 Object\[\]\[\]\[\]\[\]；而用容器的话则需要这样定义:ArrayList<ArrayList>array

#### 数组为何从0开始？ ####

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。如果用 a 来表示数组的首地址，a\[0\] 就是偏移为 0 的位置，也就是首地址，a\[k\] 就表示偏移 k 个 type\_size 的位置，所以计算 a\[k\] 的内存地址只需要用这个公式：  
 a \[ k \] \_ a d d r e s s = b a s e \_ a d d r e s s + k ∗ d a t a \_ t y p e \_ s i z e a\[k \]\\\_address = base\\\_address + k \* data\\\_type\\\_size a\[k\]\_address=base\_address\+k∗data\_type\_size  
但是，如果数组从 1 开始计数， a\[k\] 的内存地址就会变为：base\_address + (k-1)\*data\_type\_size。(k-1)意味着每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。

当然这都不是压倒性原因，主要是历史原因。C采用了0开始，很多语言沿用了，也有例外，Matlab，甚至有负下标的 Python。

对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/e8adc7618ec24416ba9f8fae2a8d912c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/7fc0bb3587b2434ab9467f765c992c8c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/4da15e949348498ba5071f2ae00924bf.png