Java源码分析之Arrays

乍一看Arrays的源码，223k，5000多行，心想争取2，3内看完，没想到，里面，居然，是每种基本类型都写了一遍，还有object，真的是，！

先看排序吧（只拿int举例了）

//基本类型都是调用另一个类的排序函数，是快排，当我也想顺便把这个也贴上来的时候发现，一个int的排序有400行！！！我还是决定，再开一篇在讨论吧 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); } //1.8之后，对排序做了进一步的优化，调用了另一个类的排序，那个类里面也是调用的快排 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(); } public static void parallelSort(int[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); int n = toIndex - fromIndex, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJInt.Sorter (null, a, new int[n], fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke(); }

Object的排序不同于基本类型，使用的是归并排序+插入排序

public static void sort(Object[] a) { if (LegacyMergeSort.userRequested) legacyMergeSort(a); else ComparableTimSort.sort(a, 0, a.length, null, 0, 0); } private static void legacyMergeSort(Object[] a) { Object[] aux = a.clone(); mergeSort(aux, a, 0, a.length, 0); } private static final int INSERTIONSORT_THRESHOLD = 7; private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) { int length = high - low; //当元素个数小于7个的时候，直接插入排序 // Insertion sort on smallest arrays if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >>> 1; mergeSort(dest, src, low, mid, -off); mergeSort(dest, src, mid, high, -off); // If list is already sorted, just copy from src to dest. This is an // optimization that results in faster sorts for nearly ordered lists. if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) dest[i] = src[p++]; else dest[i] = src[q++]; } } private static void swap(Object[] x, int a, int b) { Object t = x[a]; x[a] = x[b]; x[b] = t; }

二分查找

public static int binarySearch(int[] a, int key) { return binarySearch0(a, 0, a.length, key); } //也可以是从一段区间中查找 public static int binarySearch(int[] a, int fromIndex, int toIndex, int key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } //注意，Java中个给的二分，只是说这段区间中有没有，并返回该index，而不是返回第一个出现的位置或者是最后一次出现的位置 private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; //居然是找到了就返回 else return mid; // key found } //并不是找不到就返回-1，而是-(low + 1)，所以区间查找的话，判有没有要看的是该index的正负 return -(low + 1); // key not found. }

判两个数组是否相等

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; }

填充

public static void fill(int[] a, int val) { for (int i = 0, len = a.length; i < len; i++) a[i] = val; } //可以填充一段区间 public static void fill(int[] a, int fromIndex, int toIndex, int val) { rangeCheck(a.length, fromIndex, toIndex); for (int i = fromIndex; i < toIndex; i++) a[i] = val; }

复制

//如果newLength > original.length，居然不是抛出异常，而是取两个中的最小值，如果newLength < 0呢。。 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; } 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; }

hashCode

//这里给出了一种计算hash值的方法，用的数是31 public static int hashCode(int a[]) { if (a == null) return 0; int result = 1; for (int element : a) result = 31 * result + element; return result; } //如果是多维数组，计算hash的方法 public static int deepHashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) { int elementHash = 0; //递归求hash，算是一大亮点吧 if (element instanceof Object[]) elementHash = deepHashCode((Object[]) element); else if (element instanceof byte[]) elementHash = hashCode((byte[]) element); else if (element instanceof short[]) elementHash = hashCode((short[]) element); else if (element instanceof int[]) elementHash = hashCode((int[]) element); else if (element instanceof long[]) elementHash = hashCode((long[]) element); else if (element instanceof char[]) elementHash = hashCode((char[]) element); else if (element instanceof float[]) elementHash = hashCode((float[]) element); else if (element instanceof double[]) elementHash = hashCode((double[]) element); else if (element instanceof boolean[]) elementHash = hashCode((boolean[]) element); else if (element != null) elementHash = element.hashCode(); result = 31 * result + elementHash; } return result; }

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(", "); } }

另外还有spliterator，stream等实现并行访问的方法，在这里就先不写了