Array

一、OverView

思维导图：

二、特性

数组应该是所有程序员中最熟悉的数据结构了，如果你简单的回忆一下数组的具体含义，你可以得到已经几个重要的结论：

• 🐷 线性结构
• 🐢 连续内存
• 🐭 存储相同类型

2.1 线性结构

顾名思义，线性结构就是这个结构像线性一样，而非是其它结构，这样说的确有点抽象，可以从下面几个例子来看一下：

注：

• 这里的 Array 是使用 Java 中的内存模型，即 char 为 2 个字节
• 链表没有使用哨兵模式 (后面会提到)

2.2 连续内存和相同数据类型

正如上面例子中的数组一样，在这个数组中，它们的地址是连续的，且数组中每一个元素都是 char 类型，正是由于这两个特性，让数组实现了这一生中最重要的操作：快速查询，它可以达到 O(1) 的速度，当然要对这里进行限制条件，即准确的表达应该是按照下标进行查询，它的时间复杂度可以达到 O(1) ，而不是我们经常说的根据某个值来确定它的位置等，这样的查询方式 (已经排好序) 最快也是 O(logn)

先来看一下是如何实现根据下标来进行时间复杂度为 O(1) 的操作：

我们很容易就发现这样的规律：

前提：char[] charList = new char[6]

结论：address = baseAddress + i * charSize

也就是说，我们只需要知道以下条件就行：

• 该数组的起始地址 baseAddress，也就是图中的 1000
• 该数组是什么类型，这里是 Java 的 char 类型，字节数为 2

就这样，可以通过上面条件求出这里任意一个元素的地址。

假知识：

如果，起始地址从 1 开始的话，来计算一下会发生什么情况？

计算公式是不是要变为：address = baseAddress + (i - 1) * charSize

你想，你细想，是不是每次都要多进行一次减法操作，这样 加法器 (在计组中是没有减法器存在的，通过转换为加法来计算)是不是就要多进行一次计算

这会不会就是当年定义数组从 0 开始的那位程序员的 idea 呢？(强者如斯) 当然不是，这仅仅是一种规定而已，上面的一系列猜测，仅仅是为了猜而猜

2.3 插入和删除

One coin has two sides，有利自然有弊。在上面已经说过了数组的查询，也是数组的最大优点；当然数组在插入和删除的时间复杂度比较高，但是也有一些优化的小 tips。

插入

为什么说数组中插入，会是时间复杂度变高呢？主要是数组是连续存储的，如果只是在最后一个元素插入一个新的元素，那么没什么大不了；但是你要是在第一个元素后面插入一个新的元素，那就要把原本的第二个元素到最后一个元素全部向后移动一个 typeSize，如下：

由上面的图，可以轻易看出插入新的元素在最后：前面元素的位置都未变；插入在第二个位置：第二个元素到最后一个元素的位置都 + 1 了

平均的时间复杂度就为：O(n)

当然这样做是有前提的：就是是要有序的。如果对排序没有要求的，可以如下操作：

此时只需要把原本在 1 位置的元素复制到新扩展的位置，把 1 中的元素换成新的元素，在上述的例子中对应的就是：将 n 复制到位置 5 上，然后将位置 1 的元素覆盖为新元素 a

删除

删除数组中的元素与插入操作类似：主要是为了保证内存的连续性，如果删除最后一个元素，那没什么问题；如果是删除第一个元素，那么第一个元素后面的所有元素都要向前移动一个位置。

则平均的时间复杂度就为：O(n)

一些特殊情况下的删除：如果对没有立马对删除元素进行垃圾回收的操作，有什么比较好的方式？

在 JVM 进行垃圾回收时，有以下几种算法：

• 标记 - 清除算法
• 复制算法
• 标记 - 整理算法
• 分代收集算法

在这里主要介绍一下 标记 - 清除算法，简单来说：

在 JVM 进行垃圾回收时，不立马进行回收，只是对要进行回收的元素进行标记，等到积累到一定量再进行一次批处理，例子如下：

可以看见，只需要对要删除的元素进行标记，随后到最后一次性进行回收

但是这样也会带来很多问题，如效率问题和空间问题，如下：

如果是删除的元素是一段一段的，那么就会产生大量的空间碎片，所以 JVM 后面还有很多其余的回收算法

2.4 关于数组越界的问题

我们尝试在 Ubuntu 18.04 64bit 中运行下面这段 C 代码：

OverFlow.c

1
2
3
4
5
6
7
8
9
10
11

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

按照正常想法走下去：会打印三行 hello world，就会运行完毕

让我们进行测试吧：

你就会看到控制台开始无限打印 hello world 了：


只要在内存足够的情况下，这个程序就会一直运行下去，这就是典型的 StackOverFlow 问题

简单的就可以理解成如下结构：

这个栈的结构具体可以参考《深入理解计算机系统》，这里出现上述情况的主要原因：

• C 语言中是所有的内存都是可以访问 (除了受限内存以外)
• 在上述代码中 i <=3，说明 a[3] = 0 在内存的某个地址上
• 而这个地址本身是 原来的 i 的地址 ，所以就相当于 i = 3 又被赋值为 i = 0，然后继续不断循环

如果想知道这个栈溢出是如何具体实现的话，可以是用 objdump 命令进行反编译，再进行分析，其中主要的汇编代码如下：其中关键行应该为 65f、67e、682、661

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

000000000000063a <main>:
 63a:    55                       push   %rbp
 63b:    48 89 e5                 mov    %rsp,%rbp
 63e:    48 83 ec 20              sub    $0x20,%rsp
 642:    89 7d ec                 mov    %edi,-0x14(%rbp)
 645:    48 89 75 e0              mov    %rsi,-0x20(%rbp)
 649:    c7 45 fc 00 00 00 00     movl   $0x0,-0x4(%rbp)
 650:    48 c7 45 f0 00 00 00     movq   $0x0,-0x10(%rbp)
 657:    00 
 658:    c7 45 f8 00 00 00 00     movl   $0x0,-0x8(%rbp)
 65f:    eb 1d                    jmp    67e <main+0x44>
 661:    8b 45 fc                 mov    -0x4(%rbp),%eax
 664:    48 98                    cltq   
 666:    c7 44 85 f0 00 00 00     movl   $0x0,-0x10(%rbp,%rax,4)
 66d:    00 
 66e:    48 8d 3d 9f 00 00 00     lea    0x9f(%rip),%rdi        # 714 <_IO_stdin_used+0x4>
 675:    e8 96 fe ff ff           callq  510 <puts@plt>
 67a:    83 45 fc 01              addl   $0x1,-0x4(%rbp)
 67e:    83 7d fc 03              cmpl   $0x3,-0x4(%rbp)
 682:    7e dd                    jle    661 <main+0x27>
 684:    b8 00 00 00 00           mov    $0x0,%eax
 689:    c9                       leaveq 
 68a:    c3                       retq   
 68b:    0f 1f 44 00 00           nopl   0x0(%rax,%rax,1)

其实，在这个巨大漏洞出来后，现在的内存已经加了金丝雀保护 (canary) 了，为了让这个漏洞复现，在上面编译的过程中，已经使用 -fno-stack-protector 将保护关闭了

而如果该程序在 Java 中复现，在编译时就会抛出 ArrayIndexOutOfBoundsException 的异常了

三、Java 中的数组

在 Java 中，对于数组没有什么好了解的，顶多就一个基本语法；但是在 Java 中有一个集合类，是每个 Java 程序员应该每天都会用到的，它就是 ArrayList

先看一下它的继承和实现关系

• 它继承了 AbstractList ，实现了 List ====> 它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能
• 它实现了RandomAccess 接口 ====> 实现这个这个接口的 List 集合是支持快速随机访问
• 它实现 java.io.Serializable 接口 ====> ArrayList 支持序列化，能通过序列化去传输
• 并且要注意，在单线程中使用它，在多线程使用 Vector(少) 或者 CopyOnWriteArrayList(多)**，尽量还是使用后者较多，前者主要是基于 **synchronized 关键字，后者是基于 ReentrantLock 操作的

它与 Java 自带的普通数组最大的区别就是：它是动态的

这里主要基于源码分析一下动态扩容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public void ensureCapacity(int minCapacity) {
    if (minCapacity > this.elementData.length && (this.elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA || minCapacity > 10)) {
        ++this.modCount;
        this.grow(minCapacity);
    }

}

private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));
}

private Object[] grow() {
    return this.grow(this.size + 1);
}

private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10, minCapacity);
        } else if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            return minCapacity;
        }
    } else {
        return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
    }
}

注：

• 对于变长数据结构，当结构中没有空余空间可供使用时，就需要进行扩容。在 ArrayList 中，当空间用完，其会按照原数组空间的1.5倍进行扩容。