Array数组的概念和用法

这篇文章主要介绍"Array数组的概念和用法"，在日常操作中，相信很多人在Array数组的概念和用法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"Array数组的概念和用法"的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

数据结构课程学习笔记。

数组概念

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据, 并且不支持动态扩容。

• 线性表

  线性表就是数据排成一条线一样的数据结构，每个线性表最多只有前后两个方向，数组，链表丶队列丶栈等都是线性表数据结构。

• 非线性表

  非线性表就是数据不规则，与线性表是相对立的，比如二叉树丶堆丶等，在非线性表中，数据之间并不是简单的前后关系。

数组随机访问

• 公式

  address[i] = base_address + i * data_type_size

  
  

  address[i] : 下标 i 的地址值。

  base_address： 数组的首地址。

  data_type_size： 数组中每个元素的大小，也就是数据类型大小(字节)，例如int是4个字节。

数组的增加和删除

数组 (Array) 在增删查这三个动作中，查询是高效的，但是增和删是低效的，查询高效是因为数组支持随机访问，时间复杂度是 O(1) ,这里就不多赘述了，但是在增加和删除的动作中，因为会涉及数据搬移，所以时间复杂度是 O(n) ，下面来详细讲解。

• 低效的"插入"和"删除"

     int[] info = new int[6];

  
  

  插入

  数组 info 是一个一维数组，其内容是 33,44,66,77,88 现在需要在下标 2 的位置插入 55 ，将其变成33 44 55 66 77 88的数组，这其中涉及将下标 2 到下标 4 的之间进行数据进行搬移，完成后在下标 2 的位置插入 55 , 其复杂度是 O(n)， 但如果是在最后进行插入的话其复杂度是 O(1)。

  删除

  还拿数组 info 来举例，数组删除前其内容是 33,44,00,55,66,77 现在进行删除操作，删除下标为 2 内容，这其中涉及将下标 3 到 5 的内容向前搬移，其操作的时间复杂度是 O(n) ，如果是是删除最后一位且后面没有内容，则其时间复杂度是O(1) 。

  因插入和删除操作会涉及到数据搬移,所以说他是低效的。

  CPU缓存**

  Cpu缓存的最小单位是Cpu缓存行，一个缓存行大小通常是64字节(取决于CPU)，试想一下你正在遍历一个长度为 16 的 long 数组 data[16]，原始数据自然存在于主内存中，访问过程描述如下：

  1：访问 data[0]，CPU core 尝试访问 CPU Cache，未命中。

  2：尝试访问主内存，操作系统一次访问的单位是一个 Cache Line 的大小 - 64 字节，这意味着：既从主内存中获取3：到了 data[0] 的值，同时将 data[0] ~ data[7] 加入到了 CPU Cache 之中，

  4：访问 data[1]~data[7]，CPU core 尝试访问 CPU Cache，命中直接返回。

  5：访问 data[8]，CPU core 尝试访问 CPU Cache，未命中, 尝试访问主存，重复步骤2。

  测试数组和Cpu缓存行

  因Cpu缓存最小单位是缓存行(64字节)，我么来测试一下二维数组的横向遍历和纵向遍历的具体时间和性能。

  代码

  package com.com.array;/** * @Auther: lantao * @Date: 2019-06-24 15:52 * @Company: 随行付支付有限公司 * @maill: lan_tao@suixingpay.com * @Description: TODO */public class ArrayTest {    static long[][] arr;    public static void main(String[] args) {        long sum = 0L;        arr = new long[1024 * 1024][10];        // 横向遍历        long l = System.currentTimeMillis();        for (int i = 0; i < 1024 * 1024; i++) {            for (int j = 0; j < 10; j++) {                sum += arr[i][j];            }        }        System.out.println("Loop Time 横向遍历：" + (System.currentTimeMillis() - l) + "ms");        long l1 = System.currentTimeMillis();        // 纵向遍历        for (int i = 0; i < 10; i++) {            for (int j = 0; j < 1024 * 1024; j++) {                sum += arr[j][i];            }        }        System.out.println("Loop Time 纵向遍历：" + (System.currentTimeMillis() - l) + "ms");    }}

• 结果：Loop Time 横向遍历：14msLoop Time 纵向遍历：83ms

• 总结： 因横向遍历遍历的是行，然后在循环行的每一列，Cpu缓存会缓存64字节大小的缓存行，所以可以减少cpu和主存之间的交互，直接和高速缓存交互，提升性能，纵向遍历因每次循环都是不同的行，所以使缓存行没有作用。

到此，关于"Array数组的概念和用法"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！