Java源码分析之Collections类

绝地灬酷狼 2023-05-31 12:23 13阅读 0赞

### 文章目录 ###

*   *  概述
     *  常用方法
     *   *  1. addAll
         *  2. reverse
         *  3. shuffle
         *  4. sort
         *  5. swap
         *  6. max
         *  7. min
         *  8. frequency
         *  9. copy
         *  10. replaceAll
         *  11. binarySearch
         *  12. rotate
         *  13. indexOfSubList
         *  14. lastIndexOfSubList
         *  15. nCopies
         *  16. fill

## 概述 ##

Collections 类提供一些常用方法

## 常用方法 ##

*  addAll：将指定元素加入到指定集合中
 *  reverse：反转指定 List 中元素的顺序
 *  shuffle：对 List 集合元素进行随机排序
 *  sort：排序
 *  swap：交换 list 中指定两个位置的元素
 *  max：返回给定集合中的最大元素
 *  min：返回给定集合中的最小元素
 *  frequency：返回指定集合中指定元素的出现次数
 *  copy：将 src 中的内容复制到 dest 中
 *  replaceAll：将列表中出现的所有指定值替换为另一个值
 *  binarySearch：使用二分搜索法在指定列表中搜索指定对象
 *  rotate：将指定列表元素按指定距离旋转
 *  indexOfSubList：返回目标列表在指定列表第一次出现的起始位置，如果未找到，返回 -1
 *  lastIndexOfSubList：返回目标列表在指定列表最后一次出现的起始位置，如果未找到，返回 -1
 *  nCopies：返回 n 个指定对象的副本组成的不可变列表
 *  fill：将指定 list 的元素全部替换为指定值

分类：

*  增：addAll、nCopies
 *  改：reverse、shuffle、sort、swap、copy、replaceAll、rotate、fill
 *  查：max、min、frequency、binarySearch、indexOfSubList、lastIndexOfSubList

### 1. addAll ###

将指定元素加入到指定集合中

**声明**

public static <T> boolean addAll(Collection<? super T> c, T... elements)

**参数**

*  c：元素要插入的集合
 *  elements：可变参数列表，要插入到 c 中的元素

**返回值**

*  true：当调用该方法使集合发生变化

**异常**

*  UnsupportedOperationException：如果 c 不支持 add() 方法
    
        String[] strArr = {
              "1","2","3"};
        List<String> l1 = Arrays.asList(strArr);
        // 抛出UnsupportedOperationException异常，原因是asList返回的是Arrays的内部类ArrayList
        // 而不是 java.util.ArrayList
        Collections.addAll(l1, "2");
 *  NullPointerException：当 c 不允许空值而 elements 含有一个或多个 null 值，另一种情况是 c 或者 elements 为空
    
        List<String> list = null;
        // 抛出NullPointerException异常，因为list为空
        Collections.addAll(list, "1", "2", "3");
 *  IllegalArgumentException：elements 中值的某些属性不能加入 c
    
    //TODO

**使用示例**

代码

public void addAllTest() {
        
        List<String> list = new ArrayList<>();
        list.add("1");
        list.add("1");
        System.out.println("使用addAll之前：" + list);
        boolean b = Collections.addAll(list, "2", "2");
        System.out.println("使用addAll之后：" + list + "，返回值为：" + b);
    }

输出

使用addAll之前：[1, 1]
    使用addAll之后：[1, 1, 2, 2]，返回值为：true

**源码分析**

public static <T> boolean addAll(Collection<? super T> c, T... elements) {
        
        // 原始结果为 false
        boolean result = false;
        // 遍历elements可变参数列表
        for (T element : elements)
            // 按位或，只有同为 false，结果才为 false
            // 只有全部 element 加入失败，才会返回 false
            result |= c.add(element);
        return result;
    }

### 2. reverse ###

反转指定 List 中元素的顺序

**声明**

public static void reverse(List<?> list)

**参数**

*  list：指定被翻转的列表

**返回值**

void

**异常**

*  UnsupportedOperationException：如果指定 list 或者其迭代器不支持 set 操作
    
        List<String> list = Collections.nCopies(4, "hhhh");
        // 抛出UnsupportedOperationException异常，nCopies返回的是一个Collections类中的静态内部类
        // 该静态内部类不存在set方法
        Collections.reverse(list);

**使用示例**

代码

public void reverseTest() {
        
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println("使用reverse之前：" + list);
    
        Collections.reverse(list);
    
        System.out.println("使用reverse之后：" + list);
    }

输出

使用reverse之前：[a, b, c]
    使用reverse之后：[c, b, a]

**源码分析**

public static void reverse(List<?> list) {
        
        // 得到 list 中元素个数
        int size = list.size();
        // private static final int REVERSE_THRESHOLD  = 18;
        // List 接口下的子类中，ArrayList 和 Vector 实现了 RandomAccess 接口
        // 如果元素个数小于 18，或者该 List 实现了 RandomAccess 接口，就进行此类反转
        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 传递的参数是索引
            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);
            }
        }
    }

### 3. shuffle ###

对 List 集合元素进行随机排序

**声明**

public static void shuffle(List<?> list);
    public static void shuffle(List<?> list, Random rnd);

**参数**

*  list：将要进行随机排序的列表
 *  rnd：指定用于随机排列列表的随机数

**返回值**

void

**异常**

**使用示例**

代码

public void shuffleTest() {
        
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
        
            list.add(i);
        }
        System.out.print("使用shuffle之前：" + list);
        System.out.println();
        Collections.shuffle(list);
        System.out.print("使用shuffle之后：" + list);
        System.out.println();
        Collections.shuffle(list,new Random());
        System.out.print("使用带随机种子的shuffle之后：" + list);
        System.out.println();
        Collections.shuffle(list,new Random());
        System.out.print("使用带随机种子的shuffle之后：" + list);
    }

输出

使用shuffle之前：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    使用shuffle之后：[9, 6, 1, 8, 4, 7, 3, 2, 5, 0]
    使用带随机种子的shuffle之后：[1, 6, 5, 9, 4, 0, 2, 3, 7, 8]
    使用带随机种子的shuffle之后：[0, 4, 9, 7, 1, 3, 8, 2, 6, 5]

**源码分析**

public static void shuffle(List<?> list) {
        
        // private static Random r;
        Random rnd = r;
        // 参数如果为空，初始化参数
        if (rnd == null)
            r = rnd = new Random(); // harmless race.
        // 调用重载方法
        shuffle(list, rnd);
    }
    public static void shuffle(List<?> list, Random rnd) {
        
        // 得到元素个数
        int size = list.size();
        // private static final int SHUFFLE_THRESHOLD  =  5;
        // 元素个数小于 5，或者该 List 实现了 RandomAccess 接口，直接进行随机打乱
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        
            // nextInt(i) 生成 [0,i)之间的数
            // 每次 i-1 位置的数和 nextInt(i) 生成的位置的数互换
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
        
            // 将 list 元素转存进 arr 数组
            Object arr[] = list.toArray();
    
            // Shuffle array
            // 转存数组后随机排序，和上面一样
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));
    
            // Dump array back into list
            // 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
            // 利用迭代器把随机排序后的数组转存回原 list
            ListIterator it = list.listIterator();
            for (Object e : arr) {
        
                it.next();
                it.set(e);
            }
        }
    }

### 4. sort ###

对指定 list 按默认升序或传递的比较器顺序排序

**声明**

public static <T extends Comparable<? super T>> void sort(List<T> list)
    public static <T> void sort(List<T> list, Comparator<? super T> c)

**参数**

*  list：要排序的列表
 *  c：指定列表的排序规则，如果是 null，则为默认升序

**返回值**

void

**异常**

*  ClassCastException：如果列表中的元素不能相互比较
    
        List list = new ArrayList<>();
        list.add(1);
        list.add("2");
        // ClassCastException String和Integer类型不可以互相比较
        Collections.sort(list);
 *  UnsupportedOperationException：如果指定列表的列表迭代器不支持 set 操作
    
    // TODO
 *  IllegalArgumentException：如果检测到列表元素的自然顺序违反了可比较的约定

**使用示例**

代码

public void sortTest() {
        
        List<Integer> list = new ArrayList<>();
        list.add(5);
        list.add(2);
        list.add(7);
        System.out.println("使用sort之前：" + list);
        Collections.sort(list);
        System.out.println("使用sort之后：" + list);
        // 降序
        Collections.sort(list, new Comparator<Integer>() {
        
            @Override
            public int compare(Integer o1, Integer o2) {
        
                return o2 - o1;
            }
        });
        System.out.println("使用sort之后：" + list);
    }

输出

使用sort之前：[5, 2, 7]
    使用sort之后：[2, 5, 7]
    使用sort之后：[7, 5, 2]

**源码**

// Collections 中的sort
    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        
        // 调用 List 接口下的sort
        list.sort(null);
    }
    public static <T> void sort(List<T> list, Comparator<? super T> c) {
        
        // 调用 List 接口下的sort，传入比较器
        list.sort(c);
    }

// List 接口中的sort
    default void sort(Comparator<? super E> c) {
        
        // 将 list 转存到数组中
        Object[] a = this.toArray();
        // 调用 Arrays 类的 sort
        Arrays.sort(a, (Comparator) c);
        // 调用迭代器，将排好序的数组存回 list
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
        
            i.next();
            i.set((E) e);
        }
    }

// Arrays类中的sort
    public static <T> void sort(T[] a, Comparator<? super T> c) {
        
        // 迭代器为null时，调用不使用迭代器的方法
        if (c == null) {
        
            sort(a);
        } else {
        
            // 兼容老版本，当用户设置时，使用
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                // 调用 TimSort 类的 sort
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

之后太复杂了，几乎涉及了 TimSort 类的所有方法，暂时 //TODO，之后专门分析这个类

### 5. swap ###

交换指定 list 的 i、j 位置元素

**声明**

public static void swap(List<?> list, int i, int j)

**参数**

*  list：要交换位置的列表
 *  i：要交换的一个元素的索引值
 *  j：要交换的另一个元素的索引值

**返回值**

void

**异常**

*  IndexOutOfBoundsException：如果 i 或 j 超出范围（i<0 || i>=list.size() || j<0 || j>=list.size()）
    
        List<Integer> list = new ArrayList<>();
        list.add(5);
        // 抛出IndexOutOfBoundsException异常
        Collections.swap(list,-1,5);

**使用示例**

代码

public void swapTest(){
        
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println("使用swap之前：" + list);
        Collections.swap(list,0,1);
        System.out.println("使用swap之后：" + list);
    }

输出

使用swap之前：[1, 2, 3, 4]
    使用swap之后：[2, 1, 3, 4]

**源码分析**

public static void swap(List<?> list, int i, int j) {
        
        // 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
        final List l = list;
        // 被final修饰的引用本身不可改变，但是引用所指的对象可以改变
        // l.get(i)，得到 i 位置上的值
        // l.set(j, l.get(i))，将得到的值赋值到 j 位置，并返回原来 j 位置的旧值
        // l.set(i, l.set(j, l.get(i)))，把得到的 j 的旧值赋值到 i 位置
        l.set(i, l.set(j, l.get(i)));
    }

### 6. max ###

根据元素自然顺序或根据给定比较器规则返回最大值

**声明**

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
    public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)

**参数**

*  coll：要返回最大值的集合
 *  comp：自定义比较器

**返回值**

*  T：给定集合按自然顺序或者自定义比较器规则得到的最大值

**异常**

*  ClassCastException：如果集合元素间不可互相比较
    
        HashSet integers = new HashSet<>();
        integers.add(5);
        integers.add("3");
        // 抛出ClassCastException异常，Integer和String无法比较
        Collections.max(integers);
 *  NoSuchElementException：如果集合为空
    
        HashSet integers = new HashSet<>();
        // 抛出NoSuchElementException异常，集合为空
        Collections.max(integers);

**使用示例**

代码

public void maxTest() {
        
        List<Integer> list1 = new ArrayList<>();
        list1.add(5);
        list1.add(1);
        List<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("D");
        System.out.println("list1中最大值为：" + Collections.max(list1));
        System.out.println("list2中最大值为：" + Collections.max(list2));
    }

输出

list1中最大值为：5
    list2中最大值为：a

**源码分析**

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
        
        // 拿到迭代器
        Iterator<? extends T> i = coll.iterator();
        // 第一个值作为备选项
        T candidate = i.next();
    
        // 逐个比较，如果存在更大的元素就替换备选项
        while (i.hasNext()) {
        
            T next = i.next();
            if (next.compareTo(candidate) > 0)
                candidate = next;
        }
        // 返回
        return candidate;
    }
    public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
        
        // 如果比较器为null，调用另一个max方法
        if (comp==null)
            return (T)max((Collection) coll);
    
        // 拿到迭代器
        Iterator<? extends T> i = coll.iterator();
        T candidate = i.next();
    
        while (i.hasNext()) {
        
            T next = i.next();
            // 使用迭代器的 compare方法
            if (comp.compare(next, candidate) > 0)
                candidate = next;
        }
        return candidate;
    }

### 7. min ###

根据元素自然顺序或根据给定比较器规则返回最小值

**声明**

public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
    public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)

**参数**

*  coll：要返回最小值的集合
 *  comp：自定义比较器

**返回值**

*  T：给定集合按自然顺序或者自定义比较器规则得到的最小值

**异常**

*  ClassCastException：如果集合元素间不可互相比较
    
        HashSet integers = new HashSet<>();
        integers.add(5);
        integers.add("3");
        // 抛出ClassCastException异常，Integer和String无法比较
        Collections.min(integers);
 *  NoSuchElementException：如果集合为空
    
        HashSet integers = new HashSet<>();
        // 抛出NoSuchElementException异常，集合为空
        Collections.min(integers);

**使用示例**

代码

public void minTest() {
        
        List<Integer> list1 = new ArrayList<>();
        list1.add(5);
        list1.add(1);
        List<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("D");
        System.out.println("list1中最小值为：" + Collections.min(list1));
        System.out.println("list2中最小值为：" + Collections.min(list2));
    }

输出结果

list1中最小值为：1
    list2中最小值为：D

**源码分析**

public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {
        
        // 拿到迭代器
        Iterator<? extends T> i = coll.iterator();
        T candidate = i.next();
    
        while (i.hasNext()) {
        
            T next = i.next();
            // next < candidate，更新 candidate
            if (next.compareTo(candidate) < 0)
                candidate = next;
        }
        return candidate;
    }
    public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
        
        // 如果比较器为null，使用默认自然顺序取最小值
        if (comp==null)
            return (T)min((Collection) coll);
    
        Iterator<? extends T> i = coll.iterator();
        T candidate = i.next();
    
        while (i.hasNext()) {
        
            T next = i.next();
            // 调用比较器的compare方法
            if (comp.compare(next, candidate) < 0)
                candidate = next;
        }
        return candidate;
    }

### 8. frequency ###

返回指定集合中指定元素的出现次数

**声明**

public static int frequency(Collection<?> c, Object o)

**参数**

*  c：需要确定频率的指定集合
 *  o：频率待指定的元素

**返回值**

int：c 中等于 o 的元素数目

**异常**

*  NullPointerException：c 为 null
    
        ArrayList<Object> list = null;
        // 抛出NullPointerException异常
        Collections.frequency(list,1);

**使用示例**

代码

public void frequencyTest(){
        
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("A");
        list.add("A");
        list.add("B");
        list.add("B");
        list.add("C");
        System.out.println("使用frequency得到的结果是：" + Collections.frequency(list,"A"));
    }

输出

使用frequency得到的结果是：3

**源码分析**

public static int frequency(Collection<?> c, Object o) {
        
        int result = 0;
        // 如果o为null，判断集合中有多少元素等于null
        if (o == null) {
        
            for (Object e : c)
                if (e == null)
                    result++;
        } else {
        
            // 否则调用equals判等
            for (Object e : c)
                if (o.equals(e))
                    result++;
        }
        return result;
    }

### 9. copy ###

将一个列表的所有内容复制到另一个列表中

**声明**

public static <T> void copy(List<? super T> dest, List<? extends T> src)

**参数**

*  dest：目标列表
 *  src：源列表

**返回值**

void

**异常**

*  IndexOutOfBoundsException：如果目标列表太小，不足以容纳源列表
    
        ArrayList<Integer> dest = new ArrayList<>();
        ArrayList<Integer> src = new ArrayList<>();
        src.add(1);
        src.add(2);
        // 抛出IndexOutOfBoundsException异常，因为 dest.size()<src.size()
        Collections.copy(dest,src);
 *  UnsupportedOperationException：如果目标列表的迭代器不支持 set 操作
    
    //TODO

**使用示例**

代码

public void copyTest(){
        
        ArrayList<String> dest = new ArrayList<>();
        ArrayList<String> src = new ArrayList<>();
        dest.add("1");
        dest.add("2");
        dest.add("3");
        src.add("6");
        src.add("7");
        System.out.println("未使用copy之前：" + dest);
        Collections.copy(dest,src);
        System.out.println("使用copy之后：" + dest);
    }

输出结果

未使用copy之前：[1, 2, 3]
    使用copy之后：[6, 7, 3]

**源码分析**

public static <T> void copy(List<? super T> dest, List<? extends T> src) {
        
        // 源列表集合的大小
        int srcSize = src.size();
        // 如果目标列表集合个数小于源列表集合个数，抛出异常
        if (srcSize > dest.size())
            throw new IndexOutOfBoundsException("Source does not fit in dest");
    
        // private static final int COPY_THRESHOLD = 10;
        // 如果源列表集合大小小于10，或者源列表和目标列表都实现了RandomAccess接口
        // 使用直接 set 的方式复制
        if (srcSize < COPY_THRESHOLD ||
            (src instanceof RandomAccess && dest instanceof RandomAccess)) {
        
            // 从下标0开始，复制源列表到目标列表
            for (int i=0; i<srcSize; i++)
                dest.set(i, src.get(i));
        } else {
        
            // 否则使用迭代器
            ListIterator<? super T> di=dest.listIterator();
            ListIterator<? extends T> si=src.listIterator();
            // 也是从下标0开始，将源列表复制到目标列表
            for (int i=0; i<srcSize; i++) {
        
                di.next();
                di.set(si.next());
            }
        }
    }

### 10. replaceAll ###

将列表中出现的所有指定值替换为另一个值

**声明**

public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)

**参数**

*  list：要进行替换的列表
 *  oldVal：要被替换的值
 *  newVal：取代oldVal的值

**返回值**

当list包含一个或多个oldVal时，返回"true"，否则返回"false"

**异常**

*  UnsupportedOperationException：如果目标列表的迭代器不支持 set 操作
    
    //TODO

**使用示例**

代码

public void replaceAllTest(){
        
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("a");
        list.add("b");
        list.add("a");
        list.add("c");
        System.out.println("使用replaceAll之前：" + list);
        System.out.println("成功替换后返回：" + Collections.replaceAll(list,"b","h"));
        System.out.println("使用replaceAll之后：" + list);
        System.out.println("未成功替换时，返回：" + Collections.replaceAll(list,"b","h"));
    }

输出结果

使用replaceAll之前：[a, a, b, a, c]
    成功替换后返回：true
    使用replaceAll之后：[a, a, h, a, c]
    未成功替换时，返回：false

**源码分析**

public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
        
        // 声明返回值为false
        boolean result = false;
        // 列表大小
        int size = list.size();
        //  private static final int REPLACEALL_THRESHOLD = 11;
        // 如果列表大小小于11，或者当前list实现了RandomAccess接口
        if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
        
            // 考虑oldVal为null的情况
            if (oldVal==null) {
        
                for (int i=0; i<size; i++) {
        
                    if (list.get(i)==null) {
        
                        // 在旧值的位置赋值新值
                        list.set(i, newVal);
                        // 返回值置为true
                        result = true;
                    }
                }
            } else {
        
                // 返回值不为 null时，调用equals方法比较
                for (int i=0; i<size; i++) {
        
                    if (oldVal.equals(list.get(i))) {
        
                        list.set(i, newVal);
                        result = true;
                    }
                }
            }
        } else {
         // 列表大小大于等于11，且该list未实现RandomAccess接口，调用迭代器替换
            ListIterator<T> itr=list.listIterator();
            // oldVal为null的情况
            if (oldVal==null) {
        
                for (int i=0; i<size; i++) {
        
                    if (itr.next()==null) {
        
                        itr.set(newVal);
                        result = true;
                    }
                }
            } else {
         // oldVal不为null的情况
                for (int i=0; i<size; i++) {
        
                    if (oldVal.equals(itr.next())) {
        
                        itr.set(newVal);
                        result = true;
                    }
                }
            }
        }
        return result;
    }

### 11. binarySearch ###

使用二分搜素法在指定列表搜索指定对象。

在调用该方法之前，事先必须根据自然顺序或比较器顺序按升序排序，否则不确保能得到正确的答案。

且当列表存在等于指定对象的多个元素，则不能保证找到哪个元素

**声明**

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
    public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

**参数**

*  list：要搜索的列表
 *  key：要查找的元素
 *  c：用于排序列表的比较器

**返回值**

如果key存在list中，返回key所在索引；如果不存在，返回 ( - ( 插入点位置 ) - 1)

**异常**

*  ClassCastException：如果传入的key与list元素不能互相比较
    
        List list = new ArrayList<>();
        list.add("1");
        list.add("3");
        // 抛出ClassCastException异常，Integer和String无法互相比较
        Collections.binarySearch(list,2);

**使用示例**

代码

public void binarySearchTest() {
        
        List<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(6);
        System.out.println("查找2的索引为：" + Collections.binarySearch(list, 2));
        // 如果没找到，返回 ( -(插入点位置) - 1)
        // 插入位置应该是 5，-5-1 = -6
        System.out.println("查找5的索引为：" + Collections.binarySearch(list, 5));
    }

输出结果

查找2的索引为：2
    查找5的索引为：-6

**源码分析**

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        
        // private static final int BINARYSEARCH_THRESHOLD = 5000;
        // 如果该list实现了RandomAccess接口，或者该list的大小小于5000
        // 使用索引二分搜索法
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else // 否则使用迭代器二进制搜索法
            return Collections.iteratorBinarySearch(list, key);
    }
    
    public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
        
        // 如果比较器为null，调用另一个二分搜索法
        if (c==null)
            return binarySearch((List<? extends Comparable<? super T>>) list, key);
    
        // private static final int BINARYSEARCH_THRESHOLD = 5000;
        // 如果该list实现了RandomAccess接口，或者该list的大小小于5000
        // 使用索引二分搜索法，并传入比较器c
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key, c);
        else // 否则使用迭代器二进制搜索法，并传入比较器c
            return Collections.iteratorBinarySearch(list, key, c);
    }

// 不带比较器的indexedBinarySearch
    private static <T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
        
        // 二分搜索法
        int low = 0;
        int high = list.size()-1;
    	
        while (low <= high) {
        
            // 中间索引
            int mid = (low + high) >>> 1;
            // 用list的get方法查找中间值
            Comparable<? super T> midVal = list.get(mid);
            // 比较中间值
            int cmp = midVal.compareTo(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
    }
    
    // 带比较器的indexedBinarySearch
    private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
        
        //  二分搜索法
        int low = 0;
        int high = l.size()-1;
    
        while (low <= high) {
        
            int mid = (low + high) >>> 1;
            //用list的get方法查找中间值
            T midVal = l.get(mid);
            // 这用的是比较器的compare方法
            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
    }

// 不带比较器的iteratorBinarySearch
    private static <T> int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
    {
        
        int low = 0;
        int high = list.size()-1;
        ListIterator<? extends Comparable<? super T>> i = list.listIterator();
    
        while (low <= high) {
        
            int mid = (low + high) >>> 1;
            // 从迭代器中返回中间值
            Comparable<? super T> midVal = get(i, mid);
            // 比较中间值
            int cmp = midVal.compareTo(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
    }
    // 带比较器的iteratorBinarySearch
    private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
        
        int low = 0;
        int high = l.size()-1;
        ListIterator<? extends T> i = l.listIterator();
    
        while (low <= high) {
        
            int mid = (low + high) >>> 1;
            // 从迭代器中返回中间值
            T midVal = get(i, mid);
            // 调用迭代器的compare方法
            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
    }

// 从迭代器中返回中间值的方法
    // 通过重定位指定列表，获取指定位置元素
    private static <T> T get(ListIterator<? extends T> i, int index) {
        
        T obj = null;
        // 返回后序调用next将返回的元素的索引
        int pos = i.nextIndex();
        if (pos <= index) {
          // 如果 pos 小，往后找
            do {
        
                obj = i.next();
            } while (pos++ < index);
        } else {
         // 如果 pos 大，往前找
            do {
        
                obj = i.previous();
            } while (--pos > index);
        }
        // 找到值返回
        return obj;
    }

### 12. rotate ###

将指定列表元素按指定距离旋转。

距离为正时，列表元素整体向右移动，超出列表元素大小的元素依次左补齐；反之

**声明**

public static void rotate(List<?> list, int distance)

**参数**

*  list：要被旋转的列表
 *  distance：要旋转列表的距离

**返回值**

void

**异常**

*  UnsupportedOperationException：如果目标列表的迭代器不支持 set 操作
    
    //TODO

**使用示例**

代码

public void rotateTest() {
        
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
        
            list.add(i);
        }
        System.out.println("未使用rotate前：" + list);
        Collections.rotate(list, 3);
        System.out.println("使用rotate右移3位后：" + list);
        Collections.rotate(list, -3);
        System.out.println("使用rotate左移3位后：" + list);
        Collections.rotate(list, 13);
        System.out.println("使用rotate右移13位后：" + list);
    }

输出结果

未使用rotate前：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    使用rotate右移3位后：[7, 8, 9, 0, 1, 2, 3, 4, 5, 6]
    使用rotate左移3位后：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    使用rotate右移13位后：[7, 8, 9, 0, 1, 2, 3, 4, 5, 6]

**源码分析**

public static void rotate(List<?> list, int distance) {
        
        // private static final int ROTATE_THRESHOLD = 100;
        // 如果该list实现了RandomAccess接口，或者该list的大小小于100
        if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
            rotate1(list, distance);
        else
            rotate2(list, distance);
    }

private static <T> void rotate1(List<T> list, int distance) {
        
        // 得到list的大小
        int size = list.size();
        // 大小为0直接返回
        if (size == 0)
            return;
        // 对distance取余，减少旋转次数
        distance = distance % size;
        // 如果distance小于0，加上size，使distance落在[0,size)上
        if (distance < 0)
            distance += size;
        // distance为0没有旋转的必要，直接返回
        if (distance == 0)
            return;
    
        for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
        
            // 拿到cycleStart位置的值
            T displaced = list.get(cycleStart);
            // 存下cycleStart
            int i = cycleStart;
            // 直接将数放到最终位置
            do {
        
                // 找到cycleStart旋转后的落脚点
                i += distance;
                // 如果超过列表大小，减回来，使i落在[0,size)中
                if (i >= size)
                    i -= size;
                // 在新位置赋值原来cycleStart位置的值，并拿到旧值
                displaced = list.set(i, displaced);
                nMoved ++;
            } while (i != cycleStart);
        }
    }

private static void rotate2(List<?> list, int distance) {
        
        // 得到list的大小
        int size = list.size();
        // 大小为0没有翻转的必要
        if (size == 0)
            return;
        // distance 是需要从列表后面移到列表前的数的个数
        // mid 计算的是移动后依然还处于列表后面的数
        // ex：1 2 3 4 5，distance = 2
        // mid 是指 1 2 3，这 3 个数未被重新移动到列表开头
        int mid =  -distance % size;
        if (mid < 0)
            mid += size;
        if (mid == 0)
            return;
    
        // 通过mid进行划分，根据线性代数原理
        // ((AB)^T)^T = AB = (B^TA^T)^T
        // 逆转 [0,mid)
        reverse(list.subList(0, mid));
        // 逆转 [mid,size)
        reverse(list.subList(mid, size));
        // 逆转整个列表
        reverse(list);
    }

### 13. indexOfSubList ###

返回目标列表在指定列表第一次出现的起始位置，如果未找到，返回 -1

**声明**

public static int indexOfSubList(List<?> source, List<?> target)

**参数**

*  source：搜索target第一次出现的列表
 *  target：要在source中作为子列表搜索的列表

**返回值**

返回target在source中首次出现的下标，如果target未找到，返回-1

**异常**

无

**使用示例**

代码

public void indexOfSubListTest() {
        
         List<Integer> source = new ArrayList<>();
         for (int i = 0; i < 10; i++) {
        
             source.add(i);
         }
         source.add(2);
         source.add(3);
         List<Integer> target = new ArrayList<>();
         target.add(2);
         target.add(3);
         System.out.println("target在srouce中第一次出现：" + Collections.indexOfSubList(source, target));
         target.add(6);
         System.out.println("target在source未出现：" +  Collections.indexOfSubList(source, target));
     }

输出结果

目标list在srouce中第一次出现：2
    如果目标list在source未出现：-1

**源码分析**

public static int indexOfSubList(List<?> source, List<?> target) {
        
        int sourceSize = source.size();
        int targetSize = target.size();
        // 最大需要比较的长度
        int maxCandidate = sourceSize - targetSize;
    
        // private static final int INDEXOFSUBLIST_THRESHOLD = 35;
        // 如果 source的大小大于35，或者source和target都实现了RandomAccess接口
        if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
            (source instanceof RandomAccess&&target instanceof RandomAccess)) {
        
            // 标签
            nextCand:
            // candidate 从 0 开始
            for (int candidate = 0; candidate <= maxCandidate; candidate++) {
        
                for (int i=0, j=candidate; i<targetSize; i++, j++)
                    // 如果 target.get(i)和source.get(j)不相等，结束此次以ij为变量的循环
                    if (!eq(target.get(i), source.get(j)))
                        continue nextCand;  // Element mismatch, try next cand
                // 如果全都相等，直接返回索引
                return candidate;  // All elements of candidate matched target
            }
        } else {
          // Iterator version of above algorithm
            // 否则使用迭代器
            ListIterator<?> si = source.listIterator();
            nextCand:
            // candidate 从 0 开始
            for (int candidate = 0; candidate <= maxCandidate; candidate++) {
        
                ListIterator<?> ti = target.listIterator();
                for (int i=0; i<targetSize; i++) {
        
                    // 如果不相等，迭代器回退
                    if (!eq(ti.next(), si.next())) {
        
                        // Back up source iterator to next candidate
                        for (int j=0; j<i; j++)
                            si.previous();
                        continue nextCand;
                    }
                }
                return candidate;
            }
        }
        // 未找到，返回 -1
        return -1;  // No candidate matched the target
    }

static boolean eq(Object o1, Object o2) {
        
        return o1==null ? o2==null : o1.equals(o2);
    }

### 14. lastIndexOfSubList ###

返回目标列表在指定列表最后一次出现的起始位置，如果未找到，返回 -1

**声明**

public static int lastIndexOfSubList(List<?> source, List<?> target)

**参数**

*  source：搜索target最后一次出现的列表
 *  target：要在source中作为子列表搜索的列表

**返回值**

返回target在source中最后一次出现的下标，如果target未找到，返回-1

**异常**

无

**使用示例**

代码

public void lastIndexOfSubListTest() {
        
         List<Integer> source = new ArrayList<>();
         for (int i = 0; i < 10; i++) {
        
             source.add(i);
         }
         source.add(2);
         source.add(3);
         List<Integer> target = new ArrayList<>();
         target.add(2);
         target.add(3);
         System.out.println("target在srouce中最后一次出现：" + Collections.lastIndexOfSubList(source, target));
         target.add(6);
         System.out.println("target在source未出现：" + Collections.lastIndexOfSubList(source, target));
     }

输出结果

target在srouce中最后一次出现：10
    target在source未出现：-1

**源码分析**

public static int lastIndexOfSubList(List<?> source, List<?> target) {
        
        int sourceSize = source.size();
        int targetSize = target.size();
        // 最大需要比较的长度
        int maxCandidate = sourceSize - targetSize;
    
        // private static final int INDEXOFSUBLIST_THRESHOLD = 35;
        // source大小小于35，或者source实现了RandomAccess接口
        if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
            source instanceof RandomAccess) {
           // Index access version
            // 标签
            nextCand:
            // candidate 从最大需要比较的长度maxCandidate开始
            for (int candidate = maxCandidate; candidate >= 0; candidate--) {
        
                for (int i=0, j=candidate; i<targetSize; i++, j++)
                    // 如果target.get(i)和source.get(j)不等，该ij循环结束，继续下一轮candidate循环
                    if (!eq(target.get(i), source.get(j)))
                        continue nextCand;  // Element mismatch, try next cand
                // 找到了直接返回，所以是最后一个
                return candidate;  // All elements of candidate matched target
            }
        } else {
          // Iterator version of above algorithm
            // sourceSize<targetSize，肯定找不到，直接返回-1
            if (maxCandidate < 0)
                return -1;
            // 使用迭代器指向maxCandidate位置
            ListIterator<?> si = source.listIterator(maxCandidate);
            nextCand:
            // candidate从maxCandidate开始
            for (int candidate = maxCandidate; candidate >= 0; candidate--) {
        
                ListIterator<?> ti = target.listIterator();
                for (int i=0; i<targetSize; i++) {
        
                    // 如果不等，退出此轮i循环，且迭代器回退
                    if (!eq(ti.next(), si.next())) {
        
                        if (candidate != 0) {
        
                            // Back up source iterator to next candidate
                            for (int j=0; j<=i+1; j++)
                                si.previous();
                        }
                        continue nextCand;
                    }
                }
                return candidate;
            }
        }
        // 没找到返回-1
        return -1;  // No candidate matched the target
    }

// 和 indexOfSubList用的同一个eq方法
    static boolean eq(Object o1, Object o2) {
        
        return o1==null ? o2==null : o1.equals(o2);
    }

### 15. nCopies ###

返回 n 个指定对象的副本组成的不可变列表

**声明**

public static <T> List<T> nCopies(int n, T o)

**参数**

*  n：返回列表中元素的个数
 *  o：返回列表中重复出现的元素

**返回值**

由 n 个 o 组成的不可变列表

**异常**

*  IllegalArgumentException：如果 n < 0
    
        // 抛出IllegalArgumentException异常
        Collections.nCopies(-2,1);

**使用示例**

代码

public void nCopiesTest(){
        
        List<String> list1 = Collections.nCopies(4, "hhhh");
        System.out.println("list1得到的是：" + list1);
        List<Integer> list2 = Collections.nCopies(3, 2);
        System.out.println("list2得到的是：" + list2);
    }

输出结果

list1得到的是：[hhhh, hhhh, hhhh, hhhh]
    list2得到的是：[2, 2, 2]

**源码分析**

public static <T> List<T> nCopies(int n, T o) {
        
        // n<0抛出异常
        if (n < 0)
            throw new IllegalArgumentException("List length = " + n);
        // 创建一个静态内部类
        return new CopiesList<>(n, o);
    }

private static class CopiesList<E> extends AbstractList<E> implements RandomAccess, Serializable{
        
        private static final long serialVersionUID = 2739099268398711800L;
    
        // 该类的两个成员变量都被 final 修饰
        final int n;
        final E element;
    
        // 构造方法中已经初始化两个成员变量
        // 所以该类的 n 和 element已不可变
        CopiesList(int n, E e) {
        
            assert n >= 0;
            this.n = n;
            element = e;
        }
    
        public int size() {
        
            return n;
        }
    
        public boolean contains(Object obj) {
        
            return n != 0 && eq(obj, element);
        }
    
        public int indexOf(Object o) {
        
            return contains(o) ? 0 : -1;
        }
    
        public int lastIndexOf(Object o) {
        
            return contains(o) ? n - 1 : -1;
        }
    
        public E get(int index) {
        
            if (index < 0 || index >= n)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+n);
            return element;
        }
    
        public Object[] toArray() {
        
            final Object[] a = new Object[n];
            if (element != null)
                Arrays.fill(a, 0, n, element);
            return a;
        }
    
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) {
        
            final int n = this.n;
            if (a.length < n) {
        
                a = (T[])java.lang.reflect.Array
                    .newInstance(a.getClass().getComponentType(), n);
                if (element != null)
                    Arrays.fill(a, 0, n, element);
            } else {
        
                Arrays.fill(a, 0, n, element);
                if (a.length > n)
                    a[n] = null;
            }
            return a;
        }
    
        public List<E> subList(int fromIndex, int toIndex) {
        
            if (fromIndex < 0)
                throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
            if (toIndex > n)
                throw new IndexOutOfBoundsException("toIndex = " + toIndex);
            if (fromIndex > toIndex)
                throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                                   ") > toIndex(" + toIndex + ")");
            return new CopiesList<>(toIndex - fromIndex, element);
        }
    
        // Override default methods in Collection
        @Override
        public Stream<E> stream() {
        
            return IntStream.range(0, n).mapToObj(i -> element);
        }
    
        @Override
        public Stream<E> parallelStream() {
        
            return IntStream.range(0, n).parallel().mapToObj(i -> element);
        }
    
        @Override
        public Spliterator<E> spliterator() {
        
            return stream().spliterator();
        }
    }

### 16. fill ###

将指定 list 的元素全部替换为指定值

**声明**

public static <T> void fill(List<? super T> list, T obj)

**参数**

*  list：要进行元素替换的列表
 *  obj：用于填充指定值的元素

**返回值**

void

**异常**

*  UnsupportedOperationException：如果指定 list 或者其迭代器不支持 set 操作
    
        List<Integer> list = Collections.nCopies(4,2);
        // 抛出UnsupportedOperationException异常，nCopies返回的是一个Collections类中的静态内部类
        // 该静态内部类不存在set方法
        Collections.fill(list,1);

**代码示例**

代码

public void fillTest() {
        
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
        
            list.add(i);
        }
        System.out.println("使用fill方法前：" + list);
        Collections.fill(list, 1);
        System.out.println("使用fill方法后：" + list);
    }

输出结果

使用fill方法前：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    使用fill方法后：[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

**源码分析**

public static <T> void fill(List<? super T> list, T obj) {
        
        int size = list.size();
    
        //  private static final int FILL_THRESHOLD = 25;
        // list的大小小于25或者该list实现了 RandomAccess 接口，使用for循环覆盖
        if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
        
            for (int i=0; i<size; i++)
                list.set(i, obj);
        } else {
        
            // 否则使用迭代器覆盖
            ListIterator<? super T> itr = list.listIterator();
            for (int i=0; i<size; i++) {
        
                itr.next();
                itr.set(obj);
            }
        }
    }