java.util.Collections 是java集合框架中的一个工具类，主要用于Collectiont提供的通用算法，比如：排序(sort)、二分查找(binarySearch)、洗牌(shuffle)、旋转(rotate)
1. Collections.sort 排序
-
方法使用，代码测试
List<String> list = new ArrayList<String>(); list.add("7"); list.add("4"); list.add("8"); list.add("3"); list.add("9"); // 默认排序(正序) 测试结果为3, 4, 7, 8, 9 list.sort(); // Comparator排序 可以已定义正序、倒叙, 还可以支持以对象的某个字段进行排序 Collections.sort(list, new Comparator<String>() { @Override public int compare(String o1, String o2) { // 倒叙 正序的话 return o1.compareTo(o2); return o2.compareTo(o1); } }); // reverseOrder 倒叙 Collections.sort(list, Collections.<String>reverseOrder()); -
源码分析
Collections.sort集合排序最终调用的是
java.util包下Arrays类的Arrays.sort(T[] a, Comparator<? super T> c)，这个方法根据有没有传入Compararot c调用快速排序(sort())和优化的归并排序(TimSort.sort())，源码如下：public static <T> void sort(T[] a, Comparator<? super T> c){ if (c == null) { // 实际调用的是ComparableTimSort.sort sort(); } else { // 默认关闭 if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else TimSort.sort(a, 0, a.length, c, null, 0, 0); } } public static void sort(Object[] a) { // 默认关闭 if (LegacyMergeSort.userRequested) legacyMergeSort(a); else ComparableTimSort.sort(a, 0, a.length, null, 0, 0); }同时在快速排序和归并排序中，会判断个数是否大于32，从而选择分段排序和二分插入排序，部分源码如下：
// ComparableTimSort类 和TimSort类方法一样 static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) { // ... 省略代码 if (nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi); // 二分插入排序 binarySort(a, lo, hi, lo + initRunLen); return; } // 分段排序 }
2. Collections.binarySearch 二分查找
二分查找的前提是集合有序，否则不能满足二分算法的查找过程。
-
方法使用，代码测试
List<String> list = new ArrayList<String>(); list.add("1"); list.add("2"); list.add("3"); list.add("4"); list.add("5"); list.add("6"); list.add("7"); list.add("8"); // 二分查找, 传入list和需要查找的元素 int idx = Collections.binarySearch(list, "5"); // 输出4 System.out.println("二分查找：" + idx); -
源码分析
private static<T> binarySearch (List<? extends Comparable<? super T>> list, T key) { // list继承RandAccess或者list的大小小于二分查找最大阙值5000 if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD) // 调用下标二分查找 return Collections.indexedBinarySearch(list, key); else // 调用迭代器二分查找 考虑到LinkedList的get方法时间复杂度是O(n) return Collections.iteartorBinarySearch(list, key); } // 下标二分查找 private static <T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) { // 初始低位为0 int low = 0; // 初始高位为list.size() - 1 int high = list.size() - 1; // while循环低位小于等于高位 while(low <= high) { // 位运算获取中间下标 int mid = (low + high) >>> 1; // 获取中间下标元素 Comparable<? super T> midVal = list.get(mid); // 调用compareTo方法, 中间元素和寻找元素做对比 大于返回大于0, 小于返回小于0, 相等返回0 int cmp = midVal.compareTo(key); if (cmp < 0) // 小于0说明中间元素小于寻找元素, 说明寻找元素在右边, 低位 = 中间下标 + 1 low = mit + 1; else if (cmp > 0) // 大于0说明中间元素大于寻找元素, 说明寻找元素在左边, 高位 = 中间下标 - 1 high = mit - 1; else // 相等 找到该值 返回中间下标 return mid; } // 没有找到返回 -(low + 1) return -(low + 1); } // 迭代器二分查找, 原理和下标二分查找一样, 核心通过compareTo做比较查找元素, 区别就是在获取中间下标元素上 // 迭代器二分查找通过迭代器获取元素, 时间复杂度为O(n), 也做了优化,通过迭代器的下一个元素的下标和中间下标做比较, // 判断中间下标元素是在前面(previous)还是后面(next) private static <T> int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key) { // 初始低位为0 int low = 0; // 初始高位为集合大小 - 1 int high = list.size() - 1; // 获取集合迭代器 ListIterator<? extends Comparable<? super T>> i = list.listIterator(); // while循环低位小于等于高位 while (low <= high) { // 通过位运算获取中间下标 int mid = (low + high) >>> 1; // 通过迭代器获取中间下标元素值 Comparable<? super T> mitVal = get(i, mid); // 中间值和寻找值做对于 大于返回大于0, 小于返回小于0, 相等返回等于0 int cmp = mitVal.compareTo(key); if (cmp < 0) // 中间值小于寻找值, 说明寻找值在右边, 低位 = 中间下标 + 1 low = mid + 1; else if (cmp > 0) // 中间值大于寻找值, 说明寻找值在左边, 高位 = 中间下标 - 1 high = mid - 1; else // 找到该值 返回下标 return mid; } // 没有找到返回 -(low + 1) return -(low + 1); } // 迭代器获取中间下标元素 private static <T> T get(ListIterator<? extends T> i, int index) { T obj = null; // 迭代器下一个元素下标 int pos = i.nextIndex(); if (pos <= inde){ // 下一个元素下标值小于等于寻找下标值, 所以寻找下标值在链表的后面(next) do { obj = i.next(); } while (pos++ < index); } else { // 下一个元素下标值小于寻找下标值, 所以寻找下标值在链表的前面(prev) do { obj = i.previous(); } while (--pos > index); } return obj; } -
上面二分查找源码流程如下：
- 判断list是RandomAccess或者list的容量小于二分查找阙值5000，则调用下标二分查找，否则调用迭代器二分查找。
- 初始化低位为0，高位为
list.size()-1，while循环知道直到元素或者low > high - 通过位运算获取中间下标
(low + high) >>> 1返回mid - 通过
mid下标元素(二分查找直接通过list.get()获取，迭代器二分查找通过迭代器get()获取)。 - 中间元素和寻找元素调用
comparteTo()方法做比较返回cmp，如果cmp < 0，说明中间值小于寻找值，则寻找元素在右边，低位 =mid + 1，如果cmp > 0，说明中间值大于寻找值，则寻找元素在左边，高位 =mid - 1，如果mid = 0说明找到寻找元素，返回中间下标。
3. Collections.shuffle 洗牌算法
洗牌算法就是将List集合中的元素打乱，一般可以用于抽奖、摇号、洗牌等场景。
-
方法使用，代码测试
List<String> list = new ArrayList<String>(); list.add("1"); list.add("2"); list.add("3"); list.add("4"); list.add("5"); list.add("6"); list.add("7"); list.add("8"); //两种使用方式 一种是直接传入list //另一种还可以传入固定随机种子, 这种方式可以控制洗牌范围 Collections.shuffle(list); Collections.shuffle(list, new Random(100)); -
源码分析
public static void shuffle(List<?> list) { Random rnd = r; // 没有传入固定随机种子则初始化 if (rnd == null) r = rnd = new Random(); // 洗牌算法 shuffle(list, rnd); } public static void shuffle(List<?> list, Random rnd) { // 集合容量 int size = list.size(); // 集合容量小于洗牌阙值5 或者 是RandomAccess if (size < SHUFFLE_THRESHOLD || list.instanceof RandomAccess) { // for循环调用交换算法 for (int i = size; i > 1; i--) swap(list, i - 1, rnd.nextInt(i)); } else { // 集合容量大于洗牌阙值5, 且不是RandomAccess, 比如LindedList // 转成数组,对数组做调换操作, 不调用list的set方法主要是因为LindedList的set方法要获取传入下标的元素,获取元素 // 时间复杂度为O(n)性能低 Object[] arr = list.toArray(); // for循环对数组进行调换算法 for (int i = size; i > 1; i--) swap(arr, i - 1, rnd,nextInt(i)); // 通过迭代器进行元素的调换, 使用迭代器的set方法性能就是很高,因为可以通过迭代器获取元素 ListIterator it = list.listIterator(); for (int i = 0; i < arr.length; i++){ it.next(); it.set(arr[i]); } } } public static void swap (List<?> list, int i, int j){ final List l = list; // 通过list.set(int index, E e)方法进行元素调换, 该方法返回原元素 // 比如list(1, 2, 3, 4, 5, 6, 7, 8) i = 7, j = 0 // 首先 l.set(j, l.get(i)) 将下标为7的元素调到下位为0的位置,并返回元素1, 此时list为(8,2,3,4,5,6,7,8) // l.set(i, 1), 将元素1设置到下标7, 此时list为(8,2,3,4,5,6,7,1) // 这样子就完成了元素调换 l.set(i, l.set(j, l.get(i))); } public static void swap(Object[] arr, int i, int j) { // 下标i元素 Object tmp = arr[i]; // 将下标j元素赋值到下标i位置 arr[i] = arr[j]; // 下标i元素赋值到下标j位置 // 完成下标i, j的调换 arr[j] = tmp; } -
上面洗牌算法
shuffle(List<?> list, Random rnd)流程如下- 判断容量是否小于洗牌阙值
5或者是RandomAccess，来调用不同的调换算法 - 容量小于
5或者是RandomAccess，通过循环容量大小得到当前下标和随机下标，然后通过list.set(int index, E e)方法将两个下标元素调换。 - 如果容量大于
5且不是RandomAccess，通过将list转成数组，然后循环容量大小得到当前下标和随机下标，然后通过数组赋值调换元素，最后通过循环数组，通过list的迭代器将数组里面的元素赋值到list。
- 判断容量是否小于洗牌阙值
1.4 Collections.rotate 旋转算法
rotate旋转算法可以把ArrayList、LinkedList从指定的位置开始，进行顺时针或者逆时针旋转操作。
-
方法使用，代码测试
List<String> list = new ArrayList<String>(); list.add("1"); list.add("2"); list.add("3"); list.add("4"); list.add("5"); // 将list顺时针旋转2位, 逆时针旋转为负数 // 输出为 4,5,1,2,3 Collections.rotate(list, 2); // 输出为 3,4,5,1,2 Collections.rotate(list, -2); -
源码分析
public static void rotate(List<?> list, int distance) { if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD) rotate1(list, distance); else rotate2(list, distance); } private static <T> void rotate1(List<?> list, int distance) { // 集合容量 int size = list.size(); // 集合容量为0直接结束 if (size == 0) return; // 计算旋转的距离 distance = distance % size; if (distance < 0) distance += size; if (distance == 0) return; // for循环和do while,配合每次的旋转操作 for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) { // 旋转的元素 T displaced = list.get(cycleStart); // 旋转的元素下标 int i = cycleStart; do { i += distance; if (i > size) i -= size; // 通过list.set方法旋转元素 displaced = list.set(i, displaced); nMoved++; } while (i != cycleStart); } } private static <T> void rotate2(List<?> list, int distance) { int size = list.size(); if (size == 0) return; int mid = -distance % size; if (mid < 0) mid += size; if (mid == 0) return; reverse(list.subList(0, mid)); reverse(list.subList(mid, size)); reverse(list); } public static void reverse(List<?> list) { int size = list.size(); if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) { for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--) swap(list, i, j); } else { // instead of using a raw type here, it's possible to capture // the wildcard but it will require a call to a supplementary // private method ListIterator fwd = list.listIterator(); ListIterator rev = list.listIterator(size); for (int i=0, mid=list.size()>>1; i<mid; i++) { Object tmp = fwd.next(); fwd.set(rev.previous()); rev.set(tmp); } } }rotate1方法流程如下：- 判断集合容量，并计算旋转的距离。
-
for循环和do while配合每次的旋转，比如这里第一次会把0位置元素替换到2位置，此时list是1,2,1,4,5,do while中会判断i != cycleStart，当i == cycleStart的时候说明旋转全部的元素了，然后继续把被替换2位置的元素继续往下替换，比如这里第二次会把被替换2位置替换到4位置，此时list是1,2,1,4,3，直到一轮循环把所有元素都放置到正确位置。 - 移动的次数为
size表明list全部元素都旋转，结束for循环。
rotate2方法流程如下：该方法主要针对大于100个元素的LinkedList进行操作。- 定位拆链位置， distance % size + size ，也就是我们要旋转后找到的元素位置。
- 第一次翻转，把从位置 0 到拆链位置
- 第三次翻转，翻转整个链表。
1.5 Collections其他API
-
最大最小值，主要依赖compareTo方法比较大小
List<String> list = new ArrayList<String>(); list.add("1"); list.add("2"); list.add("3"); list.add("4"); list.add("5"); // 最小值 String min = Collections.min(list); // 最大值 String max = Collections.max(list); -
元素替换，会判断list是RandomAccess，小于替换阙值11，调用不同的替换值方法，一个是使用list的set方法，一个是使用迭代器的set方法。
List<String> list = new ArrayList<String>(); list.add("1"); list.add("2"); list.add("3"); list.add("4"); list.add("5"); Collections.replaceAll(list, "5", "6"); -
连续集合位置判断
List<String> list = new ArrayList<String>(); list.add("7"); list.add("4"); list.add("8"); list.add("3"); list.add("9"); // 返回2 int idx = Collections.indexOfSubList(list, Arrays.asList("8", "3")); -
synchronized方法，将非线程安全的集合转换成线程安全集合。Collections内部定义了静态类
SynchronizedList、SynchronizedMap，这两个类定义List、Map然后操作方法加锁List<String> list = Collections.synchronizedList(new ArrayList<String>()); Map<String, String> map = Collections.synchronizedMap(new HashMap<String, String>()
