转载

数组

一、认识数组

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

1. 概念的理解

线性表:

顾名思义，线性表就是数据排列成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向，数组，链表，栈，队列等都是典型的线性表结构。

与其相对立的，在非线性表中，数据之间并不是简单的前后关系，像树，堆，图等都是典型的非线性表。

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

即计算机分配连续的内存单元来存储数据，相同类型的数据即每个内存单元的大小是相同的。

如声明一个长度为 5 的 int 类型的数组 int[] arr = new int[5] ，计算机给数组分配了一块连续的内存空间，其中内存块的首地址为 base_address = 0xc0000160e0，每个内存单元占 4 个字节：

2. 高效的随机访问

数组的一个特点是可以根据下标随机访问数组元素，其时间复杂度为 O(1)，那么它是如何实现的呢？

计算机分配的内存单元存储数据时，也会为内存单元分配一个地址，然后可以通过地址来访问内存中的数据。由数组的内存空间连续的特性，当需要访问某个元素时，它会通过下面的寻址公式来计算出该元素存储的内存地址：

arr[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小，如在 int 型的数组 arr 中，data_type_size 就为 4 个字节。

这样，便可以很快的根据内存地址来读取数据。

3. 低效的“插入”和“删除”

在数组中，为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效。

例如在 插入操作 中，假设数组的长度为 n，若我们要在数组的第 k 个位置插入一个数据，为了把第 k 个位置腾出来给新的数据，我们需要将第 k ~ n 这部分的元素都顺序地向后挪一位： arr[i] = arr[i-1] 。其时间复杂度为 O(n)。

而在 删除操作 中，若我们要删除数组的第 k 个元素，为了内存的连续性，就需要将第 k ~ n 这部分的元素都顺序地向前挪一位： arr[i] = arr[i+1] 。其时间复杂度为 O(n)。

插入和删除操作的优化

然而在很多我们不需要考虑数组中元素的有序性，数组只被当作一个存储数据的集合的时候，为了避免大规模的数据搬移，我们可以对插入和删除操作做一些优化。例如：

如果要将某个数据插入到第 k 个位置，可以直接将第 k 为的数据搬移到数组元素的末尾，然后将新的元素值直接赋值给第 k 个元素；
如果要将第 k 个元素删除，可以直接将数组的最后一个元素赋值给第 k 个元素，然后删除最后一个元素即可。

这样，其时间复杂度就会降为 O(1) 。

4. 容器与数组的比较

对于数组类型，Java 中的 ArrayList 容器是基于数组实现的，那么二者相比各有什么优点和适用场景呢？

ArrayList 的优势是方便，适合在一般的业务中使用。它将很多数组的操作细节封装起来了，如数据的插入、删除、数组的扩容。ArrayList 无法存储基本类型，比如 int、double，需要封装为 Integer、Double 类，而自动装箱/拆箱的操作会有一定的性能消耗；
相对于容器来说，数组的使用虽然麻烦一点，但它的性能会优于容器，更适合用于底层的开发和追求极致性能的优化。

二、数组扩容及拷贝

1. 数组的扩容

数组是根据固定容量创建的，在必要的时候我们需要对数组 arr 进行扩容：

// 初始长度为 10
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
    arr[i] = i+1;
}
...
// 下面决定需要对数组 arr 进行扩容
int[] newArr = new int[arr.length*2];

// 对原数组进行内容拷贝
for (int i = 0; i < arr.length; i++) {
    newArr[i] = arr[i];
}

arr = newArr;

在对数组进行拷贝时除了利用 for 循环遍历数组元素进行拷贝外，推荐使用更高效的 System.arraycopy() 方法。

2. System.arraycopy() 方法拷贝数组

System.arraycopy() 使用 native 关键字修饰，大大加快程序性能，为 JVM 内部固有方法。它通过手工编写汇编或其他优化方法来进行 Java 数组拷贝，这种方式比起直接在 Java 上进行 for 循环或 clone 是更加高效的。数组越大体现地越明显。

该方法用于从指定源数组中进行拷贝操作，可以指定开始位置，拷贝指定长度的元素到指定目标数组中。其声明如下：

public static native void arraycopy(Object src,  int                  srcPos, Object dest, int destPos, int length);

参数说明：

src：要被复制的数组，
srcPos：被复制的数组开始复制的下标，
dest：目标数组，也就是要把数据放进来的数组，
destPos：从目标数组第几个下标开始放入数据，
length：被复制的数组中拿几个数值放到目标数组中；

例，数组 arr 进行扩容：

// 初始长度为 10
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
    arr[i] = i+1;
}
...
// 下面决定需要对数组 arr 进行扩容
int[] newArr = new int[arr.length*2];
System.arraycopy(arr,0,newArr,0,10); // 对原数组进行内容拷贝
arr = newArr;

绝大部分数组和基于数组实现的容器（ArrayList 等）的扩容都是基于 System.arraycopy() 方法进行操作的。

原文 https://segmentfault.com/a/1190000018773014

正文到此结束