资讯专栏INFORMATION COLUMN

上云采购季！| 爆款云服务器低至4.6元/月，首单享0.9折

免费试用
首页/文章专栏/数组

数组

Yuqi / 2123人阅读

摘要：二数组扩容及拷贝数组的扩容数组是根据固定容量创建的，在必要的时候我们需要对数组进行扩容初始长度为下面决定需要对数组进行扩容对原数组进行内容拷贝在对数组进行拷贝时除了利用循环遍历数组元素进行拷贝外，推荐使用更高效的方法。

PS：如果觉得文章有什么地方写错了，哪里写得不好，或者有什么建议，欢迎指点。
一、认识数组

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

1. 概念的理解 线性表:

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

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

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

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

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

2. 高效的随机访问

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

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

// 一维数组 arr[n]：
arr[i]_address = base_address + i * data_type_size

// 二维数组 arr[m][n]：
address = base_address + (i * n + j) * 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() 方法进行操作的。

欢迎您的点赞、收藏和评论！
（完）

专线服务 服务器托管 java数组数组相加 多维数组转一维数组 数组java二维数组 二维数组转换一维数组

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77472.html

相关文章

  • C语言进阶：指针的进阶

    摘要：本章节在此基础上，对语言阶段指针进行更深层次的研究。数组指针的类型由数组类型决定，先找出数组的类型去掉名就是类型。相当于数组指针所指向数组的数组名。数组指针指向整个数组，将其看作二维数组并解引用得到一行的首元素，从而遍历访问。 ...

    浠ラ箍 评论0 收藏0

  • 犀牛书——CHAP7：数组

    摘要：数组有以下特点无类型数组元素可以是任意元素。因此，当小于数组最大索引时，大于的数组元素会被删除。原数组不会改变将数组元素转换为字符串并连接在一起。默认将数组元素用，连接，传入的参数即为连接符。 showImg(https://box.worktile.com/view/fcfcdf2c99b14edfb6768085955ae253?pid=4b0845b09ca94218a955f8...

    Alfred 评论0 收藏0

  • JS基础06「数组」

    摘要：为了维持此规则不变化，数组有两个特殊的行为。运算符对数组返回并且对于除了函数以外的所有对象都是如此。解决方案是检查对象的类属性，对数组而言该属 数组 数组是值的有序集合。每个值叫做一个元素，而每个元素在数组中有一个位置，以数字表示，称为索引。 JavaScript 数组是无类型的，数组元素可以是任意类型，并且同一个数组中的不同元素也可能有不同的类型。数组的元素甚至也可能是对象或其他数组...

    forrest23 评论0 收藏0

  • JavaScript数组

    摘要：与稀疏数组对立的为密集数组，密集数组的索引会被持续的创建，并且其元素的数量等于其长度。创建一个长度为的数组，并初始化了个元素使用构造函数创建数组对象的时候，关键字是可以省略的。另外使用和删除元素是影响数组的长度的。 说明：本文只总结了JavaScript数组在web端的行为，不包括NodeJs端的行为。本文不涉及类型化数组（TypedArray）的讨论、总结。 一、什么是数组 数组的定...

    HtmlCssJs 评论0 收藏0

  • java知识体系梳理-->数组

    摘要：知识体系梳理流程图一维数组数组概述数组是指一组数据的集合，数组中的每个数据被称作元素。定义打印数组元素方法按照给定的格式打印题目分析通过观察发现，要实现按照指定格式，打印数组元素操作。按照这种方式，数组循环多圈以后，就完成了数组元素的排序。 知识体系梳理流程图 showImg(https://segmentfault.com/img/bVXwAi?w=902&h=652); 一维数组 ...

    james 评论0 收藏0

  • 《javascript高级程序设计》笔记_数组 稀疏数组 伪数组

    摘要：数组是数据的有序列表，与其他语言不同的是，数组的每一项可以保存任何类型的数据。如下的代码创建的就是一个密集数组稀疏数组与密集数组相反，并不强制要求数组元素是紧密相连的，即允许间隙的存在。 数组是数据的有序列表，与其他语言不同的是，ECMAScript 数组的每一项可以保存任何类型的数据。也就是说，可以用数组的第一个位置来保存字符串，用第二位置来保存数值，用第三个位置来保存对象， 以此类...

    pepperwang 评论0 收藏0

发表评论

登陆后可评论

0条评论

Yuqi

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<