快讯：构造器必须是私有的 工具类的特征是什么？

工具类特征：

(资料图)

构造器必须是私有的，工具类一般不需要初始化，可以直接使用；工具类的方法必须是被static final方法修饰，保证方法不可变；不要在工具类方法中对共享变量有修改的操作，如果一定要有，必须加锁保证线程安全；工具类的所有方法都没有线程安全问题；

一、Arrays

Arrays主要提供了对数组的高效操作，包括排序、查找、填充、拷贝、相等判断等操作；

1、sort(int[] a)

1.1、JDK1.6

1.1.1、源码

// int类型数组排序public static void sort(int[] a) {sort1(a, 0, a.length);}private static void sort1(int x[], int off, int len) {// Insertion sort on smallest arrays    if (len < 7) {for (int i = off; i < len + off; i++)            for (int j = i; j > off && x[j - 1] > x[j]; j--)                swap(x, j, j - 1);        return;    }    // Choose a partition element, v    int m = off + (len >> 1);       // Small arrays, middle element    if (len > 7) {int l = off;        int n = off + len - 1;        if (len > 40) {// Big arrays, pseudomedian of 9            int s = len / 8;            l = med3(x, l, l + s, l + 2 * s);            m = med3(x, m - s, m, m + s);            n = med3(x, n - 2 * s, n - s, n);        }        m = med3(x, l, m, n); // Mid-size, med of 3    }    int v = x[m];    // Establish Invariant: v* (v)* v*    int a = off, b = a, c = off + len - 1, d = c;    while (true) {while (b <= c && x[b] <= if="" while="" c="">= b && x[c] >= v) {if (x[c] == v)                swap(x, c, d--);            c--;        }        if (b > c)            break;        swap(x, b++, c--);    }    // Swap partition elements back to middle    int s, n = off + len;    s = Math.min(a - off, b - a);    vecswap(x, off, b - s, s);    s = Math.min(d - c, n - d - 1);    vecswap(x, b, n - s, s);    // Recursively sort non-partition-elements    if ((s = b - a) > 1)        sort1(x, off, s);    if ((s = d - c) > 1)        sort1(x, n - s, s);}/** * Swaps x[a] with x[b]. */private static void swap(int x[], int a, int b) {int t = x[a];    x[a] = x[b];    x[b] = t;}/** * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */private static void vecswap(int x[], int a, int b, int n) {for (int i = 0; i < n; i++, a++, b++)        swap(x, a, b);}/** * Returns the index of the median of the three indexed integers. */private static int med3(int x[], int a, int b, int c) {return (x[a] < x[b] ?            (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :            (x[b] > x[c] ? b : x[a] > x[c] ? c : a));}

1.1.2、分析

（1）数组长度小于7，那么排序时基于基本的插入排序算法（2）数组长度大于7，那么在使用的优化后的快速排序，对应数组长度在7和40之间的数组，取的切分元素相对来说简单点

1.2、JDK1.7

1.2.1、源码：

public static void sort(int[] a) {DualPivotQuicksort.sort(a);}// 下面方法来自：java.util.DualPivotQuicksort#sort(int[])public static void sort(int[] a) {sort(a, 0, a.length - 1);}/** * If the length of an array to be sorted is less than this * constant, Quicksort is used in preference to merge sort. */private static final int QUICKSORT_THRESHOLD = 286;/** * The maximum number of runs in merge sort. */private static final int MAX_RUN_COUNT = 67;/** * The maximum length of run in merge sort. */private static final int MAX_RUN_LENGTH = 33;public static void sort(int[] a, int left, int right) {// Use Quicksort on small arrays    if (right - left < QUICKSORT_THRESHOLD) {sort(a, left, right, true);        return;    }    /*     * Index run[i] is the start of i-th run     * (ascending or descending sequence).     */    int[] run = new int[MAX_RUN_COUNT + 1];    int count = 0; run[0] = left;    // Check if the array is nearly sorted    for (int k = left; k < right; run[count] = k) {if (a[k] < a[k + 1]) {// ascending            while (++k <= right && a[k - 1] <= else="" if=""> a[k + 1]) {// descending            while (++k <= right="" k="" -="">= a[k]);            for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {int t = a[lo]; a[lo] = a[hi]; a[hi] = t;            }        } else {// equal            for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {if (--m == 0) {sort(a, left, right, true);                    return;                }            }        }        /*         * The array is not highly structured,         * use Quicksort instead of merge sort.         */        if (++count == MAX_RUN_COUNT) {sort(a, left, right, true);            return;        }    }    // Check special cases    if (run[count] == right++) {// The last run contains one element        run[++count] = right;    } else if (count == 1) {// The array is already sorted        return;    }    /*     * Create temporary array, which is used for merging.     * Implementation note: variable "right" is increased by 1.     */    int[] b; byte odd = 0;    for (int n = 1; (n <<= 1) < count; odd ^= 1);    if (odd == 0) {b = a; a = new int[b.length];        for (int i = left - 1; ++i < right; a[i] = b[i]);    } else {b = new int[a.length];    }    // Merging    for (int last; count > 1; count = last) {for (int k = (last = 0) + 2; k <= count; k += 2) {int hi = run[k], mi = run[k - 1];            for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {if (q >= hi || p < mi && a[p] <= else="" if="" count="" for="" int="" i="right," lo="run[count" -="" --i="">= lo;                 b[i] = a[i]                    );            run[++last] = right;        }        int[] t = a; a = b; b = t;    }}/** * Sorts the specified range of the array by Dual-Pivot Quicksort. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param leftmost indicates if this part is the leftmost in the range */private static void sort(int[] a, int left, int right, boolean leftmost){}

在JDK7中，排序使用的双轴快速排序，其要比传统的单轴排序要快

双轴快速排序：如果数组的长度小于QUICKSORT_THRESHOLD的话就会使用这个双轴快速排序，而这个值是286

if (right - left < QUICKSORT_THRESHOLD) {sort(a, left, right, true);    return;}

1.3、JDK1.8

1.3.1、源码

public static void sort(int[] a) {DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);}

DualPivotQuicksort.sort方法

private static final int QUICKSORT_THRESHOLD = 286;static void sort(int[] a, int left, int right,                 int[] work, int workBase, int workLen) {// Use Quicksort on small arrays，QUICKSORT_THRESHOLD为286，当要排序区间小于286时，发现调用了本类的重载sort方法    if (right - left < QUICKSORT_THRESHOLD) {sort(a, left, right, true);        return;    }    /**    * run[i] 意味着第i个有序数列开始的位置，（升序或者降序）    **/    int[] run =new int[MAX_RUN_COUNT + 1];    int count=0; run[0] = left;    // 检查数组是不是已经接近有序状态    for(int k = left; k < right; run[count] = k) {if(a[k] < a[k + 1]){// 升序            while(++k <= right && a[k - 1] <= else=""> a[k + 1]) {// 降序            while(++k <=right k="" -="">= a[k]);            //如果是降序的，找出k之后，把数列倒置            for (int lo = run[count],hi = k;++lo < --hi) {int t = a[lo]; a[lo] = a[hi]; a[hi] = t;            }        } else {// 相等            for(int m = MAX_RUN_LENGTH; ++k <=right && a[k - 1] == a[k];) {// 数列中有至少MAX_RUN_LENGTH的数据相等的时候，直接使用快排。                // 这里为什么这么处理呢？                if(--m == 0){sort(a, left, right, true);                    return;                }            }        }        /**        * 数组并非高度有序，使用快速排序,因为数组中有序数列的个数超过了MAX_RUN_COUNT        */        if(++count == MAX_RUN_COUNT) {sort(a, left, right, true);            return;        }    }    //检查特殊情况    if(run[count] == right++){// 最后一个有序数列只有最后一个元素        run[++count] =right; // 那给最后一个元素的后面加一个哨兵    } else if(count == 1) {// 整个数组中只有一个有序数列，说明数组已经有序啦，不需要排序了        return;    }    /**    * 创建合并用的临时数组。    * 注意： 这里变量right被加了1，它在数列最后一个元素位置+1的位置    * 这里没看懂，没发现后面的奇数处理和偶数处理有什么不同    */    int[] b; byte odd=0;    for(int n=1; (n <<= 1) < count; odd ^=1);    if(odd == 0) {b=a;a= new int[b.length];        for(int i=left -1; ++i < right; a[i] = b[i]);    } else {b=new int[a.length];    }    // 合并    // 最外层循环，直到count为1，也就是栈中待合并的序列只有一个的时候，标志合并成功    // a 做原始数组，b 做目标数组    for(int last; count > 1; count = last) {// 遍历数组，合并相邻的两个升序序列        for(int k = (last = 0) + 2; k <= count; k += 2) {// 合并run[k-2] 与 run[k-1]两个序列            int hi = run[k], mi = run[k - 1];            for(int i = run[k - 2], p = i,q = mi; i < hi; ++i){// 这里我给源码加了一个括号，这样好理解一点。 之前总觉得它会出现数组越界问题，                // 后来加了这个括号之后发现是没有问题的                if(q >= hi  ||  (p < mi && a[p] <= else="" count="" int="" i="right," lo="run[count" --i="">= lo; b[i] = a[i]);            run[++last] = right;        }        //临时数组，与原始数组对调，保持a做原始数组，b 做目标数组        int[] t = a; a = b; b = t;    }}int length = right - left + 1;// INSERTION_SORT_THRESHOLD为47，发现当要排序的个数小于47个时，采用插入排序，采用了哨兵方法，对于新元素从他前一个一个一个比较// Use insertion sort on tiny arraysif (length < INSERTION_SORT_THRESHOLD) {if (leftmost) {/*        * Traditional (without sentinel) insertion sort,        * optimized for server VM, is used in case of        * the leftmost part.        */        for (int i = left, j = i; i < right; j = ++i) {int ai = a[i + 1];            while (ai < a[j]) {a[j + 1] = a[j];                if (j-- == left) {break;                }            }            a[j + 1] = ai;        }    } else {/**        * 首先跨过开头的升序的部分        */        do {if(left > right) {return;            }        }while(a[++left] >= a[left - 1]);        /**        * 这里用到了成对插入排序方法，它比简单的插入排序算法效率要高一些        * 因为这个分支执行的条件是左边是有元素的        * 所以可以直接从left开始往前查找。        */        for(int k = left; ++left <= k="++left)" int="" a1="" a2="a[left];">=a2            if(a1 < a2) {a2 = a1; a1 = a[left];            }            //先把两个数字中较大的那个移动到合适的位置            while(a1 < a[--k]) {a[k + 2] = a[k]; //这里每次需要向左移动两个元素            }            a[++k + 1] = a1;            //再把两个数字中较小的那个移动到合适的位置            while(a2 < a[--k]) {a[k + 1] = a[k]; //这里每次需要向左移动一个元素            }            a[k + 1] = a2;        }        int last = a[right];        while(last < a[--right]) {a[right + 1] = last;        }        a[right + 1] = last;    }    return;}

至于大过INSERTION_SORT_THRESHOLD（47）的，用一种快速排序(双轴快排)的方法：

从数列中挑出五个元素，称为 “基准”（pivot）；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

总结：插入排序，快速排序，归并排序三种排序的组合

1.4、parallelSort

并行排序，JDK1.8增加的新方法

// 并行排序的最小数组长度private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;public static void parallelSort(int[] a) {int n = a.length, p, g;    // 如果数据的长度小于 MIN_ARRAY_SORT_GRAN（1 << 13）    if (n <= MIN_ARRAY_SORT_GRAN ||        // 或者当前并行度级别是 1的话，仍然使用常规的双轴快速排序        (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();}

2、搜索：binarySearch

主要用于快速从数组中查找对应的值，如果查找到了，返回的是对应数组的下标的值；如果查询不到则返回负数；

二分查找确保数组一定是有序的，否则可能找不到对应的数据

但是该方法有有一个问题：如果一个数组当中有多个元素，其无法保证匹配的到底是哪一个

// a：我们要搜索的数组，fromIndex：从那里开始搜索，默认是0； toIndex：搜索到何时停止，默认是数组大小// key：我们需要搜索的值 // c：外部比较器private staticint binarySearch0(T[] a, int fromIndex, int toIndex,                                     T key, Comparator c) {// 如果比较器 c 是空的，直接使用 key 的 Comparable.compareTo 方法进行排序    // 假设 key 类型是 String 类型，String 默认实现了 Comparable 接口，就可以直接使用 compareTo 方法进行排序    if (c == null) {// 这是另外一个方法，使用内部排序器进行比较的方法        return binarySearch0(a, fromIndex, toIndex, key);    }    int low = fromIndex;    int high = toIndex - 1;    // 开始位置小于结束位置，就会一直循环搜索    while (low <= low="0，high" mid="(low" int="">>> 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.}

3、数据拷贝：copyOf和copyRange

拷贝整个数组：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;}

拷贝部分数组：copyOfRange

// original 原始数组数据// from 拷贝起点// to 拷贝终点public static char[] copyOfRange(char[] original, int from, int to) {// 需要拷贝的长度    int newLength = to - from;    if (newLength < 0)        throw new IllegalArgumentException(from + " > " + to);    // 初始化新数组    char[] copy = new char[newLength];    // 调用 native 方法进行拷贝，参数的意思分别是：    // 被拷贝的数组、从数组那里开始、目标数组、从目的数组那里开始拷贝、拷贝的长度    System.arraycopy(original, from, copy, 0,                    Math.min(original.length - from, newLength));    return copy;}

基本上调用的是System.arrayCopy方法。

另外在在ArrayList的toArray方法中，其调用的也是Arrays里的copyOf方法，因为ArrayList的底层实现是数组；

4、数组填充：fill

5、数组转换为结婚：asList

public staticListasList(T... a) {    return new ArrayList<>(a);}

该方法有以下需要注意的：

其返回的集合不是java.util.ArrayList的实例，而是Array的内部类：java.util.Arrays.ArrayList；java.util.Arrays.ArrayList不能对集合进行增、删操作，其没有实现AbstractList类中的add、remove方法；常见使用方法是：Listlist = new ArrayList<>(Arrays.asList(T...a));，可以将其作为参数传到对应集合的构造方法里面；

二、Collections

为方便集合操作而产生的工具类。

Collections也提供sort和binarySearch方法，其sort方法底层调用就是Arrays.sort方法，而binarySearch底层重写了二分查找算法，实现逻辑和Arrays的二分查找算法一致

1、sort()方法实现

public staticvoid sort(Listlist)

1.1、JDK1.6

1.1.1、源码

// 基本方法public staticvoid sort(Listlist) {Object[] a = list.toArray();    Arrays.sort(a);    ListIteratori = list.listIterator();    for (int j=0; j<A.LENGTH; j++)="" {i.next();        i.set((T)a[j]);    }}/**********************下面方法未自Arrays***********************/// 调用 Arrays.sort(Object[] a) 排序方法，This algorithm offers guaranteed n*log(n) performance.public static void sort(Object[] a) {Object[] aux = (Object[])a.clone();    mergeSort(aux, a, 0, a.length, 0);}/** * Tuning parameter: list size at or below which insertion sort will be * used in preference to mergesort or quicksort. */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 */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; 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;}

1.2、JDK1.7

1.2.1、源码

public staticvoid sort(Listlist) {Object[] a = list.toArray();    Arrays.sort(a);    ListIteratori = list.listIterator();    for (int j=0; j<A.LENGTH; j++)="" {i.next();        i.set((T)a[j]);    }}//Arrays.sort方法public static void sort(Object[] a) {if (LegacyMergeSort.userRequested)        legacyMergeSort(a);    else        ComparableTimSort.sort(a);}static final class LegacyMergeSort {private static final boolean userRequested =        java.security.AccessController.doPrivileged(            new sun.security.action.GetBooleanAction(                "java.util.Arrays.useLegacyMergeSort")).booleanValue();}/** To be removed in a future release. */private static void legacyMergeSort(Object[] a) {Object[] aux = a.clone();    mergeSort(aux, a, 0, a.length, 0);}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;    }    // 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++];    }}/** * 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;}// ComparableTimSort

1.3、JDK1.8

2、集合的最大、最小值

max方法提供了两种实现

// 没有比较器的，那么默认非泛型必须实现了Comparable接口，否则编译的时候会报错，因为其底层是调用Comparable的compareTo方法来进行比较的；// 泛型必须继承Objec且实现Comparable接口；public staticT max(Collection coll) {Iterator i = coll.iterator();    T candidate = i.next();    while (i.hasNext()) {T next = i.next();        if (next.compareTo(candidate) > 0)            candidate = next;    }    return candidate;}// 带比较器，跟不带比较器的类似；public staticT max(Collection coll, Comparator comp) {if (comp==null)        return (T)max((Collection) coll);    Iterator i = coll.iterator();    T candidate = i.next();    while (i.hasNext()) {T next = i.next();        if (comp.compare(next, candidate) > 0)            candidate = next;    }    return candidate;}

3、多张类型的集合

Collections对原始集合进行了封装，提供了：线程安全的集合、不可变的集合；

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R1ReBn5L-1580104538820)(集合/image/Collections-InnerClass.png)]

3.1、线程安全的集合

线程安全的集合都是以Synchronized开头

SynchronizedListSynchronizedMapSynchronizedSetSynchronizedSortedMapSynchronizedSortedSet

上述线程安全的集合都是通过synchronized代码块来实现的，虽然都是线程安全的，但是在实际应用中避免使用这些类；

3.2、不可变集合

不可变集合都是Unmodifiable开头，这类方法的操作是会从原集合中得到一个不可变的新集合，新集合只能访问，不能修改；否则抛出异常；

UnmodifiableCollection：为只读集合

static class UnmodifiableListextends UnmodifiableCollectionimplements List{public E set(int index, E element) {// 抛出异常        throw new UnsupportedOperationException();    }    public void add(int index, E element) {// 抛出异常        throw new UnsupportedOperationException();    }    public E remove(int index) {// 抛出异常        throw new UnsupportedOperationException();    }    public int indexOf(Object o)            {return list.indexOf(o);}    public int lastIndexOf(Object o)        {return list.lastIndexOf(o);}    public boolean addAll(int index, Collection c) {// 抛出异常        throw new UnsupportedOperationException();    }    @Override    public void replaceAll(UnaryOperatoroperator) {// 抛出异常        throw new UnsupportedOperationException();    }    @Override    public void sort(Comparator c) {// 抛出异常        throw new UnsupportedOperationException();    }}

三、Objects

1、相等

主要有两个方法：deepEquals、equals，其中deepEquals主要是判断数组的，后面equals主要判断基本类型和自定义类型的

public static boolean deepEquals(Object a, Object b) {if (a == b)        return true;    else if (a == null || b == null)        return false;    else        return Arrays.deepEquals0(a, b);}public static boolean equals(Object a, Object b) {return (a == b) || (a != null && a.equals(b));}

2、判空

Objects.isNull(Object obj)Objects.nonNull(Object obj)Objects.requireNonNull(T obj)Objects.requireNonNull(T obj, String message)Objects.requireNonNull(T obj, SuppliermessageSupplier)