Arrays源码分析

Arrays源码分析

简介

Arrays.class中是对array进行操作的类，主要的操作包括排序和搜索。如果array的引用为空，则会抛出空指针异常

NullPointerException

方法

1.rangeCheck 数组越界检查

private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) { if (fromIndex > toIndex) { throw new IllegalArgumentException( "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); } if (fromIndex < 0) { throw new ArrayIndexOutOfBoundsException(fromIndex); } if (toIndex > arrayLength) { throw new ArrayIndexOutOfBoundsException(toIndex); } }

私有的静态方法。

2.排序

在Arrays.java中，对基本类型的数组提供了DualPivotQuicksort即双轴快速排序。

主要是提供了sort方法和其重载：

public static void sort(int[] a) { DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); } #重载 public static void sort(int[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); }

除了int之外，还可以对char、shot、long、double、byte、float运行此方法。改变待排序数组即可。

还提供parallelSort的排序方式，处理的基本类型同上。

/* 算法思想： 并行排序的思想就是将数组划分成几个小数组并行排序然后合并 */ public static void parallelSort(int[] a) { int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJInt.Sorter (null, a, new int[n], 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke(); }

注意：

MIN_ARRAY_SORT_GRAN官方文档中称为粒度，其实可以理解为待排序数组的允许最小长度，如果低于这个长度或者线程为1则直接调用双轴快排DualPivotQuicksort，对应的就是这段代码：

if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);

当满足长度要求之后，实际上是调用了Helper类，完成的并行排序算法。

ArraysParallelSortHelpers简要源码分析

此类是帮助Arrays.parallelSort完成其排序操作的实际操作类。那么Helper为每个基本类型都提供了静态类，每个静态类负责完成Sorter和Merger。

基本算法思想：

if array size is small, just use a sequential quicksort (via Arrays.sort) Otherwise: 1. Break array in half. 2. For each half, a. break the half in half (i.e., quarters), b. sort the quarters c. merge them together 3. merge together the two halves. 从以上算法思想可以看出，对于长度过短的array，直接调用的是Arrays.sort方法，也就是双轴快排。

每一个基本类型都对应着一个static final修饰的类,同时在类的主体内部，包含两个内部类，分别是Sorter和Merger。

static final class FJChar { static final class Sorter extends CountedCompleter<Void>{} static final class Merger extends CountedCompleter<Void>{}

具体的算法代码未做分析

3.对于Object和泛型的排序算法

public static <T extends Comparable<? super T>> void parallelSort(T[] a) { int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0); else new ArraysParallelSortHelpers.FJObject.Sorter<T> (null, a, (T[])Array.newInstance(a.getClass().getComponentType(), n), 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke(); }

可以看到，和基本类型还是有点区别：

基本类型中，如果长度不满足，则默认调用双轴快排DualPivotQuicksortObject和泛型中，默认调用的是TimSort

object和T泛型还包括一些归并排序，此处不作介绍

4.算法

二分查找

public static int binarySearch(long[] a, int fromIndex, int toIndex,long key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } private static int binarySearch0(long[] a, int fromIndex, int toIndex,long key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; long midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } ">>> 1"位移操作 相当于/2

5.equal方法

JDK1.8文档中给出的解释：

如果两个数组包含相同数量的元素并且对应元素相同，则两个数组equalIn other words, two arrays are equal if they contain the same elements in the same order public static boolean equals(int[] a, int[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; i<length; i++) if (a[i] != a2[i]) return false; return true; }

其实可以看到，equal方法中首先是判断两个数组是否，然后依次进行判断。所以如果两个array都为null，那么equal的结果还是true，因为这两个数组满足==

文末我们会对java中的equal和==操作的区别和联系进行总结。

6.fill方法

将给定数组全部填充为具体value

public static void fill(long[] a, long val) { for (int i = 0, len = a.length; i < len; i++) a[i] = val; }

7.copyof方法

public static int[] copyOf(int[] original, int newLength) { int[] copy = new int[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }

给定新数组的长度，将原数组进行copy。

新数组长度大于原数组，则补零新数组长度小于原数组，则截断返回的是一个新的同类型数组，调用的是System.arraycopy()方法。

8.copyOfRange方法

public static int[] copyOfRange(int[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); int[] copy = new int[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; }

给定copy的范围。

9.asList

public static <T> List<T> asList(T... a) { return new ArrayList<>(a); }

注意返回的是一个新的new

10.内部类ArrayList

private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable { private static final long serialVersionUID = -2764017481108945198L; private final E[] a; ArrayList(E[] array) { a = Objects.requireNonNull(array); } @Override public int size() { return a.length; } @Override public Object[] toArray() { return a.clone(); } @Override @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { int size = size(); if (a.length < size) return Arrays.copyOf(this.a, size, (Class<? extends T[]>) a.getClass()); System.arraycopy(this.a, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } @Override public E get(int index) { return a[index]; } @Override public E set(int index, E element) { E oldValue = a[index]; a[index] = element; return oldValue; } @Override public int indexOf(Object o) { E[] a = this.a; if (o == null) { for (int i = 0; i < a.length; i++) if (a[i] == null) return i; } else { for (int i = 0; i < a.length; i++) if (o.equals(a[i])) return i; } return -1; } @Override public boolean contains(Object o) { return indexOf(o) != -1; } @Override public Spliterator<E> spliterator() { return Spliterators.spliterator(a, Spliterator.ORDERED); } @Override public void forEach(Consumer<? super E> action) { Objects.requireNonNull(action); for (E e : a) { action.accept(e); } } @Override public void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); E[] a = this.a; for (int i = 0; i < a.length; i++) { a[i] = operator.apply(a[i]); } } @Override public void sort(Comparator<? super E> c) { Arrays.sort(a, c); } }

原来ArrayList是Arrays的内部类而已，他们之间并不是继承关系。

所以以下声明是错误的：

Arrays arrays = new ArrayList();

因为ArrayList不是Array子类

Arrays arrays = new Arrays();

这种的声明也是错误的。因为Arrays.java中，其无参构造器是private修饰的，不允许你使用。

private Arrays() {}

java: Arrays()可以在java.util.Arrays中访问private

11.hashCode方法

public static int hashCode(long a[]) { if (a == null) return 0; int result = 1; for (long element : a) { int elementHash = (int)(element ^ (element >>> 32)); result = 31 * result + elementHash; } return result; } 如果两个数组相等也就是满足equals操作，则他们的hashcode值相等。null数组的hashcode返回为0

12.toString()方法

public static String toString(int[] a) { if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) return b.append(']').toString(); b.append(", "); } }