Java数据结构之数组

前言

学习java数据结构的重要性:

有必要去学习数据结构吗?虽然你可能没有特意去看一些数据结构的专业书籍,你仍然可以用java做一份还过得去的工作,不过并不是说你完全没有接触到数据结构,因为java已经在底层帮你做了太多,在你和数据结构打交道的时候,你所做更多的是在调用 API 。当你的代码量累积到一定程度的时候,就会想要去加强数据结构和算法的相关知识了。

打个比方,你可以把java看做是自动档轿车,数据结构呢就是变速箱的工作原理。你完全可以不知道变速箱怎样工作,就把自动档的车子开上路,而且未必就比懂得的人慢。写程序这件事,和开车一样,经验可以起到很大作用,但如果你不知道底层是怎么工作的,就永远只能开车,既不会修车,也不能造车。如果你对这两件事都不感兴趣也就罢了,数据结构懂得用就好。但若你此生在编程领域还有点更高的追求,数据结构是绕不开的课题。

编程好比盖高楼,根基没打好早晚有一天会垮掉,而且盖得越高,损失越惨重。数据结构也是通向各种实用算法的基石,所以学习数据结构都是提升内力的事情。

​推荐2️⃣ 本书籍:《Java数据结构和算法》、《数据结构与算法分析_Java语言描述》

pdf

数据结构概述

数据结构(data structure)是计算机中存储、组织数据 (计算机内存或磁盘中的数据)的方式。它不仅存储数据,还支持访问和处理数据的操作。

数据结构包括数组、链表、栈、二叉树、哈希表等等。

算法:对这些结构中的数据进行各种处理。例如,查找一条特殊的数据项或对数据进行排序。

数据结构为算法服务,但是算法可以和数据结构没关系。

DataStructureCompare

上图中的数据结构除了数组之外都可以被认为是抽象数据结构(ADT)。

Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类:

  • 枚举(Enumeration)

该接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里应用很广。 枚举接口定义了一种从数据结构中取回(一次获得一个)连续元素的方式。这种传统接口已被迭代器Iterator取代。参见Enumeration接口

  • 位集合(BitSet)

实现了一组可以单独设置和清除的位或标志。参见Bitset类

  • 向量(Vector)

该类和传统数组非常相似,但是Vector的大小能根据需要动态的变化。和ArrayList相似,但Vector是同步访问的,而且还包含了许多不属于集合框架的传统方法。 使用Vector类最主要的好处就是在创建对象的时候不必给对象指定大小,它的大小会根据需要动态的变化。参见Vector 类

  • 栈(Stack)

是Vector的子类,它实现了一个标准的后进先出(LIFO)的栈。 你可以把栈理解为对象的垂直分布的栈,当你添加一个新元素时,就将新元素放在其他元素的顶部。当你从栈中取元素的时候,就从栈顶取一个元素。换句话说,最后进栈的元素最先被取出。参见Stack 类

  • 字典(Dictionary)

是一个抽象类,它定义了键映射到值的数据结构。作用和Map类相似。 当你想要通过特定的键而不是整数索引来访问数据的时候,这时候应该使用Dictionary。参见Dictionary 类

  • 哈希表(Hashtable)

Hashtable是原始的java.util的一部分, 是一个Dictionary具体的实现 。Java 2 重构的Hashtable实现了Map接口。它和HashMap类很相似,但是它支持同步。参见Hashtable 类

  • 属性(Properties)

继承于 Hashtable,表示一个持久的属性集。属性列表中每个键及其对应值都是一个字符串。参见Properties 类

以上这些类是传统遗留的,在Java2中引入了一种新的框架-集合框架(Collection) ,我们后面再讨论。

插入、查找和删除是大部分数据结构的最基本的三个操作。

线性表是最常用且最简单的一种数据结构,它是n个数据元素的有限序列。

实现线性表的方式一般有两种:

1️⃣ 使用数组存储线性表的元素,即用一组连续的存储单元依次存储线性表的数据元素。

2️⃣ 使用链表存储线性表的元素,即用一组任意的存储单元存储线性表的数据元素(存储单元可以是连续的,也可以是不连续的)。

数组

数组是应用最广泛的数据存储结构。

数组只是相同数据类型的、用同一个标识符名称封装到一起的一个对象序列或基本类型数据序列。即一个数组里只能存储一种数据类型的数据。

一旦数组的初始化完成,数组在内存中所占的空间将被固定下来,因此数组的长度将不可变。即使把某个数组元素清空,但它所占的空间依然被保留,依然属于数组,数组的长度依然不变。

Java的数组既可以存储基本类型的数据,也可以存储引用类型的数据,只要所有的数组元素具有相同的类型即可。

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

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

定义数组

Java 语言支持两种语法格式定义数组:

1
2
type[] arrayName;//① 推荐写法
type arrayName[];//②

对于第①种写法,很容易理解这是定义变量,其中变量名是arrayName,而变量类型是type[]。(如int是基本类型,int[]是引用类型)这里type[]与type类型不同,是一种新类型。[]操作符对于编译器来说是一个标志,它说明正在命名的是数组对象而不是普通的变量。还可以将它放在变量名的后面,而不是类型后面,即第②中写法。

第②种写法,可读性差。看起来好像定义了一个类型为type的变量,而变量名是arrayName[],这与真实含义相去甚远。

数组是一种引用类型的变量,因此使用它定义一个变量时,仅仅表示定义了一个引用变量,这个引用变量还未指向任何有效的内存空间,因此 定义数组时不能指定数组的长度 。由于还没有内存空间来存储数组元素,因此这个数组也不能使用,只有对数组进行初始化后才可以使用。

初始化

Java语言中数组必须先初始化,然后才可以使用。所谓初始化,就是为数组的数组元素分配内存空间,并为每个数组元素赋初始值

数组的初始化有两种方式:

  • 静态初始化:初始化时由程序员显式指定每个数组元素的初始值,由系统决定需要的数组长度。
  • 动态初始化:初始化时程序员只指定数组长度,由系统为数组元素分配初始值。

Java中有两种数据类型:基本类型 和 引用类型。在许多编程语言中(甚至有些面向对象语言,如c++),数组也是基本类型,但在Java中把数组当作对象对待。因此在创建数组时必须使用new操作符。

ps:我们知道创建对象时会为对象分配存储空间,并调用相应的构造器,确保在操作对象之前被恰当的初始化了。从概念上讲,“初始化”与“创建”是彼此独立的。但在Java中,“初始化”和“创建”是捆绑在一起,两者不能分离。

静态初始化

1
arrayName = new type[]{element1, element2 , element3 , element4 ...}

type就是数组元素的数据类型,此处的type必须与定义数组变量时所使用的type相同,也可以是定义数组时所使用的type的子类;并使用花括号把所有的数组元素括起来,多个数组元素之间以英文逗号(,)隔开,定义初始化值的花括号紧跟[]之后。值得指出的是:执行静态初始化时,显式指定的数组元素值的类型必须与new关键字后type类型相同,或者是其子类的实例。

除此之外,静态初始化还有如下简化的语法格式:

1
2
arrayName = {element1, element2 , element3 , element4 ...}
//在这种语法格式中,直接使用花括号来定义一个数组,花括号把所有数组元素括起来形成一个数组。

实际开发过程中,可能更习惯将数组定义和数组初始化同时完成.

1
2
//数组的定义和初始化同时完成,使用简化的静态初始化写法
int[] a = {5, 6 , 7, 9};

动态初始化

动态初始化只指定数组的长度length ,由系统为每个数组元素指定初始值,动态初始化的语法格式

1
arrayName = new type[length];

执行动态初始化时,程序员只需指定数组的长度,即为每个数组元素指定所需的内存空间,系统将负责为这些数组元素分配初始值。

指定初始值时,系统按如下规则分配初始值:

数组元素的类型是基本类型中的整数类型(byte、short、int和long),则数组元素的值是0。

数组元素的类型是基本类型中的浮点类型(float、double),则数组元素的值是0.0。

数组元素的类型是基本类型中的字符类型(char),则数组元素的值是’\u0000’。

数组元素的类型是基本类型中的布尔类型(boolean),则数组元素的值是false。

数组元素的类型是引用类型(类、接口和数组),则数组元素的值是null。

ps:基本类型默认值

basicTypeDefaultValue

⚠️ 注意: 不要静态初始化和动态初始化同时使用,也就是说不要在进行数组初始化时,既指定数组的长度,也为每个数组元素分配初始值。

数组初始化完成后就可以使用数组了,包括为数组元素赋值、访问数组元素值和获取数组长度等。这里再做一下延伸,对比说明基本类型和引用类型的数组初始化。

使用数组

数组最常用的用法就是访问数组元素,包括对数据元素进行赋值和取出数组元素的值。

访问数组元素是通过在数组引用变量后紧跟一个方括号[] ,方括号里是数组元素的索引值。

Java语言的数组索引是从0开始,也就是第一个数组元素的索引值为0,最后一个数组元素索引值为数组长度length减1.

如果访问数组元素时指定的索引值小于0,或者大于数组的长度,编译程序不会出现任何错误,但是运行时出现异常:java.lang.ArrayIndexOutOfBoundsException:N(数组索引越界异常),异常信息后的N就是程序员试图访问的数组索引。

所有数组都提供了一个length 属性,通过这个属性可以访问到数组的长度,一旦获得了数组的长度,就可以通过循环来遍历该数组的每个数组元素。

深入数组

数组是一种引用数据类型,数组引用变量只是一个引用,数组元素和数组变量在内存里是分开存放的。下面深入介绍数组在内存中的运行机制。

内存中的数组

数组变量引用只是一个引用,这个引用变量可以指向任何有效的内存,只有当该引用指向有效内存后,才可通过该数组变量来访问该数组元素。

与所有引用变量相同的是,引用变量是访问真是对象的根本方式。也就是说,如果希望在程序中数组对象本身,则只能通过这个数组的引用变量来访问它。

实际的数组对象被存储在堆(heap)内存中,如果引用该数组对象的数组引用变量时一个局部变量,那么它被存储在栈(stack)内存中。下图是数组在内存中的存储示意图。

MemoryArray

如果要访问上图所示堆内存中的数组元素,则程序中只能通过p[index]的形式实现。也就是说,数组引用变量是访问堆内存中数组元素的根本方式。

PS: 栈内存和堆内存

当一个方法执行时,每个方法都会建立自己的内存栈,在这个方法内定义的变量将会逐个放入这块栈内存 里,随着方法的执行结束,这个方法的内存栈也将自然销毁。因此,所有在方法中定义的局部变量都是放在栈内存中的;

在程序中创建一个对象时,这个对象将被保存到运行时数据区中,以便反复利用(因为对象的创建成本通常较大),这个运行时数据区就是堆内存 。堆内存中的对象不会随方法的结束而销毁,即使方法结束后,这个对象还可能被另一个引用变量所引用(在方法的参数传递时很常见),则这个对象依然不会被销毁。只有当一个对象没有任何引用变量引用它时,系统的垃圾回收器才会在合适的时候回收它。

如果堆内存中数组不再有任何引用变量指向自己,则这个数组将成为垃圾,该数组所占的内存将被系统的垃圾回收机制回收。

只要类型相互兼容,就可以让一个数组变量指向另一个实际的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class ArrayInRam {
public static void main(String[] args) {
//定义并初始化数组,使用静态初始化
int[] a={5,7,20};
//定义并初始化数组,使用动态初始化
int[] b=new int[4];
//输出b数组的长度
System.out.println("b数组的长度为:"+b.length);
//循环输出a数组的长度
for (int i=0,len=a.length;i<len;i++){
System.out.println(a[i]);
}
//循环输出b数组的长度
for(int i=0,len=b.length;i<len;i++){
System.out.println(b[i]);
}
/*
因为a是int[]类型,b也是int[]类型,所以可以a的值赋给b。
也就是让b引用指向a引用指向的数组
*/
b=a;//复制引用
//再次输出b数组的长度
System.out.println("b数组的长度为:"+b.length);
}
}

运行上面代码后,可以看到先输出b数组的长度为4,然后依次输出a数组和b数组的每个数组元素,接着输出b数组的长度为3。

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

ArrayCopyReference

当程序定义并初始化了a、b两个数组后,系统中实际上产生了4块内存区,其中栈内存中有两个引用变量:a和b;堆内存中也有两块内存区,分别用于存储a和b引用所指向的数组本身。

当执行“b=a”时,系统会把a的值赋给b,a和b都是引用类型变量,存储的都是地址。因此把a的值赋给b后,就是让b指向a所指向的地址。此时计算机内存的存储示意图如下所示:

ArrayCopyReference1

由上图可以看出,当执行了“b=a;”之后,堆内存的第一个数组具有了两个引用:a变量和b变量都引用了第一个数组。此时第二个数组失去了引用,变成垃圾,只有等待垃圾回收机制来回收它——但它的长度依然不会改变,直到它彻底消失。

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

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

基本类型数组初始化

对于基本类型数组而言,数组元素的值直接存储在对应的数组元素中,因此,初始化数组时,先为该数组分配内存空间,然后直接将数组元素的值存入对应数组元素中。

下面程序定义了一个int[]类型的数组变量,采用动态初始化的方式初始化了该数组,并显式为每个数组元素赋值,程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
public class TestPrimitiveArray {
public static void main(String[] args) {
//定义一个int[]类型的数组变量
int[] iArr;
//动态初始化数组,数组长度为5
iArr = new int[5];
//采用循环方式为每个数组元素赋值。
for (int i = 0; i < iArr.length; i++) {
iArr[i] = i + 10;
}
}
}

上面代码的执行过程代表了基本类型数组初始化的典型过程,下面将结合示意图详细介绍这段代码的执行过程。

执行第一行代码int[] iArr;时,仅定义一个数组变量,此时内存中的存储示意如图所示:

basicTypeInit1

执行了int[] iArr;代码后,仅在栈内存中定义了一个空引用(就是iArr数组变量),这个引用并未指向任何有效的内存,当然无法指定数组的长度。

当执行iArr = new int[5];动态初始化后,系统将负责为该数组分配内存空间,并分配默认的初始值:所有数组元素都被赋为0,此时内存中的存储示意如图所示:

basicTypeInit2

此时iArr数组的每个数组元素的值都是0,当循环为该数组的每个数组元素依次赋值后,此时每个数组元素的值都变成程序指定的值。显式指定数组元素值后存储示意如图所示:

basicTypeInit3

从上图可以看到基本类型数组的存储示意图,每个数组元素的值直接存储在对应的内存里。操作基本类型数组的数组元素时,实际上就是操作基本类型的变量。

引用类型数组的初始化

引用类型数组的数组元素是引用,因此情况变得更加复杂:每个数组元素里存储还是引用,它指向另一块内存,这块内存里存储了有效数据。

为了更好地说明引用类型数组的运行过程,下面先定义一个Person类(所有类都是引用类型):

1
2
3
4
5
6
7
8
9
10
public class Person {
//年龄
public int age;
//身高
public double height;
//定义一个info方法
public void info() {
System.out.println("我的年龄是:" + age + ",我的身高是:" + height);
}
}

下面程序将定义一个Person[]数组,接着动态初始化这个Person[]数组,并为这个数组的每个数组元素指定值。程序代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class TestReferenceArray {
public static void main(String[] args) {
//定义一个students数组变量,其类型是Person[]
Person[] students;
//执行动态初始化
students = new Person[2];
//创建一个Person实例,并将这个Person实例赋给zhang变量
Person zhang = new Person();
//为zhang所引用的Person对象的属性赋值
zhang.age = 15;
zhang.height = 158;
//创建一个Person实例,并将这个Person实例赋给lee变量
Person lee = new Person();
//为lee所引用的Person对象的属性赋值
lee.age = 16;
lee.height = 161;
//将zhang变量的值赋给第一个数组元素
students[0] = zhang;
//将lee变量的值赋给第二个数组元素
students[1] = lee;
//下面两行代码的结果完全一样,因为lee和students[1]指向的是同一个Person实例。
lee.info();
students[1].info();
}
}

上面代码的执行过程代表了引用类型数组的初始化的典型过程,下面将结合示意图详细介绍这段代码的执行过程。

执行Person[] students;代码时,这行代码仅仅在栈内存中定义了一个引用变量,也就是一个指针,这个指针并未指向任何有效的内存区。此时内存中存储示意如图所示:

referenceTypeInit1

在上图中的栈内存中定义了一个students变量,它仅仅是一个引用,并未指向任何有效的内存。直到执行初始化,本程序对students数组执行动态初始化,动态初始化由系统为数组元素分配默认的初始值:null,即每个数组元素的值都是null。如果尝试访问一个含有null的数组数据项,程序会出现Null Point Assignment (空指针赋值)的运行时错误。这主要是为了保证在读取某个数据项之前要先对其赋值。执行动态初始化后的存储示意如图所示:

referenceTypeInit2

从上图可以看出,students数组的两个数组元素都是引用,而且这个引用并未指向任何有效的内存,因此每个数组元素的值都是null。这意味着依然不能直接使用students数组元素,因为每个数组元素都是null,这相当于定义了两个连续的Person变量,但这个变量还未指向任何有效的内存区,所以这两个连续的Person变量(students数组的数组元素)还不能使用。

接着的代码定义了zhang和lee两个Person实例,定义这两个实例实际上分配了4块内存,在栈内存中存储了zhang和lee两个引用变量,还在堆内存中存储了两个Person实例。此时的内存存储示意如图所示:

referenceTypeInit3

此时students数组的两个数组元素依然是null,直到程序依次将zhang赋给students数组的第一个元素,把lee赋给students数组的第二个元素,students数组的两个数组元素将会指向有效的内存区,此时的内存存储示意如图所示:

referenceTypeInit4

从上图可以看出:此时zhang和students[0]指向同一个内存区,而且它们都是引用类型变量,因此通过zhang和students[0]来访问Person实例的属性和方法的效果完全一样,不论修改students[0]所指向的Person实例的属性,还是修改zhang变量所指向的Person实例的属性,所修改的其实是同一个内存区,所以必然互相影响。同理,lee和students[1]也是引用到同一个Person对象,也有相同的效果。

多维数组

如果从Java数组底层的运行机制来看,是没有多维数组的:

Java语言里的数组类型是引用类型,因此数组变量其实是一个引用,这个引用指向真实的数组内存。数组元素的类型也可以是引用,如果数组元素的引用再次指向真实的数组内存,这种情形看上去很像多维数组。

type[] arrName; 是典型的一维数组的定义语法,其中type是数组元素的类型。如果希望数组元素也是一个引用,比如是指向int数组的引用,则可以把type具体成int[],那么上面定义数组的语法就是int[][] arrName 。如果把int类型扩大到Java的所有类型(不包括数组类型),则出现了定义二维数组的语法:

1
type[][] arrName;

Java 语言采用上面的语法格式来定义二维数组,但它实质还是一维数组,只是其数组元素也是引用,数组元素里保存的引用指向一维数组。

初始化,同样可以把这个当成一个一维数组来初始化,其元素的类型是type[] 类型。

1
arrName = new type[length][];

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class TwoDimension {
public static void main(String[] args) {
//定义一个二维数组
int[][] a;
//把a当成一个一维数组进行初始化,初始化a是一个长度为4的数组
//a数组的数组元素又是引用类型
a = new int[4][];
//把a数组当成一维数组,遍历a数组的每个数组元素
for(int i=0,len=a.length;i<len;i++){
System.out.println(a[i]);
}
//初始化a数组的第一个元素
a[0] = new int[2];
//访问a数组的第一个元素所指数组的第二个元素
a[0][1] = 6;
//a数组的第一个元素是一个一维数组,遍历这个一维数组
for(int i=0,len=a[0].length;i<len;i++){
System.out.println(a[0][i]);
}
}
}

分析:int[][] a; 在栈内存中定义一个引用变量,这个变量并未指向任何有效的内存空间,此时堆内存中还未为这行代码分配任何存储区。

a = new int[4][]; 让a变量指向一块长度为4的数组内存,这个长度为4的数组里每个数组元素都是引用类型(数组类型),系统为这些数组分配默认的初始值null。

TwoDimension1

由于a数组的元素必须是int[]数组,所以接下来对a[0]元素执行初始化,也就是让上图堆内存中的第一个数组元素指向一个有效的数组内存,指向一个长度为2的int数组。因为程序采用动态初始化a[0]数组,因此系统将为a[0]所引用数组的每个元素分配默认的初始值0,然后显示为a[0]数组的第二个元素赋值为6。

TwoDimension2

初始化多维数组时,可以只指定最左边维的大小(如上所示),也可以一次指定每一维的大小。

1
2
//同时初始化二维数组的两个维数
int[][] b=new int[3][4];

TwoDimension3

还可以使用静态初始化方法来初始化二维数组。使用静态初始化方式来初始化二维数组,二维数组的每个数组元素都是一维数组,因此必须指定多个一维数组作为二维数组的初始化值。

1
2
3
4
//使用静态初始化语法来初始化一个二维数组
String[][] str1=new String[][]{new String[3],new String[]{"hello"}};
//使用简化的静态初始化语法来初始化二维数组
Stringp[][] str2={new String[3],new String[]{"hello"}};

TwoDimension4

Arrays工具类及其他应用

Arrays工具类

Arrays工具类提供了针对数组(Array)的一些操作,比如排序、搜索、将数组(Array)转换列表(List)等等。它提供的方法都是静态的。整个Arrays工具类的实现有3000+行,但是归纳总结一下可知它有以下功能:

  • List<T> asList(T… a):

将一个数组(变长参数的语法糖实现就是数组)转变成一个List(确切的来说是ArrayList),注意这个List是定长的,企图添加或者删除数据都会报错(java.lang.UnsupportedOperationException)(PS:参见Arrays.asList方法详解

  • int binarySearch(type[] a, type key):

使用二分法查询key元素值在a数组中出现的索引;如果a数组不包含key元素值,则返回负数。调用该方法时要求数组中元素已经按升序排列,这样才能得到正确结果。

  • int binarySearch(type[] a, int fromIndex, int toIndex, type key):

与上一个方法类似,但它只搜索a数组中fromIndex到toIndex索引的元素值。调用该方法时要求数组中元素已按升序排列,这样才能得到正确的结果。

  • type[] copyOf(type[] original, int newLength):

把original数组复制成一个新数组,其中newLength 是新数组的长度。如果newLength 小于original数组的长度,则新数组就是原数组的前面newLength个元素;如果大于原数组的长度,则新数组的前面元素就是原数组的所有元素,后面补充(数值类型)0、(布尔类型)false或者(引用类型)null。

  • type[] copyOfRange(type[] original, int from, int to):

与上一个方法类似,但这个方法只复制original数组的from索引到to索引的元素。

  • boolean equals(type[] a, type[] a2):

如果a数组和a2数组的长度相等,而且a数组和a2数组的数组元素也一一相同,该方法将返回true。(ps:比较一维数组可以使用equals,参数可以是基本类型数组也可以是引用类型数组;比较多维数组使用deepEquals ,参数是引用类型数组Object[]–参见链接:deepEquals和equals示例

  • void fill(type[] a, type val):

该方法将会把a数组的所有元素都赋值为val。

  • void fill(type[] a, int fromIndex, int toIndex,type val):

与上一个方法作用相同,区别只是该方法仅仅将a数组的fromIndex到toIndex索引的数组元素赋值为val。

  • int hashCode(type a[]):

返回数组的哈希码

  • void sort(type[] a) :

该方法对a数组元素进行排序。

  • void sort(char[] a, int fromIndex, int toIndex):

与上一个方法类似,区别是该方法仅仅对fromIndex到toIndex索引的元素进行排序。

  • String toString(type[] a):

将一个数组转换成一个字符串。该方法按顺序把多个数组元素连缀在一起,多个数组元素使用英文逗号和空格隔开。

下面补充一些不属于Arrays但很有用的方法:

数组复制

System 类static native void arraycopy(Object src, int srcPos, Object dest, int destPos,int length):复制数组。 需要的参数:源数组src,源数组的开始复制位置srcPos,目标数组dest,目标数组的开始复制位置destPos,需复制的元素个数。

基本类型和引用类型的数组都可以复制。如果复制引用型数组,只是复制了对象的引用——而不是对象本身的拷贝。这被称作浅复制 (shallow copy)

System.arraycopy() 不会执行自动包装盒自动拆包。两个数组必须具有相同的确切类型。

1
2
3
4
5
6
int[] src = {1,3,5,7,9,11,13,15,17};
int[] dest = {2,4,6,8,10,12,14,16,18,20};
//从src中的第一个元素起复制三个元素,即1,3,5覆盖到dest第2个元素开始的三个元素
System.arraycopy(src, 0, dest, 1, 3);
System.out.println(Arrays.toString(dest));
//[2, 1, 3, 5, 10, 12, 14, 16, 18, 20]

上面Arrays类提供了copyOfcopyOfRange 两个方法。

1
2
3
4
5
6
int[] src = {1,3,5,7,9,11,13,15,17};
int[] dest = {2,4,6,8,10,12,14,16,18,20};
//copyOf(是复制src数组从0开始的两个元素到新的数组对象)
int[] copyof=Arrays.copyOf(src, 2);
System.out.println(Arrays.toString(copyof));
//[1, 3]
1
2
3
4
5
6
int[] src = {1,3,5,7,9,11,13,15,17};
int[] dest = {2,4,6,8,10,12,14,16,18,20};
//copyRange(从src数组中从0开始的第二个元素到第五个元素复制到新数组,含头不含尾)
int[] copyofRange=Arrays.copyOfRange(src, 2,6);
System.out.println(Arrays.toString(copyofRange));
//[5, 7, 9, 11]

数组比较

Arrays类提供了重载后的equals()方法,用来比较整个数组。此方法针对所有基本类型和Object都做了重载。数组相等的条件是元素个数必须相等,并且对应位置的元素也相等。对于基本类型,需要使用基本类型的包装器类的equals()方法。

数组元素比较

排序必须根据对象的实际类型执行比较操作。一般自然的解决方案是为每种不同的类型各编写一个不同的排序方法,但这不能被新类型复用。另一种解决方案,采用策略设计模式,这里不变的是通用排序算法,变化的是各种对象相互比较的方式。所以就将“会发生变化的代码”封装在单独的类中(策略对象)。用不同的对象来表示不同的比较方式,然后将它们传递给相同的排序代码。

Java 中为我们提供了两种比较机制:ComparableComparator

实现Comparable接口

Comparablejava.lang 包下的一个接口,该接口里只有一个compareTo() 方法:

1
2
3
4
5
package java.lang;
import java.util.*;
public interface Comparable<T> {
public int compareTo(T o);
}

Comparable 可以让实现它的类的对象进行比较,具体的比较规则是按照 compareTo 方法中的规则进行。这种顺序称为 自然顺序

Comparable翻译为“可比较的”,表明实现该接口的类都是可以比较的,即实现Comparable接口的类本身就已经支持自比较。

其compareTo()方法只要一个参数,因为这里只有“你”“我”的关系,没有第三方。比如,两个人要比较身高,分辨高矮是人类固有的能力,两个人只要站到一起就能分出谁高谁矮。

例如: String、Integer 自己就可以完成比较大小操作,它们已经实现了Comparable接口。查看String类的源码可以看见是这样声明的(JDK1.7):

1
2
public final class String
implements java.io.Serializable, Comparable<String>, CharSequence

而Integer类的声明如下:

1
public final class Integer extends Number implements Comparable<Integer>

可见它们都实现了Comparable接口,它们的实例都可以通过调用自身的compareTo()方法来比较自己,例如:

1
2
3
4
5
6
String s1 = "aa";
String s2 = "ab";
System.out.println(s1.compareTo(s2)); //返回是两字符串第一个不同的char的unicode编码的差
Integer i1 = 3;
Integer i2 = 2;
System.out.println(i1.compareTo(i2)); //前者大返回1,后者大返回-1,相等返回0

而String类中的compareTo方法时这样实现的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int compareTo(String anotherString) {
int len1 = value.length;
int len2 = anotherString.value.length;
int lim = Math.min(len1, len2);
char v1[] = value;
char v2[] = anotherString.value;
int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2;//返回第一个不同字母的unicode的差
}
k++;
}
return len1 - len2;//如果两个字符串只有长度不同,则返回长度的差
}

Integer类中的compareTo()方法的实现如下:

1
2
3
4
5
6
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1); //前者大返回1,后者大返回-1,相等返回0
}

compareTo 方法的返回值有三种情况:

  • e1.compareTo(e2) > 0 即 e1 > e2
  • e1.compareTo(e2) = 0 即 e1 = e2
  • e1.compareTo(e2) < 0 即 e1 < e2

注意:

1.由于 null 不是一个类,也不是一个对象,因此在重写 compareTo 方法时应该注意 e.compareTo(null) 的情况,即使 e.equals(null) 返回 false,compareTo 方法也应该主动抛出一个空指针异常 NullPointerException。

2.Comparable 实现类重写 compareTo 方法时一般要求 e1.compareTo(e2) == 0 的结果要和 e1.equals(e2) 一致。这样将来使用 SortedSet 等根据类的自然排序进行排序的集合容器时可以保证保存的数据的顺序和想象中一致。

实际上所有实现了 Comparable 接口的 Java 核心类的结果都和 equlas 方法保持一致。Comparable对实现它的每个类的对象进行整体排序。这个接口需要类本身去实现。实现了 Comparable 接口的 List (或 数组)可以使用 Collections.sort() (或者 Arrays.sort() )方法进行排序。

实现 Comparable 接口的类的对象 可以用作 “有序映射 ( 如 TreeMap)” 中的键key或 “有序集合 (TreeSet)” 中的元素,而不需要指定比较器。

Comparable 接口属于 Java 集合框架的一部分。

现在我们可以参照String类及Integer类对于Comparable接口的实现来实现自己的比较方式,然后调用compareTo方法即可知道它们的顺序。 下面是一个例子(按Person类的年龄排序):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Arrays;
public class ComparableTest {
public static void main(String[] args) {
Person[] persons = new Person[]{
new Person(20, "P1"),
new Person(60, "P2"),
new Person(50, "P3"),
new Person(40, "P4")
};
Arrays.sort(persons);
System.out.println(Arrays.toString(persons));//数组需要借助Arrays.toString()格式化输出
//下面代码的结果一样
//List<Person> personList = Arrays.asList(persons);
//Collections.sort(personList);
//System.out.println(personList);//因为list的实现类重写了toString,可以格式化输出
}
}
class Person implements Comparable<Person> {
private int age;
private String name;
public Person(int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
//实现Comparable接口的compareTo方法
@Override
public int compareTo(Person o) {
return this.age - o.age;
}
@Override
public String toString() {
return "Person[name=" + name + ", age=" + age + "]";
}
}

​ 执行结果是:

1
[Person[name=P1, age=20], Person[name=P4, age=40], Person[name=P3, age=50], Person[name=P2, age=60]]

由此可见,Person对象已经通过Arrays.sort()方法按照age排序。

实现Comparator接口

Comparatorjava.util包下的一个接口,JDK 1.8 以前该接口里有两个方法compare() 和 equals():

1
2
3
4
5
package java.util;
public interface Comparator<T> {
int compare(T o1, T o2);
boolean equals(Object obj);
}

JDK 1.8 以后又新增了很多方法:

Comparator

基本上都是跟 Function 相关的,这里暂不介绍 1.8 新增的。

Comparator翻译为“比较器”,表明实现该接口的类都是一个比较器,一般在要比较的对象类型不支持自比较或者自比较函数不能满足要求时使用。

使用这种策略来比较时,如何进行比较和两个对象本身无关,而是由第三者(即比较器)来完成的。第三方比较器类需要另外专门设计:只要实现Comparator接口,任何一个类(对象)都可能成为一个“比较器”,但比较器并不是比较自己的实例,而是比较其它类的两个不同对象,比较器在这里充当“仲裁者”的角色,这也就是为什么compare()方法需要两个参数。 比如,两个人要比较谁智商更高,靠他们自身无法进行,这时要借助一个比较器(比如,智商测试题)。

从上面内容可知使用自然排序需要类实现 Comparable,并且在内部重写 comparaTo 方法。

而 Comparator 则是在外部制定排序规则,然后作为排序策略参数传递给某些类,比如 Collections.sort(), Arrays.sort(), 或者一些内部有序的集合(比如 SortedSet,SortedMap 等)。

使用方式主要分三步:

  1. 创建一个 Comparator 接口的实现类,并赋值给一个对象,在 compare 方法中针对自定义类写排序规则
  2. 将 Comparator 对象作为参数传递给 排序类的某个方法
  3. 向排序类中添加 compare 方法中使用的自定义类

使用此接口时,我们可以不在需要比较的类型(这里是Person类)中实现比较过程,而是把这个过程转移到了Comparator接口的compare方法中。于是,上面的例子需要修改为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class ComparatorTest {
public static void main(String[] args) {
Person1[] persons = new Person1[]{
new Person1(20, "P1"),
new Person1(60, "P2"),
new Person1(50, "P3"),
new Person1(40, "P4")
};
//Arrays.sort方法不支持使用Comparator比较器了,这里只能使用Collections.sort来排序
List<Person1> personList = Arrays.asList(persons);
System.out.println("Before sort: \r\n" + personList);
//这里,将一个比较器(Comparator)传递给sort方法作为参数,按照里面的比较逻辑对Person进行排序
Collections.sort(personList, new PersonComparator());
// Collections.sort(personList, new PersonComparator2());
System.out.println("After sort: \r\n" + personList);
}
}
//被比较的类型不需要实现任何接口
class Person1 {
private int age;
private String name;
public Person1(int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Person1[name=" + name + ", age=" + age + "]";
}
}
//这是一个比较器,用于比较Person对象
class PersonComparator implements Comparator<Person1> {
// 按年龄升序
@Override
public int compare(Person1 o1, Person1 o2) {
//两个Person对象的比较过程,当然,这里可以实现更多更复杂的比较过程
return o1.getAge() - o2.getAge();
//如果o1.age > o2.age,方法返回正数,为正数正是表明哦o1 > o2
//如果o1.age = o2.age,方法返回0,返回0正是表明o1 == o1
//如果o1.age < o2.age,方法返回正数,为负数正是表明哦o1 < o2
}
}
//比较器2
class PersonComparator2 implements Comparator<Person1> {
// 按年龄降序
@Override
public int compare(Person1 o1, Person1 o2) {
return o2.getAge()-o1.getAge();
}
}

输出结果为:

1
2
3
4
Before sort:
[Person1[name=P1, age=20], Person1[name=P2, age=60], Person1[name=P3, age=50], Person1[name=P4, age=40]]
After sort:
[Person1[name=P1, age=20], Person1[name=P4, age=40], Person1[name=P3, age=50], Person1[name=P2, age=60]]

由此可见,我们可以将一个自定义的比较器作为参数传递给Collections.sort()方法,下图是API中的Collections.sort()方法:

Comparator2

Person对象已经按照比较器中的规则进行排序。我们可以自定义一系列比较器,供排序时选择使用 ,比如上面又自定义比较器PersonComparator2,我们可以在Collections.sort() 选择对应的比较器。

如果在使用Collections.sort()方法时不提供这个Comparator,那么就以自然顺序排序,如Collections.sort()方法的API所说:

CollectionsSort

这里的自然顺序就是实现Comparable接口设定的排序方式。

​ 我们注意到Comparator接口中还有个equals()方法没有实现,可程序并没有报错,原因是实现该接口的类也是Object类的子类,而Object类已经实现了equals方法。

Comparable 和 Comparator总结

相同点

  1. 都是用于比较两个对象“顺序”的接口
  2. 都可以使用Collections.sort()方法来对对象集合进行排序

不同点

  1. Comparable位于java.lang包下,而Comparator则位于java.util包下
  2. Comparable 是在集合内部定义的方法实现的排序,Comparator 是在集合外部实现的排序

总结

  • 使用Comparable接口来实现对象之间的比较时,可以使这个类型(设为A)实现Comparable接口,并可以使用Collections.sort()方法来对A类型的List进行排序,之后可以通过a1.comparaTo(a2)来比较两个对象;
  • 当使用Comparator接口来实现对象之间的比较时,只需要创建一个实现Comparator接口的比较器(设为AComparator),并将其传给Collections.sort()方法即可对A类型的List进行排序,之后也可以通过调用比较器AComparator.compare(a1, a2)来比较两个对象。

​ 可以说一个是自己完成比较,一个是外部程序实现比较的差别而已

​ 用 Comparator 是策略模式(strategy design pattern),就是不改变对象自身,而用一个策略对象(strategy object)来改变它的行为。

​ 比如:你想对整数采用绝对值大小来排序,Integer 是不符合要求的,你不需要去修改 Integer 类(实际上你也不能这么做)去改变它的排序行为,这时候只要(也只有)使用一个实现了 Comparator 接口的对象来实现控制它的排序就行了。

​ 两种方式,各有各的特点:使用Comparable方式比较时,我们将比较的规则写入了比较的类型中,其特点是高内聚。但如果哪天这个规则需要修改,那么我们必须修改这个类型的源代码。如果使用Comparator方式比较,那么我们不需要修改比较的类,其特点是易维护,但需要自定义一个比较器,后续比较规则的修改,仅仅是改这个比较器中的代码即可。但实际应用中,可以用Comparable的compareTo()方法来定义默认排序方式,用Comparator定义其他排序方式。

相关链接

文章目录
  1. 1. 前言
  2. 2. 数据结构概述
  3. 3. 数组
    1. 3.1. 定义数组
    2. 3.2. 初始化
      1. 3.2.1. 静态初始化
      2. 3.2.2. 动态初始化
    3. 3.3. 使用数组
    4. 3.4. 深入数组
      1. 3.4.1. 内存中的数组
      2. 3.4.2. 基本类型数组初始化
      3. 3.4.3. 引用类型数组的初始化
    5. 3.5. 多维数组
    6. 3.6. Arrays工具类及其他应用
      1. 3.6.1. Arrays工具类
      2. 3.6.2. 数组复制
      3. 3.6.3. 数组比较
      4. 3.6.4. 数组元素比较
        1. 3.6.4.1. 实现Comparable接口
        2. 3.6.4.2. 实现Comparator接口
        3. 3.6.4.3. Comparable 和 Comparator总结
  4. 4. 相关链接
|