Collcetions 工具类

热衷学习，热衷生活！😄

沉淀、分享、成长，让自己和他人都能有所收获！😄

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;
}

上面二分查找源码流程如下：
1. 判断list是RandomAccess或者list的容量小于二分查找阙值5000，则调用下标二分查找，否则调用迭代器二分查找。
2. 初始化低位为0，高位为list.size()-1，while循环知道直到元素或者low > high
3. 通过位运算获取中间下标(low + high) >>> 1 返回mid
4. 通过mid下标元素(二分查找直接通过list.get()获取，迭代器二分查找通过迭代器get()获取)。
5. 中间元素和寻找元素调用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)流程如下
1. 判断容量是否小于洗牌阙值5或者是RandomAccess，来调用不同的调换算法
2. 容量小于5或者是RandomAccess，通过循环容量大小得到当前下标和随机下标，然后通过list.set(int index, E e)方法将两个下标元素调换。
3. 如果容量大于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方法。
1
2
3
4
5
6
7
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然后操作方法加锁
1
2
List<String> list = Collections.synchronizedList(new ArrayList<String>());
Map<String, String> map = Collections.synchronizedMap(new HashMap<String, String>()