工具类特征:
构造器必须是私有的,工具类一般不需要初始化,可以直接使用;工具类的方法必须是被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)