数据结构之数组和Java中数组的使用

2021年7月13日15:12:36

既然之前说过，无论对Android开发还是对其他程序员，数据结构都算是一门必修课，那么从今天起，就算是新开了一个文章系列吧，关于数据结构的系列。我会不定期的更新这个系列，因为数据结构需要严谨一些，本身这是个自我学习的过程，所以文章应该会出的比较慢，很难做到高产。

由于数据结构本身就是有一定难度的内容，所以咱就从最简单的入手——数组。顺便说一下，无论是数据结构还是算法，我都会用Java语言来给出相应的代码，主要是Java语法糖不多，在学习数据结构和算法的时候，还是应该着眼于其“思维模式”，而要摒弃语言内的特殊实现和用法。所以“又臭又长”的 Java语言在这个时候绝对比Kotlin要合适的多。至于我为什么不用C/C++？哈哈，已经忘了好多年了。

什么是数组？

数组是一种线性的数据结构，它是同一种类型的数据元素的有序集合，占用了一块固定大小的连续的内存空间。也许我这里对于数组的描述并不够正式（其实好像也没有什么所谓官方描述），但已经把数组的最重要的几个特点涵盖了。下面我会比较细致的对数组的每个特点进行描述。

先说一下线性数据结构，它算是数据结构的两大基本类型之一，数据结构总体上可以分为线性数据结构和非线性数据结构。所谓线性，顾名思义它内部的数据元素是线性排列的，也就是说，一条“线”把这些元素串联在了一起。其内部的元素，彼此之间只有比较单纯的线性关系，也就是只能有前后的概念，比如元素b，它可以有前面的元素a也可以有后面的元素c。总而言之，且前后最多只能有一个元素，整个结构只有一个头元素和尾元素，是一种内部元素之间关系比较简单的数据结构。

数组内存放的数据元素是同一种类型

比如你声明了一个int型数组，那么就只能存放int型元素。如果你想往里面存放long型，那编译器直接就报错了。当然了，如果你想存放byte或者short这种比int范围更小、又被int完全涵盖了的类型，那么也是可以的。只不过存进去的实际上是经过类型转换后的int数据，而非原先的byte或short。简而言之，你声明数组的时候用的是什么类型，就只能往里存放什么类型的数据。

数组的有序性

在数组内的元素，是有序排列的。每个元素都有一个唯一的索引（或者说是下标），通过这个索引值，就可以很迅速的从数组中获取相应下标的具体数据了。在C/C++/Java里，数组的索引是从0开始的，也就是数组的第一个元素其下标是0，而不是更符合人脑思维的1。当然也有从1开始的语言（如Pascal等），但那不在咱们今天讨论的范围内。

数组的长度是固定的

数组的长度，也就是数组种所存储元素的数量。一个数组在初始化结束后，它的长度也就固定了。比如你初始化了一个长度为10的数组，那么这个数组对象就一定有且只有10个元素，想往里存放11个或者更多元素？那样只会得到一个异常错误并导致程序崩溃，你只能重新初始化一个合适的新数组。

数组在内存中是连续存储的

这里我觉得用一张图来进行说明会更容易理解：

数组在内存中是连续排列的

我们知道，计算机的内存在系统中实际上是有地址的，这个地址可以理解为一种编号，比如4GB的内存，其地址从0开始的话（实际上我们的电脑内存地址通常不是从0开始的），每个内存地址都代表了一块基本大小的内存空间，比如0x00000000就表示了最开始的1个字节大小的内存空间，0x00000001则表示紧随在后的下一个字节的内存。

而一个数组所占用的内存，则是一段连续的内存。比如一个存放了5个int元素的数组，假设它第一个元素所在内存地址是10000（这里我们用10进制方便理解），那么之后的10004、10008、10012、10016这4个内存地址所映射的内存空间，就存放着其后面4个元素。

Java数组的使用

在Java里，由于List（尤其是ArrayList）的存在，导致很多开发者习惯了使用List集合替代数组。这样做在实现上当然是没有问题的，而且List能动态扩容的特性也避免了数组不能扩容的缺点。但是作为一个对技术有一定追求的程序员，是有必要了解数组，并且知道哪些场景下数组比List集合更适用。

Java数组的使用场景

在一些比较追求性能的场景下，数组是明显优于List的。尤其是存储基本类型数据的时候，由于List的元素必须是对象，它就不能直接存储int、float等数据，而是需要经过装箱生成Integer、Float对象，而数组则可以直接进行基本数据类型的存储，这样一来在内存的使用和生成对象等方面都会产生相应的性能差距，在非常考验性能的场景，这种差距是能达到数量级差距的，不能轻易忽视。

所以一般来说，数组的使用场景是这样的：

元素的数量比较确定，你可以在使用的时候直接确定它的长度是最好的。
对性能比较敏感，希望能尽量节约内存，还要有很快的遍历和按照索引获取元素的性能。

Java数组的声明和初始化

在Java中比较常见的数组声明方式有两种：

int[] testArray;
int testArray[];

其中我更推荐前面那种声明，因为它可以很好的体现出，testArray是一个int[]类型的对象——是的，你没有看错，即使是数组，即使是基本数据类型的数组，在Java里依然是一个对象。而后面的那种声明方式，更多人使用可能仅仅是习惯了——因为在C/C++里数组一般都是这样声明的，在Java里也可以这样，但相对来说就不太推荐了，因为并不能很好的体现testArrays的类型嘛。

而数组的常见初始方式也有两种：

静态初始化

int[] testArray = new int[] {1, 2, 3, 4, 5};

动态初始化

int[] testArray = new int[5];

所谓的静态初始化，是在初始化过程中手动的为数组每个元素都进行了赋值，而动态初始化则只定义了数组的类型和长度，每个元素的数值并没有进行赋值。当然实际上动态初始化的数组每个元素都是有初始默认值的，比如int数组的元素默认值就是0，其他类型的数组元素默认值则根据元素类型和JVM的行为来确定。

另外，静态初始化那里，可以省略一些代码：

int[] testArray = {1, 2, 3, 4, 5};

虽然Java不是一个能耍花活儿的语言，但是编译器还是可以从这样的初始化里确认数组的长度和每个元素的初始值的。而类型、初始值、长度确定后，一个数组的初始化也就完成了。

二维数组和多维数组是怎么回事？

所谓多维数组，就是指数组内的元素依然是数组这种情况，一层套一层有种套娃的感觉，一直剥到最后一层，才能得到相应的数据。其实理解多维数组也不算很难，一般来说，从一维数组开始往上扩展到二维数组，再扩展到三维数组，就比较容易理解了。

二维数组：

int[][] twoDimensionalArray = new int[2][3];

这样twoDimensionalArray就是一个二维数组了，你可以这样理解，它是一个一维数组，一共有2个元素，然后每个元素又是一个一维数组，各自有3个元素。可以把它理解成这也的一个矩阵：

二维数组就像矩阵一样

其中，矩阵的第一行，就对应着数组的twoDimensionalArray[0][0]、twoDimensionalArray[0][1]和twoDimensionalArray[0][2]这3个值，第二行同理。而对于多维数组，也是一样的道理。

Java数组的遍历

由于数组的长度是固定的，而且又是一片连续的内存空间，所以使用下标来依次获取数组的每个元素从而实现遍历，是一种性能很快的方式：

int length = testArray.length;
for (int i = 0; i < length; i++) {
    int temp = testArray[i]; // 这里就获取到了数组中的第i个元素
}

当然在Java里数组也是支持for-each遍历的：

for (int temp : testArray) {
    // 这里的temp就是数组从开始的元素一直到最后一个元素的值
}

对于数组来说，想要获取其中任何一个位置的元素，用testArray[index]的方式即可，这个操作的时间复杂度我们通常认为是O(1)，即不管数组长度有多长，随机获取其中任何位置的元素所花费的时间都是一致的。

关于数组的一些有趣的问题

数组虽然是一个比较简单的数据结构，其性能表现却是非常出色的，而它的设计又有一些很有意思的地方，值得单独拿出来讲一讲。

数组元素的下标（索引）为什么是从0开始而不是从1开始的？

这个问题，相信是几乎100%开始学编程的人都会有的一个疑问。是啊，从符合我们人类思维的角度来看，数组的第一个元素，下标不就应该是1嘛，为什么搞了个从0开始呢？这完全不符合现实生活啊。其实啊，这里数组的设计还是有其科学道理的，也有一定的年代局限性。

首先，在理解数组下标的时候，不要把它单纯理解成一个索引（index），而是应该理解成偏移量（offset），也就是说，下标为2的元素，这个2代表的是该元素与数组首个元素的偏移量。这样一来，是不是就容易理解多了？那么首元素作为数组中排在最前面的，它与自身的偏移量自然是0，所以下标自然就是0了。

那么又来了一个问题，为什么数组取值要用偏移量，而不是干脆用元素在数组里的位置（从1开始）呢？咱们就从C语言开始吧，C语言是1970年左右诞生的，那个时代的计算机硬件的性能之差相信大家都有所耳闻，有多差呢，今天随便一部智能手机CPU拿出1%的运算能力也足以碾压当时性能最强的计算机了。落后的硬件带来的是当年的程序员大牛们无论是设计语言还是编程，都会想尽一切办法提升性能。比如数组如果下标使用偏移量，那么在获取数组中任意位置的元素时，只需要从内存中读取数组的首内存地址再加上偏移量就可以了，如果数组的下标不使用偏移量而从1开始标，那么从内存中读取，就需要数组的首内存地址+偏移量-1，实际上就多了一步减法操作。这个对于性能的影响有多大呢？我也不是很清楚，但一定是有性能影响的这一点毫无疑问。

另外，在C语言最早期的时候（据说那时候C语言的名字叫做new B language，哈哈），指针和数组是等价的，那么在指针中考虑偏移量这个概念，也就是水到渠成了（当然现在肯定不等价）。对于熟悉C语言的人来说，array[5] == *(array + 5)这样的东西一定不陌生吧？

数组在内存中为什么是连续的？

啊？这？人家就是这么设计的嘛。因为只有这样，才能方便的通过首地址和偏移量来高效率获取到任意位置的元素，这就是数组最基本的特性了。试想一下，如果数组在内存中并不连续，那么显然，即使你有首地址和偏移量，也不可能直接定位到对应偏移量的内存地址，那这个所谓的”数组“的数据结构其实已经没有什么实际价值了。

为什么数组的长度是固定的？

在初始化的时候我们知道数组的长度就已经固定了，因为如果不指明大小的话，就无法顺利的开辟内存。要实现常数时间的随机访问，数组的元素必须线性连续的分布在一段内存空间中。而如果想要实现不固定长度的动态数组，那么数组就需要有额外的代码了，需要实现动态的重新分配内存和旧元素的复制，无论如何都必然带来额外的性能损失。

数组必须要初始化才能用吗？

这个问题我倒是觉得不太容易描述。简单来说，你声明的数组，只要它不是null，其实就可以用了。那么如何让它不是null呢？初始化自然可以，但是这样行不行呢？

int[] arrayA = new int[5];
int[] arrayB = arrayA;
int temp = arrayB[0];

这段代码，凭直觉，你认为它能顺利运行吗？我想大多数人应该能看出来，运行应该没问题！对于arrayB我们没有进行初始化操作，但是arrayA是初始化过了的。其实这已经不算是数组的问题了，这就是一个Java的引用变量和对象的问题嘛！实际上声明那里我们只是获得了2个int[]类型的变量，而等号后面的初始化才是真正在Java堆内存里实例化了一个数组对象。而把arrayA指向的对象地址也赋给arrayB以后，arrayB这个引用也就指向了堆内存里刚才实例化的那个数组，所以也就不是null了。