Arrays源码阅读
提供了排序，并行排序，二分查找，范围填充，相等比较，深度比较等方法，深入理解一下实现方法
私有属性：
MIN_ARRAY_SORT_GRAN
private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
当数组长度小于MIN_ARRAY_SORT_GRAN将不会执行并行排序算法，源码注释中说原因是因为长度太小，划分任务也会很小，会导致内存争用，反而不会加速，所以设置一个阈值。
NaturalOrder
static final class NaturalOrder implements Comparator<Object> {
@SuppressWarnings("unchecked")
public int compare(Object first, Object second) {
return ((Comparable<Object>)first).compareTo(second);
}
static final NaturalOrder INSTANCE = new NaturalOrder();
}
一个用于自然排序的静态内部类，实现了Comparator接口，重写了compare方法，在方法中对比较类型进行了Comparable类型强转，调用了Comparable接口的compareTo方法，要求比较的对象实现Comparable接口
LegacyMergeSort
static final class LegacyMergeSort {
private static final boolean userRequested =
java.security.AccessController.doPrivileged(
new sun.security.action.GetBooleanAction(
"java.util.Arrays.useLegacyMergeSort")).booleanValue();
}
安全检查，若用户自己确定可以比较大小，则userRequested为true。这个类未来会被弃用，若未使用，不推荐使用。不过可以到时候看看安全检查的细节//TODO
INSERTIONSORT_THRESHOLD
private static final int INSERTIONSORT_THRESHOLD = 7;
若元素数量小于7，则采用插入算法
ArrayList
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable
这是调用asList（）后得到的就是这个类，一个只读的类，不是util.Arraylist。
方法
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);
}
sort底层调用DualPivotQuicksort，双轴快排，一个优化了排序方法，根据元素数量或是归并分组长度和数量，选择优化过的成对插入排序，双轴快排或归并算法。
sort支持int，short，long，char，byte，float,double，自定义类型数组。
[fromIndex,toIndex)左闭右开
- 自定义类型
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
public static void sort(Object[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex);
else
ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}
安全检查，legacyMergeSort(a)：底层调用归并排序，若递归中，若元素小于INSERTIONSORT_THRESHOLD，则直接插入排序
若没有，调用ComparableTimSort.sort，一个优化过的归并排序，考虑了最坏情况，并且与插入排序混合使用。
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
if (c == null) {
sort(a, fromIndex, toIndex);
} else {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);
else
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
}
}
和上面类似
parallelSort 并行排序
当数据量较大时，并行排序会有较大的差异，数据量小的话影响不大，中等的话，并行排序会比sort慢几毫秒。
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();
}
ForkJoinPool：支持将一个任务拆分成多个小任务并行计算然后合并。（见ForkJoinPool，挖个坑，看多线程的时候写//TODO）
不太理解parallelSort(int[] a)里面为什么不调用parallelSort(int[] a, int fromIndex, int toIndex)，代码部分重复了呀？//TODO
如果满足条件则会调用arraysparallelsorthelpers中的每个基本类型对应的类的sort函数)如果满足条件则会调用ArraysParallelSortHelpers中的每个基本类型对应的类的sort函数。
parallelPrefix
并行，lambda//TODO
binarySearch 二分查找
- 基本类型
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);
}
该方法会返回一个查找的key的index，如果没找到，就会记录这个值可以插入数组的index，返回-（index+1）
Object[] a = { 1 , 2 ,3, 5 , 6 , 7 };
System.out.println ( Arrays.binarySearch (a , 3));//2
System.out.println ( Arrays.binarySearch (a , 4));//-4
binarySearch(int[] a, int key)在内部调用了binarySearch(int[] a, int fromIndex, int toIndex,int key)，上面parallelSort（）为什么不这么做呢？
- 自定义类型
public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,T key, Comparator<? super T> c) {
return binarySearch0(a, 0, a.length, key, c);
}
如果类没有实现Comparable或其他情况，那么查找的时候也要把比较函数传进来
- equals 和 deepEquals
public static boolean equals(Object[] a, Object[] 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++) {
Object o1 = a[i];
Object o2 = a2[i];
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
return true;
}
各种类型都差不多，先比较地址，再判断null，再长度，最后一个一个元素判断，不过自定义类型还需要再判断一次取出的元素是不是null的！ deepEquanls用来比较多维的，因为多维存的是引用，直接用equals比较的是地址，如果是object类型，会调用类型自己的equals方法
- fill
public static void fill(Object[] a, Object val) {
for (int i = 0, len = a.length; i < len; i++)
a[i] = val;
}
public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
rangeCheck(a.length, fromIndex, toIndex);
for (int i = fromIndex; i < toIndex; i++)
a[i] = val;
}
初始化数组，填充范围内全为指定值
-copyOf 和 copyOfRange
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
先进行类型判断 底层调用的是本地方法System.arraycopy，会对指定的长度进行合法判断，copyOfRange与copyOf类似
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
- asList
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
返回一个Arrays内部定义的一个ArrayList，若要转化为数组，基本类型就用循环，实例对象则如下
Integer[] a = { 1 , 2 , 5 , 6 , 7 , 4 , 3 , 0 };
Integer[] b = new Integer[ a.length ];
Arrays.asList(a).toArray (b);
- hashCode 和 deepHashCode
基本类型：
int
public static int hashCode(int a[]) {
if (a == null)
return 0;
int result = 1;
for (int element : a)
result = 31 * result + element;
return result;
}
循环叠加结果，result = 31 * result + element;
double
public static int hashCode(double a[]) {
if (a == null)
return 0;
int result = 1;
for (double element : a) {
long bits = Double.doubleToLongBits(element);
result = 31 * result + (int)(bits ^ (bits >>> 32));
}
return result;
}
小数比较的话有精读问题，这里使用Double的doubleToLongBits方法处理的。
Double.doubleToLongBits(element);将double的元素转换为longbit
object类型和基本类型差不多，不过多了一个deepHashCode
public static int deepHashCode(Object a[]) {
if (a == null)
return 0;
int result = 1;
for (Object element : a) {
int elementHash = 0;
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;
}
当数组里存放数组时，若用hashCode（object[])，数组会根据数组地址去计算hashcode，而用deepHashCode则会计算数组中的值
hashcode 例子：
int[] m = { 1 };
int[] n = { 1 };
Object[] a = { 1 , 2 , 5 , 6 , 7 , 4 , 3 , m };
Object[] b = { 1 , 2 , 5 , 6 , 7 , 4 , 3 , n };
System.out.println (Arrays.hashCode (a)==Arrays.hashCode (b));//false
System.out.println (Arrays.deepHashCode (a)==Arrays.deepHashCode (b));//true
- toStirng 和deepToString
public static String toString(Object[] 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(String.valueOf(a[i]));
if (i == iMax)
return b.append(']').toString();
b.append(", ");
}
}
deepToStriing，原理和之前deepHashCode差不多，太长了就不贴了，需要的时候可以点进去看看，里面还是有一些细节注意，比如初始化StringBuilder大小，回溯，还用了个set，用...表示重复元素
剩下一堆java 8的方法，留坑//TODO
网友评论