写文章

程序员的进阶课-架构师之路 - 数组

2020-03-30 15:02:40

961 | 1 | 1

从这一节开始,我们就要正式进去数据结构的世界了,那么第一个是什么呢,就是我们的数组。

在我想写数组的时候,我的第一印象是去看它的源码,很可惜,数组的实现太特殊了,找了很久,我没有找到它的源码,带着这样的思考,我就开始了Java中数组的挖掘。Wow,真香!

一、Java中数组的介绍


数组是一种最简单的复合数据类型,它是有序数据的集合,数组中的每个元素具有相同的数据类型,可以用一个统一的数组名和不同的下标来唯一确定数组中的元素。根据数组的维度,可以将其分为一维数组、二维数组和多维数组等。一定要注意,数组只能存放同一种数据类型(Object类型数组除外)。

二、数组是一个引用类型吗?


先给答案,是的,没有任何疑问。

注意,数组也是一种数据类型,它本身是一种引用类型。

数组是一种大小固定的数据结构,对线性表的所有操作都可以通过数组来实现。虽然数组一旦创建之后,它的大小就无法改变了,但是当数组不能再存储线性表中的新元素时,我们可以创建一个新的大的数组来替换当前数组。这样就可以使用数组实现动态的数据结构。

如何验证?


定义一个数组,发现它拥有Object类的所有方法。

根据这个例子,其实大家已经看出来了,数组拥有超类Object的所有方法,说明他也是一个类。并且他拥有自己的clone()方法和length属性。

三、如何了解数组的底层实现


既然数组拥有Object的所有方法,那我们是否能查看一下数组的源码,来了解一下数组的实现呢?

可惜,数组太特殊了,他的实现是虚拟机编译的时候动态生成的,所以我们无法直接查看源码,只能通过查看编译后的class的字节码一探究竟。

JVM 中数组对象是一种特殊的对象,虚拟机从数组的元数据中无法确认数组的大小,它的Object Header 比普通对象多了一个word 来存储数组的长度,length 会编译成对应的字节码读取这个field 就可以了。

我分别定义基本数据类型和引用类型来查看一下最终生成的字节码有何区别。

public void test08(){
Object[] o = new String[11];
o[0]="1aaa";
int i=o.length;
Integer[] a=new Integer[11];
a[0]=100;
int j=a.length;
int[] b=new int[11];
b[0]=100;
int k=b.length;
}


对应的字节码为:

0 bipush 11
2 anewarray #12 <java/lang/String> //anewarray代表对象数组
5 astore_1
6 aload_1
7 iconst_0
8 ldc #25 <1aaa>
10 aastore
11 aload_1
12 arraylength //arraylength代表长度
13 istore_2
14 bipush 11
16 anewarray #26 <java/lang/Integer> //anewarray代表包装类数组
19 astore_3
20 aload_3
21 iconst_0
22 bipush 100
24 invokestatic #27 <java/lang/Integer.valueOf>
27 aastore
28 aload_3
29 arraylength
30 istore 4
32 bipush 11
34 newarray 10 (int) //newarray代表基本数组类型数组
36 astore 5
38 aload 5
40 iconst_0
41 bipush 100
43 iastore
44 aload 5
46 arraylength
47 istore 6
49 return


注意:定义并初始化一个数组后,在内存中分配了两个空间,一个用于存放数组的引用变量,另一个用于存放数组本身。



进行程序开发时,要深入底层的运行机制。

看待一个数组时,一定要把数组看成两个部分:一部分是数组引用,也就是在代码中定义的数组引用变量;还有一部分是实际的数组对象,这部分是在对内存里运行的,通常无法直接访问它,只能通过数组引用变量来访问。



四、Array 的 length 域相关


在很多的资料中都写了,Array中有类似public final int length的成员变量。但是在《Java Language Specifications》10.1. Array Types中明确写了,length不是类型的一部分;

An array's length is not part of its type.

private static void test06() {
String[] s = new String[2];
System.out.println(s.length);
System.out.println(s.getClass().getDeclaredFields().length); try {
System.out.println(s.getClass().getDeclaredField("length"));
} catch (NoSuchFieldException e) {
System.out.println(e.toString());
}
}
打印:20java.lang.NoSuchFieldException: length

可以看到length并不是Array的成员变量。

五、Java语言规范关于Array的定义


数组在Java里是一种特殊类型,有别于普通的“类的实例”的对象。
10.1. Array Types
10.8. Class Objects for Arrays

Every array has an associated Class object, shared with all other arrays with the same component type.Although an array type is not a class, the Class object of every array acts as if:

1、The direct superclass of every array type is Object.
2、Every array type implements the interfaces Cloneable and java.io.Serializable.


数组类型是由JVM从元素类型合成出来的。
10.7. Array Members

The members of an array type are all of the following:

1、The public final field length, which contains the number of components of the array. length may be positive or zero.


从Java语言到Class文件,Java源码编译器会识别出对数组类型的length字段的访问,并生成对应的字节码。
以OpenJDK8的javac为例:
jdk8u/jdk8u/langtools: 84eb51777733 src/share/classes/com/sun/tools/javac/jvm/Gen.java

base.load();
if (sym == syms.lengthVar) {
code.emitop0(arraylength);
result = items.makeStackItem(syms.intType);
}


六、数据应用场景

这种数据结构使用一段连续的空间来存贮元素,所以可以直接通过索引来获取到某个元素,而且可以通过对元素的内容进行排序,然后使用二分法查找,从而提供查找效率。其适合的场合主要是:

1、不会频繁增删元素的场合,因为增删元素都牵涉到元素空间的重新分配,频繁的内存分配操作会大幅降低操作效率。但添加操作时,可以通过预分配足够的空间来优化添加时的效率。


2、属于随机迭代器,可以随机访问任意元素。对于已排序的元素查找起来效率较高。

七、数组总结

在看数组的时候,因为class是动态创建的,所以看了很久,但是根据数组的特性,基本可以认为数组的域和方法,类似于:

class A<T> implements Cloneable, java.io.Serializable {  public final int length = X;  
public T[] clone() { try { return (T[]) super.clone();
} catch (CloneNotSupportedException e) { throw new InternalError(e.getMessage());
}
}
}


数组可以是一维数组、二维数组或多维数组。

数值数组元素的默认值为 0,而引用元素的默认值为 null。

交错数组是数组的数组,因此,它的元素是引用类型,初始化为 null。交错数组元素的维度和大小可以不同。

数组的索引从 0 开始,如果数组有 n 个元素,那么数组的索引是从 0 到(n-1)。

数组元素可以是任何类型,包括数组类型。

数组类型是从抽象基类 Array 派生的引用类型。


课程扩展阅读:https://www.roncoo.com/view/1160515822987776001


1

收藏
分享
全部评论1

156****8284 2020-04-19 02:06:43

1
没有更多了