数组是一种线性表

顾名思义，数组就是数据组合存放在一起，是一种存储数据容器。其一般定义： 数组是具有相同数据类型元素的有序集合。

从定义可知

• 所有元素必须是相同数据类型
  由此可推导数组也可认为是一种数据类型，且它的类型由其元素的数据类型决定。其中，数据类型刻画操作对象的特性，是一个值的集合和该值集上的一组操作的总称，即 数据类型 = 数据值域 + 数据操作。
• 数组中元素是有序的
  有序指数据元素之间的关系，即除首尾元素，其他元素都有且只有一个前驱元素、后继元素。

​元素有序说明数组是一种线性表。在逻辑内存上，数组不管有多大，各个元素都是连续的。那么很自然地认为，在物理存储层面可以使用顺序存储结构存储数组的元素和元素之间的关系，但又由于Windows操作系统的物理内存按照4KB分页，只能保证数组在4KB内绝对是连续的，超过4KB则无法确定。

​ 以上内容站在抽象数据类型（Abstract Data Type，ADT）的角度描述数组。实际上各类编程语言都把数组设为固有类型，有其具体实现方式。本文以下内容以java语言为例，介绍java数组的各类特性。

Java数组

​ 在java中，数组用来存储固定数量的同类型元素，且用一个标识符名称把对象序列或基本数据类型序列封装到一起。数组也是一种对象，除继承Object类的相关属性外，数组对象有一个固有成员length,表示数组的最大容量，注意不是已有数组大小。

 int[] a = new int[10];
 a[1] = 1;
 System.out.println(a.length); //输出10，不是1.

​ 数组内存模型同一般java对象基本一致，在栈空间中存储数组的引用，在堆空间中存储数组对象，且栈中引用指向堆中对象。但由于数组存储多个元素，其存储模型稍有不同。

对于一般java对象，栈空间栈帧中对象引用指向堆内存中的对象地址。如下图。

图1 java一般对象存储模型 当数组中存储基本数据类型时，栈空间中的数组引用指向堆空间中的第一个数组元素地址，且堆空间中直接存储的数组元素值。如下图。 图2 基本数据类型数组的存储模型

当数组中存储其他对象时，栈空间中的数组引用也指向堆空间中的第一个数组元素地址，但堆空间中存储的是对象的引用。如下图。

图3 对象数组的存储模型

特点

• 可以存储基本数据类型
  其他集合只能存储对象，不能存储基本数据类型。但自动拆箱、装箱技术的出现，使其他集合也可以存储基本数据类型。

• 数组一旦声明，其大小不能发生改变
  静态数组称呼的由来。
  该特点导致在实际编程中基本不使用数组，而是其他动态容器（ArrayList等）

• 数组元素逻辑删除
  数组初始化后，数组元素只能在逻辑层面删除。在物理层面，其值已写入内存，只能被覆盖，不能被物理删除。在java体系中，若数组存储对象时，数组元素被逻辑删除之后，物理地址上的值依旧存在，此时GC无法将其回收。因此，此种情况下删除数组元素对象的同时，可将其置空，使其被GC回收。

• 使用整型索引随机访问元素,下标从0开始
  随机访问的实现基于数组在内存中的连续存储。数组名指向数组元素的起始位置地址，索引下标是相对于起始地址的偏移量，操作系统在知道起始地址和偏移量之后，可立马获取对应地址上的内容，即所谓的随机访问。这同时也导致数组是存取效率最高的数据容器。但为保证数组各个元素内存仍旧连续，因此在插入和删除时需要移动元素（实质是重新赋值，全部赋值动作整体来看是一种移动效果），其操作效率比较耗时。

  数组内存层面的最基本操作是按照索引存取元素、获取数组长度。使用层面的基本操作基于内存上的基本操作，包括增删改查、排序等

数组声明

java数组定义多采用如下格式

int[] arr;

以上语句只是定义了一个数组引用，即只在栈中分配一个栈帧存储该引用，并未指向堆空间中的数组对象。之所以允许未创建数组对象就可定义一个数组引用，是因为java支持将一个数组赋值给另外一个数组。

数组初始化

定义数组之后，要进行数组初始化，其实质是对数组引用赋值（将数组引用指向堆空间中的具体地址）。根据数组引用赋值的时机不同，可分为静态方式和动态方式。

• 静态初始化指在数组声明的同时，直接给数组引用赋值

  //右侧中括号不能写长度，有JVM自动计算
  int[] arr1 = int[]{1,2,3};
  

  //上一种方式的省略方式。
  int[] arr2 = {1,2,3};
  //省略方式不允许先声明后赋值，只能声明同时直接赋值。
  int[] arr3;
  arr3 = {} //编译出错
  

• 动态初始化指数组声明和数组引用赋值分开。根据数组定义方式的不同，又分为两种。

  //这种数组定义方式，只能用数组引用赋值方式。
  int[] arr1;
  ... //其他代码 
  //其他代码段中存在同类型的数组arr2
  arr1 = arr2 
  

  //这种数组定义方式，可有数组引用赋值、数组元素下标赋值 两种赋值方式
  int[] arr1 = int[10];
  ...//其他代码段
  //数组引用赋值
  //其他代码段中存在同类型的数组arr2
  arr1 = arr2 
      
  //数组元素赋值
  arr1[1] = 1;
  arr1[2] = 2;
  

二维数组

二维数组实质上是一维数组的元素存储数组地址，这个地址指向其他一维数组。
定义方式如下

T[][] arr = new T[a][b]

其中，a表示一维数组的数量，b表示每个一维数组元素的个数。

Arrays工具类

该类在java.util.Arrays下，提供对数组的排序、比较、复制等功能。

延伸

• 数组被赋值之后，在内存层面，元素已被写入相应地址的内存空间，无法被删除，只能通过覆盖修改其值。因此当数组的元素是对象时，当逻辑删除元素之后，可手动将对应位置的元素置空，使其被GC回收。

      //在不是泛型的情况下，不需要手动置空。
      //在泛型情况下，由于泛型中装载的是对象，当删除数组元素时，
      //尾部的size指针左移一位后，指向的是一个无用的对象【loitering objects】。
      //但这个无用的对象不代表内存泄露，因为数组只要再被使用，这个对象就可能被覆盖。
      //不过，若数组不再被使用，这个对象就不会被释放，无法被GC。
      //因此，手动置空可让GC回收这个对象，以提高性能。
      //置空与否不影响删除逻辑。
      data[size] = null;
  

• 在leetcode中，数组涉及的解体方法有二分法、双指针法、滑动窗口法、模拟行为等。

• java泛型不可以装入基本数据类型（四类八种），基本数据类型需要装箱之后使用泛型。与泛型机制相关。

  List<Integer> foo = new ArrayList<Integer>(); //正确
  List<int> bar = new ArrayList<int>();//错误
  

• O(n)是渐进时间复杂度，是描述n趋近于无穷的情况.对于

  T1 = 2000*N + 1  O(n)
  
  T2=1* n * n + 1 O(n2)
  

  ​ 当n较小时，T1 > T2 .当n无穷大时，T2 > T1。渐进时间复杂度讨论的时n无穷大的情况，因此认为 T2的时间复杂度高于T1，即认为T1的性能更好，优先选择T1对应的算法。但是这种曲线有交叉 [最高次幂的系数有影响] 的情况，可以根据实际数量情况，灵活选择不同算法。当数据量小时选T2（此时最高次幂的系数对运算时间影响较大，2000>1）,数据量大时（此时元操作的阶数对运算时间影响较大）选T1.

• 均摊复杂度的场景 若干次基本操作后发生一次复杂操作，那么复杂操作就可以被均摊

• 在程序设计中，基本数据类型和引用数据类型的内存存储方式是不同的，引用类型，通过new关键字创建，故引用对象会存放在堆区内存中，对于特别小的基本数据类型，往往效率不高，因此对于基本数据类型，不用new来创建，而是采取了和C/C++相同的方法，直接赋值存储，放置在内存的栈区内存，更加高效。

参考资料

• java编程思想
• 数据结构（严蔚敏版）
• 二维数组
• 数组总结
• 数组算法题涉及的方法