转载

数组

数组

一、认识数组

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

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 容器是基于数组实现的,那么二者相比各有什么优点和适用场景呢?

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

二、数组扩容及拷贝

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);

参数说明:

  1. src:要被复制的数组,
  2. srcPos:被复制的数组开始复制的下标,
  3. dest:目标数组,也就是要把数据放进来的数组,
  4. destPos:从目标数组第几个下标开始放入数据,
  5. 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
正文到此结束
Loading...