Collection
Collection是List、Queue和Set的超集，它直接继承于Iterable，也就是所有的Collection集合类都支持for-each循环。
public interface Collection<E> extends Iterable<E> { //返回集合的长度，如果长度大于Integer.MAX_VALUE，返回 //返回集合的长度，如果长度大于Integer.MAX_VALUE，返回Integer.MAX_VALUE int size(); //如果集合元素总数为0，返回true boolean isEmpty(); //判断集合中是否包含指定的元素，其依据是equals()方法 boolean contains(Object o); //返回一个包含集合中所有元素的数组 Object[] toArray(); //与上个类似，只是增加了类型的转换 <T> T[] toArray(T[] a); //向集合中加入一个元素，如果成功加入则返回true，如果加入失败，或者因集合本身已经包含同个元素而不再加入时，返回false boolean add(E e); //从集合中删除指定元素的单个实例 boolean remove(Object o); //如果集合包含指定集合中的所有元素，返回true boolean containsAll(Collection<?> c); //把指定集合中的所有元素添加到集合中，但在此期间，如果指定的集合发生了改变，可能出现意想不到的事情 boolean addAll(Collection<? extends E> c); //从集合中删除所有包含在指定集合中的元素 boolean removeAll(Collection<?> c); //仅保留集合中包含在指定集合中的元素 boolean retainAll(Collection<?> c); //清空集合 void clear(); //将此方法抽象，是保证所有子类都覆写此方法，以保证equals的正确行为 boolean equals(Object o); //同上 int hashCode(); //这个方法在JDK1.8中提供了默认的实现，会使用Iterator的形式删除符合条件的元素 default boolean removeIf(Predicate<? super E> filter){ Objects.requireNonNull(filter); boolean removed = false; final Iterator<E> each = iterator(); while (each.hasNext()) { if (filter.test(each.next())) { each.remove(); removed = true; } } return removed; } }
Collections
Collections 是一个操作 Set、List 和 Map 等集合的工具类。Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法。
Collections 类中提供了多个 synchronizedXXX() 方法，该方法可使指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题。
static <T> Set<T> synchronizedSet(Set<T> s) { return new SynchronizedSet<>(s); }
Collections提供了三类方法返回一个不可变集合：
emptyXXX() ：返回一个空的只读集合 singleXXX()：返回一个只包含指定对象，只有一个元素，只读的集合。 unmodifiablleXXX()：返回指定集合对象的只读视图。
Collections提供了sort方法对集合进行排序：
public static <T> void sort(List<T> list)：将集合中元素按照默认规则排序。默认是升序 public static <T> void sort(List<T> list，Comparator<? super T> )：将集合中元素按照指定规则排序。
Comparator源码解析
示例：compare()结果小于0，顺序反转
class TimSort<T> { /** * * @param a the array to be sorted * @param lo the index of the first element, inclusive, to be sorted * @param hi the index of the last element, exclusive, to be sorted * @param c the comparator to use * @param work a workspace array (slice) 默认null * @param workBase origin of usable space in work array 默认0 * @param workLen usable size of work array 默认0 * @since 1.8 */ static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, T[] work, int workBase, int workLen) { assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length; int nRemaining = hi - lo; if (nRemaining < 2) return; // Arrays of size 0 and 1 are always sorted // If array is small, do a "mini-TimSort" with no merges. MIN_MERGE = 32 if (nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi, c); binarySort(a, lo, hi, lo + initRunLen, c); return; } /** * March over the array once, left to right, finding natural runs,extending short natural runs to minRun elements, and merging runs to maintain stack invariant. */ TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen); int minRun = minRunLength(nRemaining); do { // Identify next run int runLen = countRunAndMakeAscending(a, lo, hi, c); // If run is short, extend to min(minRun, nRemaining) if (runLen < minRun) { int force = nRemaining <= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen, c); runLen = force; } // Push run onto pending-run stack, and maybe merge ts.pushRun(lo, runLen); ts.mergeCollapse(); // Advance to find next run lo += runLen; nRemaining -= runLen; } while (nRemaining != 0); // Merge all remaining runs to complete sort assert lo == hi; ts.mergeForceCollapse(); assert ts.stackSize == 1; } /** * Returns the length of the run beginning at the specified position in the specified array and reverses the run if it is descending (ensuring that the run will always be * ascending when the method returns).对集合从第0位开始进行检查，如果在第p位出现前后顺序不一致（例如1,5,3），则停止检查，并返回p。如果第0位至第p位中compare(o1,o2)<0，则进行冒泡反转排序。确保结果升序 * * A run is the longest ascending sequence with: a[lo] <= a[lo + 1] <= a[lo + 2] <= ... * or the longest descending sequence with: a[lo] > a[lo + 1] > a[lo + 2] > ... * * For its intended use in a stable mergesort, the strictness of the definition of "descending" is needed so that the call can safely * reverse a descending sequence without violating stability. * * @param a the array in which a run is to be counted and possibly reversed * @param lo index of the first element in the run * @param hi index after the last element that may be contained in the run. It is required that {@code lo < hi}. * @param c the comparator to used for the sort * @return the length of the run beginning at the specified position in the specified array */ private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, Comparator<? super T> c) { assert lo < hi; int runHi = lo + 1; if (runHi == hi) return 1; // Find end of run, and reverse range if descending if (c.compare(a[runHi++], a[lo]) < 0) { // Descending 可以看到compare的第一个参数是集合中后面的数据，第二个参数是集合中前面的数 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) runHi++; reverseRange(a, lo, runHi); } else { // Ascending while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) runHi++; } return runHi - lo; } /** * Reverse the specified range of the specified array. 冒泡排序 * * @param a the array in which a range is to be reversed * @param lo the index of the first element in the range to be reversed * @param hi the index after the last element in the range to be reversed */ private static void reverseRange(Object[] a, int lo, int hi) { hi--; while (lo < hi) { Object t = a[lo]; a[lo++] = a[hi]; a[hi--] = t; } } /** * Sorts the specified portion of the specified array using a binary insertion sort. This is the best method for sorting small numbers of elements. * It requires O(n log n) compares, but O(n^2) data movement (worst case). * If the initial part of the specified range is already sorted, this method can take advantage of it: the method assumes that the * elements from index {@code lo}, inclusive, to {@code start}, exclusive are already sorted. * * @param a the array in which a range is to be sorted * @param lo the index of the first element in the range to be sorted * @param hi the index after the last element in the range to be sorted * @param start the index of the first element in the range that is * not already known to be sorted ({@code lo <= start <= hi}) * @param c comparator to used for the sort */ @SuppressWarnings("fallthrough") private static <T> void binarySort(T[] a, int lo, int hi, int start,Comparator<? super T> c) { assert lo <= start && start <= hi; if (start == lo) start++; for ( ; start < hi; start++) { T pivot = a[start]; // Set left (and right) to the index where a[start] (pivot) belongs int left = lo; int right = start; assert left <= right; /* * Invariants: * pivot >= all in [lo, left). * pivot < all in [right, start). */ while (left < right) { int mid = (left + right) >>> 1; if (c.compare(pivot, a[mid]) < 0) right = mid; else left = mid + 1; } assert left == right; /* * The invariants still hold: pivot >= all in [lo, left) and pivot < all in [left, start), so pivot belongs at left. Note * that if there are elements equal to pivot, left points to the first slot after them -- that's why this sort is stable. * Slide elements over to make room for pivot. */ int n = start - left; // The number of elements to move // Switch is just an optimization for arraycopy in default case switch (n) { case 2: a[left + 2] = a[left + 1]; case 1: a[left + 1] = a[left]; break; default: System.arraycopy(a, left, a, left + 1, n); } a[left] = pivot; } } }