7.4 剖析Arrays

数组是存储多个同类型元素的基本数据结构，数组中的元素在内存连续存放，可以通过数组下标直接定位任意元素，相比在后续章节介绍的其他容器而言效率非常高。

数组操作是计算机程序中的常见基本操作。Java中有一个类Arrays，包含一些对数组操作的静态方法，本节主要就来讨论这些方法。首先介绍怎么用，然后介绍它们的实现原理。学习Arrays的用法，就可以“避免重新发明轮子”，直接使用，学习它的实现原理，就可以在需要的时候自己实现它不具备的功能。

7.4.1 用法

Arrays类中有很多方法，我们主要介绍toString、排序、查找，对于一些其他方法，如复制、比较、批量设置值和计算哈希值等，我们也进行简单介绍。

1. toString

Arrays的toString()方法可以方便地输出一个数组的字符串形式，以便查看。它有9个重载的方法，包括8个基本类型数组和1个对象类型数组，下面列举两个：

public static String toString(int[] a)
public static String toString(Object[] a)

例如：

int[] arr = {9,8,3,4};
System.out.println(Arrays.toString(arr));
String[] strArr = {"hello", "world"};
System.out.println(Arrays.toString(strArr));

输出为：

[9, 8, 3, 4]
[hello, world]

如果不使用Arrays.toString方法，直接输出数组自身，即代码改为：

public static String toString(int[] a)
public static String toString(Object[] a)
int[] arr = {9,8,3,4};
System.out.println(Arrays.toString(arr));
String[] strArr = {"hello", "world"};
System.out.println(Arrays.toString(strArr));
int[] arr = {9,8,3,4};
System.out.println(arr);
String[] strArr = {"hello", "world"};
System.out.println(strArr);

则输出会变为如下所示：

[I@1224b90
[Ljava.lang.String; @728edb84

这个输出就难以阅读了，@后面的数字表示的是内存的地址。

2．排序

排序是一种非常常见的操作。同toString一样，对每种基本类型的数组，Arrays都有sort方法（boolean除外），例如：

public static void sort(int[] a)
public static void sort(double[] a)

排序按照从小到大升序排列，例如：

int[] arr = {4, 9, 3, 6, 10};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));

输出为：

[3, 4, 6, 9, 10]

数组已经排好序了。

除了基本类型，sort还可以直接接受对象类型，但对象需要实现Comparable接口。

public static void sort(Object[] a)
public static void sort(Object[] a, int fromIndex, int toIndex)

我们看个String数组的例子：

String[] arr = {"hello", "world", "Break", "abc"};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));

输出为：

[Break, abc, hello, world]

“Break”之所以排在最前面，是因为大写字母的ASCII码比小写字母都小。那如果排序的时候希望忽略大小写呢？sort还有另外两个重载方法，可以接受一个比较器作为参数：

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

方法声明中的T表示泛型，泛型我们在第8章介绍，这里表示的是，这个方法可以支持所有对象类型，只要传递这个类型对应的比较器就可以了。Comparator就是比较器，它是一个接口，Java 7中的定义是：

public interface Comparator<T> {
    int compare(T o1, T o2);
    boolean equals(Object obj);
}

最主要的是compare这个方法，它比较两个对象，返回一个表示比较结果的值，-1表示o1小于o2,0表示o1等于o2,1表示o1大于o2。排序是通过比较来实现的，sort方法在排序的过程中需要对对象进行比较的时候，就调用比较器的compare方法。Java 8中Comparator增加了多个静态和默认方法，具体可参看API文档。

String类有一个public静态成员，表示忽略大小写的比较器：

public static final Comparator<String> CASE_INSENSITIVE_ORDER = new CaseInsensitiveComparator();

我们通过这个比较器再来对上面的String数组排序：

String[] arr = {"hello", "world", "Break", "abc"};
Arrays.sort(arr, String.CASE_INSENSITIVE_ORDER);
System.out.println(Arrays.toString(arr));

这样，大小写就忽略了，输出变为：

[abc, Break, hello, world]

为进一步理解Comparator，我们来看下String的这个比较器的主要实现代码，如代码清单7-2所示。

代码清单7-2 String的CaseInsensitiveComparator实现

private static class CaseInsensitiveComparator
        implements Comparator<String> {
    public int compare(String s1, String s2) {
          int n1 = s1.length();
          int n2 = s2.length();
          int min = Math.min(n1, n2);
          for(int i = 0; i < min; i++) {
              char c1 = s1.charAt(i);
              char c2 = s2.charAt(i);
              if(c1 ! = c2) {
                  c1 = Character.toUpperCase(c1);
                  c2 = Character.toUpperCase(c2);
                  if(c1 ! = c2) {
                      c1 = Character.toLowerCase(c1);
                      c2 = Character.toLowerCase(c2);
                      if(c1 ! = c2) {
                        //No overflow because of numeric promotion
                        return c1 - c2;
                    }
                }
            }
        }
        return n1 - n2;
    }
}

代码比较简单直接，就不解释了。

sort方法默认是从小到大排序，如果希望按照从大到小排序呢？对于对象类型，可以指定一个不同的Comparator，可以用匿名内部类来实现Comparator，比如：

String[] arr = {"hello", "world", "Break", "abc"};
Arrays.sort(arr, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return o2.compareToIgnoreCase(o1);
    }
});
System.out.println(Arrays.toString(arr));

程序输出为：

[world, hello, Break, abc]

以上代码使用一个匿名内部类实现Comparator接口，返回o2与o1进行忽略大小写比较的结果，这样就能实现忽略大小写且按从大到小排序。

Collections类中有两个静态方法，可以返回逆序的Comparator，例如：

public static <T> Comparator<T> reverseOrder()
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)

关于Collections类，我们在12.2节介绍。

这样，上面字符串忽略大小写逆序排序的代码可以改为：

String[] arr = {"hello", "world", "Break", "abc"};
Arrays.sort(arr, Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
System.out.println(Arrays.toString(arr));

传递比较器Comparator给sort方法，体现了程序设计中一种重要的思维方式。将不变和变化相分离，排序的基本步骤和算法是不变的，但按什么排序是变化的，sort方法将不变的算法设计为主体逻辑，而将变化的排序方式设计为参数，允许调用者动态指定，这也是一种常见的设计模式，称为策略模式，不同的排序方式就是不同的策略。

3．查找

Arrays包含很多与sort对应的查找方法，可以在已排序的数组中进行二分查找。所谓二分查找就是从中间开始查找，如果小于中间元素，则在前半部分查找，否则在后半部分查找，每比较一次，要么找到，要么将查找范围缩小一半，所以查找效率非常高。

二分查找既可以针对基本类型数组，也可以针对对象数组，对对象数组，也可以传递Comparator，也可以指定查找范围。比如，针对int数组：

public static int binarySearch(int[] a, int key)
public static int binarySearch(int[] a, int fromIndex, int toIndex, int key)

针对对象数组：

public static int binarySearch(Object[] a, Object key)

指定自定义比较器：

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

如果能找到，binarySearch返回找到的元素索引，比如：

int[] arr = {3,5,7,13,21};
System.out.println(Arrays.binarySearch(arr, 13));

输出为3。如果没找到，返回一个负数，这个负数等于-（插入点+
1）。插入点表示，如果在这个位置插入没找到的元素，可以保持原数组有序，比如：

int[] arr = {3,5,7,13,21};
System.out.println(Arrays.binarySearch(arr, 11));

输出为-4，表示插入点为3，如果在3这个索引位置处插入11，可以保持数组有序，即数组会变为{3,5,7,11,13,21}。

需要注意的是，binarySearch针对的必须是已排序数组，如果指定了Comparator，需要和排序时指定的Comparator保持一致。另外，如果数组中有多个匹配的元素，则返回哪一个是不确定的。

4．更多方法

除了常用的toString、排序和查找，Arrays中还有复制、比较、批量设置值和计算哈希值等方法。

基于原数组，复制一个新数组，与toString一样，也有多种重载形式，例如：

public static long[] copyOf(long[] original, int newLength)
public static <T> T[] copyOf(T[] original, int newLength)

判断两个数组是否相同，支持基本类型和对象类型，如下所示：

public static boolean equals(boolean[] a, boolean[] a2)
public static boolean equals(Object[] a, Object[] a2)

只有数组长度相同，且每个元素都相同，才返回true，否则返回false。对于对象，相同是指equals返回true。

Arrays包含很多fill方法，可以给数组中的每个元素设置一个相同的值：

public static void fill(int[] a, int val)

也可以给数组中一个给定范围的每个元素设置一个相同的值：

public static void fill(int[] a, int fromIndex, int toIndex, int val)

针对数组，计算一个数组的哈希值：

public static int hashCode(int a[])

计算hashCode的算法和String是类似的，我们看下代码：

public static int hashCode(int a[]) {
    if(a == null)
        return 0;
    int result = 1;
    for(int element : a)
        result = 31 ＊ result + element;
    return result;
}

回顾一下，String计算hashCode的算法也是类似的，数组中的每个元素都影响hash值，位置不同，影响也不同，使用31一方面产生的哈希值更分散，另一方面计算效率也比较高。

Java 8和9对Arrays类又增加了一些方法，比如将数组转换为流、并行排序、数组比较等，具体可参看API文档。

7.4.2 多维数组

之前介绍的数组都是一维的，数组还可以是多维的。先来看二维数组，比如：

int[][] arr = new int[2][3];
for(int i=0; i<arr.length; i++){
    for(int j=0; j<arr[i].length; j++){
        arr[i][j] = i+j;
    }
}

arr就是一个二维数组，第一维长度为2，第二维长度为3，类似于一个矩阵，或者类似于一个表格，第一维表示行，第二维表示列。arr[i]表示第i行，它本身还是一个数组， arr[i][j]表示第i行中的第j个元素。

除了二维，数组还可以是三维、四维等，但一般而言，很少用到三维以上的数组，有几维，就有几个[]。比如，一个三维数组的声明为：

int[][][] arr = new int[10][10][10];

在创建数组时，除了第一维的长度需要指定外，其他维的长度不需要指定，甚至第一维中每个元素的第二维的长度可以不一样，看个例子：

int[][] arr = new int[2][];
arr[0] = new int[3];
arr[1] = new int[5];

arr是一个二维数组，第一维的长度为2，第一个元素的第二维长度为3，而第二个元素的第二维长度为5。

多维数组到底是什么呢？其实，可以认为，多维数组只是一个假象，只有一维数组，只是数组中的每个元素还可以是一个数组，这样就形成二维数组；如果其中每个元素还都是一个数组，那就是三维数组。

Arrays中的toString、equals、hashCode都有对应的针对多维数组的方法：

public static String deepToString(Object[] a)
public static boolean deepEquals(Object[] a1, Object[] a2)
public static int deepHashCode(Object a[])

这些deepXXX方法，都会判断参数中的元素是否也为数组，如果是，会递归进行操作。

看个例子：

int[][] arr = new int[][]{{0,1}, {2,3,4}, {5,6,7,8}};
System.out.println(Arrays.deepToString(arr));

输出为：

[[0, 1], [2, 3, 4], [5, 6, 7, 8]]

7.4.3 实现原理

下面介绍Arrays的方法的实现原理。hashCode()的实现我们已经介绍了；fill和equals等的实现都很简单，循环操作即可，不再赘述；下面主要介绍二分查找和排序的实现代码。

1．二分查找

二分查找（binarySearch）的代码比较直接，如代码清单7-3所示。

代码清单7-3 Arrays的二分查找实现

private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
                                      T key, Comparator<? super T> c) {
    int low = fromIndex;
    int high = toIndex - 1;
    while(low <= high) {
        int mid = (low + high) >>> 1;
        T midVal = a[mid];
        int cmp = c.compare(midVal, key);
        if(cmp < 0)
            low = mid + 1;
        else if(cmp > 0)
            high = mid - 1;
        else
            return mid; //key found
    }
    return -(low + 1);   //key not found
}

上述代码中有两个标志：low和high，表示查找范围，在while循环中，与中间值进行对比，大于则在后半部分查找（提高low），否则在前半部分查找（降低high）。

2．排序

与Arrays中的其他方法相比，sort要复杂得多。排序是计算机程序中一个非常重要的方面，几十年来，计算机科学家和工程师们对此进行了大量的研究，设计实现了各种各样的算法，进行了大量的优化。一般而言，没有一个最好的算法，不同算法往往有不同的适用场合。

那Arrays的sort是如何实现的呢？具体实现非常复杂，我们简单了解下。

对于基本类型的数组，Java采用的算法是双枢轴快速排序（Dual-PivotQuicksort）。这个算法是Java 7引入的，在此之前，Java采用的算法是普通的快速排序。双枢轴快速排序是对快速排序的优化，新算法的实现代码位于类java.util.DualPivotQuicksort中。

对于对象类型，Java采用的算法是TimSort。TimSort也是在Java 7引入的，在此之前， Java采用的是归并排序。TimSort实际上是对归并排序的一系列优化，TimSort的实现代码位于类java.util.TimSort中。

在这些排序算法中，如果数组长度比较小，它们还会采用效率更高的插入排序。

为什么基本类型和对象类型的算法不一样呢？排序算法有一个稳定性的概念，所谓稳定性就是对值相同的元素，如果排序前和排序后，算法可以保证它们的相对顺序不变，那算法就是稳定的，否则就是不稳定的。

快速排序更快，但不稳定，而归并排序是稳定的。对于基本类型，值相同就是完全相同，所以稳定不稳定没有关系。但对于对象类型，相同只是比较结果一样，它们还是不同的对象，其他实例变量也不见得一样，稳定不稳定可能就很有关系了，所以采用归并排序。

这些算法的实现是比较复杂的，所幸的是，Java提供了很好的封装，绝大多数情况下，我们会用就可以了。

7.4.4 小结

其实，Arrays中包含的数组方法是比较少的，很多常用的操作没有，比如，Arrays的binarySearch只能针对已排序数组进行查找，那没有排序的数组怎么方便查找呢？

Apache有一个开源包（http://commons.apache.org/proper/commons-lang/），里面有一个类ArrayUtils（位于包org.apache.commons.lang3），包含了更多的常用数组操作，这里就不列举了。

数组是计算机程序中的基本数据结构，Arrays类以及ArrayUtils类封装了关于数组的常见操作，使用这些方法，避免“重新发明轮子”吧。