Array Advanced

Java有大量的方式可以持有对象,其中数组是一种效率最高的存储和随机访问对象引用序列的方式

以下有些用了Java8的特性,刷题时看到有些人用,试了试

数组是对象


无论是基本类型数组还是对象类型数组,数组标识符只是一个引用,指向在堆里创建的一个真实对象。

1
2
3
4
5
6
7
int[] arr1 = new int[5];
Integer[] arr2 = new Integer[5];
System.out.println(arr1);
System.out.println(arr2);
Field[] fields = arr2.getClass().getDeclaredFields();
System.out.println(Arrays.toString(fields));

System.out.println()调用了String.valueOf()方法,后者最终调用了Object.toString(),返回对象的类名和16进制的对象地址值。

1
2
3
[I@15db9742
[Ljava.lang.Integer;@6d06d69c
[]

数组是特殊的对象,它有一个只读成员length,但上面代码显示.getDeclaredFields()获取不到这个字段。

容器替代数组?


数组可以持有基本类型,而泛型之前的容器并不能。也就是说,在泛型之前,容器类在处理对象时都会将对象视为Object对象(没有任何具体类型),而数组可以持有某种具体类型。更深一层的意义就是在编译期可以指出类型错误。

有了泛型,容器也可以检查类型。随着自动包装机制的出现,容器已经可以和数组几乎一样方便地用于基本类型中了。数组硕果仅存的优点就是效率了。

数组初始化


基本类型数组的工作方式与对象数组一样,不过基本类型的数组直接存储基本类型数据的值。

默认初始化

1
2
3
4
5
6
7
int[] arr3;
Random rand = new Random();
arr3 = new int[rand.nextInt(5)];
//基本类型中,Arrays.stream()目前只支持int\long\double
Arrays.stream(arr3)
.forEach(s ->System.out.print(s+" "));

上面代码里我定义了一个int数组arr3,此时只是一个引用(已经为这个引用分配了足够的空间),还没有给数组对象本身分配任何空间。Random.nextInt()在运行时随机出数组的大小,这表明数组对象的创建确实是在运行时进行的。

1
0 0

初始化的默认值:对于int、long型是0,flaot、double型是0.0,char是’’即(char)0),boolean型是false,引用对象类型是null。

静态初始化

1
2
3
4
Integer[] arr5 = {
new Integer(1),
2,//自动装箱
};

在这种情况下,存储空间的分配由编译器负责。初始化列表最后一个逗号可选(这个特性使维护长列表变得更容易)。

动态初始化

1
2
3
Integer[] arr6 = new Integer[rand.nextInt(10)];
Arrays.stream(arr6).map(s -> rand.nextInt(500))
.forEach(s ->System.out.print(s+" "));

在这里,“Integer[] arr6 = new Integer[rand.nextInt(10)];”之后arr6还只是一个引用。直到map()里创建Integer对象,并把对象赋值给引用,初始化进程才算结束。

1
1 2 177 77 210 482 487 477 235 191

可变参数列表


1
2
3
4
5
6
7
8
9
10
public class VarArgs {
public static void main(String[] args){
f();
f(1,2,new Integer(3));
}
public static void f(Integer... args){
Arrays.stream(args)
.forEach(s -> System.out.print(s+" "));
}
}

可变参数与自动装箱互不影响,传递给可变参数列表0个参数也是可行的。

1
1 2 3

使用可变参数列表重载时需要多注意一点

1
2
3
4
5
6
7
8
9
10
11
12
public class OverloadingVarargs1 {
public static void main(String[] args) {
g(1,'a');
g('a','b');
}
public static void g(float i, Character... args){
System.out.println("first");
}
public static void g(Character... args){
System.out.println("second");
}
}
line 4 error: The method g(float, Character[]) is ambiguous for the type OverloadingVarargs

作为对比,又写了一个。注意这里并没有报错。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class OverloadingVarargs2 {
public static void main(String[] args) {
g(1,2);
Character c = 'c';
Double d = (double) 2;
}
public static void g(float i, double... args){
System.out.println("first");
}
public static void g(double... args){
System.out.println("second");
}
}
1
first

对于重载可能出现的匹配混淆,可以采用非可变参数来解决:

1
2
3
4
5
6
7
8
9
10
11
12
public class OverloadingVarargs3 {
public static void main(String[] args) {
g(1,'a');
g('a','b');
}
public static void g(float i, Character... args){
System.out.println("first");
}
public static void g(Character... args){
System.out.println("second");
}
}
1
2
first
second

多维数组


1
int[][] arr7;

JAVA采用上面的语法格式来定义二维数组,但它的实质还是一维数组,只是其数组元素也是引用,数组元素里保存的引用指向一维数组。并且多维数组每一维度可以具有任意的长度(被称为粗糙数组)。

对以上不太理解,可扩展阅读 Java多维数组解读

数组与泛型的斗争


泛型vs数组

你不能实例化具有参数化类型的数组。

1
ArrayList<String>[] arr9 = new ArrayList<String>[]();//illegal

擦除会移除参数化类型信息,而数组必须知道它们所持有的确切类型,以强制保证类型安全。

但是可以创建泛型数组的引用。

1
List<String>[] ls;

尽管不能创建实际的持有泛型的数组对象,但是可以创建非泛型的数组,然后对其转型。

1
2
3
4
5
6
List<String>[] arr10 = (List<String>[])new List[4];
for(int i=0;i<arr10.length;i++){
arr10[i] = new ArrayList<String>();
arr10[i].add("oath");
}
System.out.println(Arrays.toString(arr10));
1
[[oath], [oath], [oath], [oath]]

将for循环改成foreach语法打印结果均是null。

1
2
3
4
5
6
List<String>[] arr10 = (List<String>[])new List[4];
for(List<String> a: arr10){
a = new ArrayList<String>();
a.add("oath");
}
System.out.println(Arrays.toString(arr10));
1
[null, null, null, null]

foreach不能赋值,只能用来遍历。stream相关的foreach/map使用时也要注意。可扩展阅读 foreach语法详解

参数化方法vs参数化类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ParameterizedArrayType {
public static void main(String[] args) {
Integer[] ints = {1,2,3,4};
Double[] doubles = {1.1,2.2,3.3,4.4};
Integer[] ints2 = new ClassParameter<Integer>().f(ints);
Double[] doubles2 = new ClassParameter<Double>().f(doubles);
ints2 = MethodParameter.f(ints);
doubles2 = MethodParameter.f(doubles);
}
}
class ClassParameter<T>{
public T[] f(T[] arg){
return arg;
}
}
class MethodParameter{
public static <T> T[] f(T[] arg){
return arg;
}
}

参数化方法显然比参数化类方便很多,不需要为应用的每种类型都使用一个参数去实例化这个类,并且你可以把参数化方法定义成static,用类名.方法调用。

Arrays类探索


可以在java.util类库里找到Arrays类,它有一套实用的用于数组的static方法。
Arrays类对以下的方法均针对所有基本类型和Object类型做了重载。

Arrays.fill()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class FillingArrays {
public static void main(String[] args) {
String[] arr8 = new String[6];
Arrays.fill(arr8, "oath");
System.out.println(Arrays.toString(arr8));
Arrays.fill(arr8, 4, 6, "yangmen");
System.out.println(Arrays.toString(arr8));
student[] arr9 = new student[2];
Arrays.fill(arr9, new student("xiaoming"));
System.out.println(Arrays.toString(arr9));
}
}
class student{
String name;
student(String name){
this.name = name;
}
}

fill只能用同一个值填充各个位置,或者像line 6所示,只填充数组的某个区域。而针对对象而言,就是复制同一个引用进行填充。该方法内部实现也是利用for循环逐个赋值。

1
2
3
[oath, oath, oath, oath, oath, oath]
[oath, oath, oath, oath, yangmen, yangmen]
[FillingArrays.student@4c873330, FillingArrays.student@4c873330]

Array.copyOf()

1
2
3
4
5
int[] arr12 = new int[]{1,2,3,4,5};
int[] arr13 = Arrays.copyOf(arr12, 2);
System.out.println(Arrays.toString(arr13));
arr13 = Arrays.copyOfRange(arr12, 3, 5);
System.out.println(Arrays.toString(arr13));
1
2
[1, 2]
[4, 5]

copyOf()实现里调用了System.arraycopy(Object src, int srcPos,Object dest, int destPos,int length)方法。

1
2
3
4
5
6
7
8
int[] arr14 = new int[5];
int[] arr15 = new int[7];
Arrays.fill(arr14, 47);
Arrays.fill(arr15, 66);
System.out.println("arr14 "+Arrays.toString(arr14));
System.out.println("arr15 "+Arrays.toString(arr15));
System.arraycopy(arr14, 1, arr15, 1, 3);
System.out.println("arr15 "+Arrays.toString(arr15));
1
2
3
arr14 [47, 47, 47, 47, 47]
arr15 [66, 66, 66, 66, 66, 66, 66]
arr15 [66, 47, 47, 47, 66, 66, 66]

如果复制对象数组,只会复制对象的引用——而不是对象本身的拷贝(浅复制)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class FillingArrays {
public static void main(String[] args) {
student[] arr16 = new student[1];
student[] arr17 = new student[2];
Arrays.fill(arr17,new student("haha"));
student i = new student("oath");
arr16[0] = i;
System.out.println("arr16 "+Arrays.toString(arr16));
System.out.println("arr17 "+Arrays.toString(arr17));
System.arraycopy(arr16, 0, arr17, 0, 1);
System.out.println("arr17 "+Arrays.toString(arr17));
System.out.println("arr17[0]'s name: "+arr17[0].name);
i.name = "oath2";
System.out.println("arr17 "+Arrays.toString(arr17));
System.out.println("arr17[0]'s name: "+arr17[0].name);
}
}
class student{
String name;
student(String name){
this.name = name;
}
}
1
2
3
4
5
6
arr16 [CopyingArrays.student@119d7047]
arr17 [CopyingArrays.student@776ec8df, CopyingArrays.student@776ec8df]
arr17 [CopyingArrays.student@119d7047, CopyingArrays.student@776ec8df]
arr17[0]'s name: oath
arr17 [CopyingArrays.student@119d7047, CopyingArrays.student@776ec8df]
arr17[0]'s name: oath2

还要注意,System.arrayCopy()不会执行自动包装和自动拆包。不举例了。

Arrays.toString()/Arrays.deepToString()

1
2
3
4
5
int[][] arr18 = new int[2][2];
Arrays.fill(arr18[0], 11);
Arrays.fill(arr18[1], 22);
System.out.println(Arrays.toString(arr18));
System.out.println(Arrays.deepToString(arr18));

Arrays.toString()对基本类型数据进行了重载,直接打印值。

1
2
[[I@3b07d329, [I@41629346]
[[11, 11], [22, 22]]

Arrays.toString(Object[])调用String.valueOf(),后者调用了Object.toString()。

Arrays.deepToString()递归调用了自身直至最后一层,最后使用基本类型和Object的toString()方法。

此处顺便加深一下二维数组实质是一维数组。

Arrays.equals()/Arrays.deepEquals()

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 ComparingArrays {
public static void main(String[] args) {
String[] arr19 = new String[2];
Arrays.fill(arr19, "oath");
String[] arr20 = {new String("oath"),new String("oath"),};
System.out.println(Arrays.equals(arr19,arr20));
student[] arr21 = new student[2];
Arrays.fill(arr21, new student("yangmen"));
student[] arr22 = {new student("yangmen"),new studen("yangmen")};
System.out.println(Arrays.equals(arr21,arr22));
int[][] arr23 = new int[2][2];
int[][] arr24 = new int[2][2];
Arrays.fill(arr23[0], 56);
Arrays.fill(arr24[0], 56);
System.out.println(Arrays.deepEquals(arr23,arr24));
}
}
class student{
String name;
student(String name){
this.name = name;
}
}

equals()方法对所有基本类型和Object类型都做了重载。基本类型和Object类型都会先比较数组地址,再比较数组长度。最后逐个比较元素,基本类型用自身包装类的equals()方法比较每一个元素,Object类型对每一个元素使用equals()作比较判断。

1
2
3
true
false
true

String类对超类Object类的equals()方法进行了重载,比较每个元素的内容。student类并没有重写,所以结果为false。

deepEquals()会递归调用自身直至最后一层,最后使用基本类型和Object的equals()方法。

数组的比较

在排序和搜索之前,说一下数组的比较。

排序比较根据对象的实际类型执行比较操作。一种自然的解决方案是为每种不同的类型各编写一个不同的排序方法,但这样的代码难以被新的类型所复用。因此,使用策略设计模式,将“会发生变化的代码”封装在单独的类中(策略对象),然后把策略对象传递给总是相同的代码,这些代码将使用策略来完成其算法。

Java有两种方式来提供比较功能。

  • 第一种是实现java.lang.Comparable接口,使你的类具体“天生”的比较能力。这个接口很简单,只要重写compareTo()方法即可。
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
public class CompType1 {
public static void main(String[] args) {
Employee[] arr25 = new Employee[3];
for(int j=0;j<arr25.length;j++){
String name = getRandomString(4);
int age = (int)Math.round(Math.random()*50);
arr25[j] = new Employee(name,age);
}
Arrays.stream(arr25)
.forEach(s -> System.out.println(s.toString()));
Arrays.sort(arr25);
System.out.println();
Arrays.stream(arr25)
.forEach(s -> System.out.println(s.toString()));
}
public static String getRandomString(int length) {
String base = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJ"
+"KLMNOPQRSTUVWXYZ0123456789";
Random random = new Random();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < length; i++) {
int idex = random.nextInt(base.length());
sb.append(base.charAt(idex));
}
return sb.toString();
}
}
class Employee implements Comparable<Employee>{
String name;
int age;
Employee(String name,int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(Employee o) {
return age-o.age;
}
public String toString(){
return "name: "+this.name+" age: "+this.age+" ";
}
}
1
2
3
4
5
6
7
name: TKA8 age: 1
name: Yqvr age: 15
name: eN4W age: 13
name: TKA8 age: 1
name: eN4W age: 13
name: Yqvr age: 15

Arrays.sort(Object[])比较时调用Employee里的compareTo()方法。

  • 第二种是编写自己的Comparator,传递给一些排序方法如Collections.sort()或者 Arrays.sort()。

String类本身重写了comprareTo()方法,是按字典序从小到大排序的。此处想先按长度再按字典序的顺序排序。所以需要自己写一个Comparator。

此外Collections类的reverseOrder()可以产生一个Comparator,是自然排序顺序的反序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class CompType2 {
public static void main(String[] args) {
String[] arr26 = {"afsd","acsd","afsdijk"};
Arrays.sort(arr26);
Arrays.stream(arr26)
.forEach(s -> System.out.println(s.toString()));
Comparator<String> comp = new Comparator<String>(){
@Override
public int compare(String s1, String s2) {
if(s1.length()!=s2.length())
return s2.length()-s1.length();
else
return s1.compareTo(s2);
}
};
System.out.println();
Arrays.sort(arr26,comp);
Arrays.stream(arr26)
.forEach(s -> System.out.println(s.toString()));
Arrays.sort(arr26,Collections.reverseOrder());
Arrays.stream(arr26)
.forEach(s -> System.out.println(s.toString()));
}
}
1
2
3
4
5
6
7
8
9
10
11
acsd
afsd
afsdijk
afsdijk
acsd
afsd
afsdijk
afsd
acsd

Arrays.sort()

可选择全排序或者部分排序。对象实现了Comparble接口(自带compareTo())或传入自己想要的Comparator。

此处要提的是String类里也有一个自定义的Comparator,String.CASE_INSENSITIVE_ORDER

  • sort(T[] a)
  • sort(T[] a, Comparator<? super T> c)
  • sort(T[] a, int fromIndex, int toIndex,Comparator<? super T> c)

对基本类型也有相应的sort()方法重载。具体内部排序之后在排序章节补充,此处会补上跳转链接。

Arrays.binarySearch()

如果数组已经排好序了,就可以使用binaraySearch进行快速查找。这里需要知道2点:

  • 如果找到目标,Arrays.binarySearch()返回目标在数组中的index值(>=0);如果没找到则返回 -(插入点)-1 (<0)。
  • 如果使用了Comparator排序了某个对象数组(基本类型数组不能用Comparator排序),这种情况下使用binarySearch()时必须提供同样的Comparator。

    binarySearch(T[] a, T key, Comparator<? super T> c)
    binarySearch(long[] a, int fromIndex, int toIndex,long key)

    基本类型当然也重载了以上两种。

下面是float基本类型的binarySearch(),注意midBits == keyBits这部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
float midVal = a[mid];
if (midVal < key)
low = mid + 1; // Neither val is NaN, thisVal is smaller
else if (midVal > key)
high = mid - 1; // Neither val is NaN, thisVal is larger
else {
int midBits = Float.floatToIntBits(midVal);
int keyBits = Float.floatToIntBits(key);
if (midBits == keyBits) // Values are equal
return mid; // Key found
else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
low = mid + 1;
else // (0.0, -0.0) or (NaN, !NaN)
high = mid - 1;
}
}
return -(low + 1); // key not found.

浮点数判断需要注意,float 和double 的精度范围,超过范围的数字会被忽略

  • 浮点数大小判断

    如果没有等号关系在里面,也就必然一大一小,那么直接用 > 或者 <

  • 浮点数相等判断

    因为浮点数在内存中存放,可能无法精确的储存,所以不同的值,可能有相同的内存数据。所以要使用以下的方法:
    以float为例,32位APP中精度为e-7,所以取1e-7。
    两个数字A、B,如果|A-B|<1e-7,则计算机里A、B就是相等的。

举例,0.0和-0.0在内存里就是不同的存储数据,所以在查找元素的时候应当区分。其他场景下时大小应该是一样的都是0。


END

0 Comments