摘要：容器相关的操作及其源码分析说明本文是基于分析的。源码是个好东东，各种编码技巧，再次佩服老外下一个主题是容器，。在了解容器之前我们先来看下重点的数据吧，还有工具类。第一段话说明返回一个指定数组的固定列表。
容器相关的操作及其源码分析 说明
1、本文是基于JDK 7 分析的。JDK 8 待我工作了得好好研究下。Lambda、Stream。
2、因为个人能力有限，只能以模仿的形式+自己的理解写笔记。如有不对的地方还请谅解。
3、记录的比较乱，但是对自己加深印象还是蛮有作用的。
4、笔记放github了，有兴趣的可以看看。喜欢的可以点个star。
5、读过源码的可以快速浏览一遍，也能加深自己的理解。
6、源码是个好东东，各种编码技巧，再次佩服老外！！！
7、下一个主题是容器，gogogo。感觉可以的话可以关注哈。
1、Array、Arrays在了解容器之前我们先来看下重点的数据吧，还有Arrays工具类。
首先看一个栗子，利用数组计算大数字。完整的点这里，重点思想就是计算数组中的每一个数，关键字是怎么进和留。
/**
* Created by guo on 2018/2/2.
* 利用数组计算大数字
*/
public static int[] get(int[] ints, int num) {
//计算每一位
for (int i = 0; i < ints.length; i++) {
ints[i] *= num;
}
//进和留
for (int i = ints.length - 1; i > 0; i--) {
//把个位数除10，加上前面的数
ints[i - 1] += ints[i] / 10;
//把最后的数模10，剩余个位数。1-9
ints[i] = ints[i] % 10;
}
return ints;
}
需要注意的还有一个System.arrayscopy()方法，那就是底层数组的拷贝，这个也是关键点。完整代码
/**
* 底层实现的数组拷贝，是一个本地方法
* void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
* src the source array.
* srcPos starting position in the source array.
* dest the destination array.
* destPos starting position in the destination data.
* length the number of array elements to be copied.
*/
System.arraycopy(src,-1,dest,2,3);
/**
* 参数：
* src：源，从哪个数组中拷贝数据
* dest：目标：把数据拷贝到哪一个数组中
* srcpos：从原数组中哪一个位置开始拷贝
* destPos：在目标数组开始存放的位置
* length：拷贝的个数
*/
static void arrayCopy(int[] src, int srcPos, int[] dest, int destPos, int length) {
if(srcPos < 0 || destPos < 0 || length < 0) {
throw new RuntimeException("出异常了，重新检查");
}
for (int index = srcPos; index < srcPos + length; index++) {
dest[destPos] = src[index];
destPos++;
}
}
static void print(int[] arr) {
String str = "[";
for (int i = 0; i < arr.length; i++) {
str += arr[i];
if (i != arr.length - 1) { //不是最后一个元素
str = str + ",";
}
}
str = str + "]";
System.out.println(str);
}
其他内容不是今天的重点，这里只是容器中需要数组的底层Copy。
ArraysArrays类是Java中用于操作数组的类，使用这个工具类可以减少平常很多工作量。 主题框架参考这里，写的非常不错，
我们具体现看看它有哪些方法
1、sort 排序
2、binarySearch 二分查找(折半查找)
3、equals 比较
4、fill 填充
5、asList 转列表 记得一个toArray吗？
6、indexOf str首次出现的位置
6、hash 哈希(重点)
7、toString 重写Object中方法
首先来看看排序的
/**
* Sorts the specified array into ascending numerical order.
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a);
}
需要关注的是底层默认是按升序(asc),还有调用这个DualPivotQuicksort.sort(a)方法是什么鬼？中文意思为双轴快速排序，它在性能上优于传统的单轴快速排序。 它是不稳定的。
重点在这里O(n log(n)),还有这句话` and is typically
faster than traditional (one-pivot) Quicksort implementations.` 具体看大佬的博文友情提示
/**
* This class implements the Dual-Pivot Quicksort algorithm by
* Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*/
final class DualPivotQuicksort {
}
上面的sort传进去的是int[] a,接下来看看传Object对象的。All elements in the array must implement the Comparable interface.
/**
* Sorts the specified array of objects into ascending order, according
* to the {@linkplain Comparable natural ordering} of its elements.
* All elements in the array must implement the {@link Comparable}
* interface. Furthermore, all elements in the array must be
* mutually comparable (that is, {@code e1.compareTo(e2)} must
* not throw a {@code ClassCastException} for any elements {@code e1}
* and {@code e2} in the array).
*/
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a);
}
在来看看带泛型参数的，这个重点那，有三个点需要关注，Comparator，ClassCastException 和 TimSort算法 是从JDK 7 开始默认支持，
/** * Sorts the specified array of objects according to the order induced by * the specified comparator. All elements in the array must be * mutually comparable by the specified comparator must not throw a * *ClassCastException for any elements and in the array. */ public staticvoid sort(T[] a, Comparator c) { if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else TimSort.sort(a, c); //注意这个TimSort }
整体上在看看这几个到底啥意思？
/**
*大概意思就是旧的归并算法使用了系统属性，可能会导致循环依赖，不是能是静态boolean，未来版本将移除
* Old merge sort implementation can be selected (for
* compatibility with broken comparators) using a system property.
* Cannot be a static boolean in the enclosing class due to
* circular dependencies. To be removed in a future release.
*/
static final class LegacyMergeSort {
private static final boolean userRequested =
java.security.AccessController.doPrivileged(
new sun.security.action.GetBooleanAction(
"java.util.Arrays.useLegacyMergeSort")).booleanValue();
}
//传进Object的排序，
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a);
}
/** To be removed in a future release. */
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
//都要移除啊，看来的JDK8了
/** To be removed in a future release. */
private static void legacyMergeSort(Object[] a,
int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
Object[] aux = copyOfRange(a, fromIndex, toIndex);
mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
}
/**
* 列表大小低于插入将优先使用归并算法，也要移除啊，
* Tuning parameter: list size at or below which insertion sort will be
* used in preference to mergesort.
* To be removed in a future release.
*/
private static final int INSERTIONSORT_THRESHOLD = 7;
/**
* Src is the source array that starts at index 0
* Dest is the (possibly larger) array destination with a possible offset
* low is the index in dest to start sorting
* high is the end index in dest to end sorting
* off is the offset to generate corresponding low, high in src
* To be removed in a future release.
*/
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
// Insertion sort on smallest arrays
//小数组将使用普通的插入算法
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; ilow &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// Merge sorted halves (now in src) into dest
}
----------------------------------------------------------------------------
/**
* Swaps x[a] with x[b]. 这个可以理解，面试手写算法时，可以写这个那。
*/
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
从上面的逻辑可以看出，它的实现方式分为两种，一种是通过Arrays中的归并算法实现的,另外一种采用了TimSOrt算法，
这个排序算法是稳定的，JDK8已经删除了，我们来看看8是怎么实现的。
/**
* Sorts the specified array of objects according to the order induced by
* the specified comparator. All elements in the array must be
* mutually comparable by the specified comparator (that is,
* {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
* for any elements {@code e1} and {@code e2} in the array).
* @since 1.8
*/
@SuppressWarnings("unchecked")
public static void parallelSort(T[] a, Comparator cmp) {
if (cmp == null)
cmp = NaturalOrder.INSTANCE;
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, cmp, null, 0, 0); //还是这个
else
new ArraysParallelSortHelpers.FJObject.Sorter
(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, cmp).invoke();
}
需要注意的是方法名变成了parallelSort并行啊，
这个也是重点，除传入int[]之外其他都变成了parallelSort.慢慢来吧，先JDK7，在JDK 8.还有就是可以传进其他类型，char、long、byte。etc(等)。
/**
* Checks that {@code fromIndex} and {@code toIndex} are in
* the range and throws an exception if they aren"t.
*/
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);
}
}
二分查找，
注意接下来，我们只看泛型有关的方法，其他实现大同小异。因为泛型很重要。
/**
* Searches the specified array for the specified object using the binary
* search algorithm. The array must be sorted into ascending order
* according to the specified comparator (as by the
* {@link #sort(Object[], Comparator) sort(T[], Comparator)}
* method) prior to making this call. If it is
* not sorted, the results are undefined.
* If the array contains multiple
* elements equal to the specified object, there is no guarantee which one
* will be found.
*/
public static int binarySearch(T[] a, T key, Comparator c) {
return binarySearch0(a, 0, a.length, key, c);
}
/**
* Searches a range of
* the specified array for the specified object using the binary
* search algorithm.
* The range must be sorted into ascending order
* according to the specified comparator (as by the
* {@link #sort(Object[], int, int, Comparator)
* sort(T[], int, int, Comparator)}
* method) prior to making this call.
* If it is not sorted, the results are undefined.
* If the range contains multiple elements equal to the specified object,
* there is no guarantee which one will be found.
*/
public static int binarySearch(T[] a, int fromIndex, int toIndex,
T key, Comparator c) {
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key, c);
}
rangeCheck作用就是检查边界，看数据是否越界，会抛出ArrayIndexOutOfBoundsException
binarySearch0这是什么鬼？点进去看看
要明白首先看参数
//fromIndex就是开始索引(inclusive)，toIndex结束(exclusive)，key就是指定的数。 * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; */
/** * 二分查找法(折半查找)：前提是在已经排好序的数组中，通过将待查找的元素 * 与中间索引值对应的元素进行比较，若大于中间索引值对应的元素，去右半边查找， * 否则，去左边查找。依次类推。直到找到位置；找不到返回一个负数 * * Like public version, but without range checks. *这里没有边界检查，这才是二分查找重点。 */ private staticequalsint binarySearch0(T[] a, int fromIndex, int toIndex, T key, Comparator c) { if (c == null) { //先判断 return binarySearch0(a, fromIndex, toIndex, key); } int low = fromIndex; //开始下标 int high = toIndex - 1; //结束下标 while (low <= high) { int mid = (low + high) >>> 1; //这里用了向右移2位(左边补0)，/2 向左就是 *2. T midVal = a[mid]; int cmp = c.compare(midVal, key); //比较key是在左边还是右边 if (cmp < 0) //小于0意味着key大， low = mid + 1; //则去掉左边的值。中间的索引+1就是新的开始下标 else if (cmp > 0) //key比中间的小 high = mid - 1; //则去掉右边的，中间下标-1，就是新的结束下标 else return mid; // key found } return -(low + 1); // key not found.这里是-1 -(0 + 1) }
接下来在看看比较的，这个是重点。这里只看Object[]，其他还有很多，如int、byte、char
重点看这句话：
In other words, the two arrays are equal if
they contain the same elements in the same order.
Also, two array references are considered equal if both are null
以相同的顺序，并且互相包含，则返回true，
两个数组引用都为null，则返回true。
