Java 集合框架系列十七：JDK 1.8 Collections 详解

蔚落 2022-12-05 02:16 213阅读 0赞

Collections 是在 JDK 1.2 时提供的用来操作集合的工具类，此类只包含对集合操作的静态方法。

## Collections API ##

public class Collections { 
        // 确保不可实例化
        private Collections() { 
        }
        
        /** * 这些属性是 Collections 的调优参数。通常 Collections 的许多算法都有两个实现， * 一个适用于随机访问，另一个适合顺序访问。通常随机访问在列表数据量小时可以获得很好的性能， * 这里的每个值代表了该操作使用随机访问的数据的阈值。而这些值的确定是根据以往的经验确定的， * 对 LinkedList 是很有效的。这里每个调优参数名的第一个词是它所应用的算法。 */
        private static final int BINARYSEARCH_THRESHOLD   = 5000;
        private static final int REVERSE_THRESHOLD        =   18;
        private static final int SHUFFLE_THRESHOLD        =    5;
        private static final int FILL_THRESHOLD           =   25;
        private static final int ROTATE_THRESHOLD         =  100;
        private static final int COPY_THRESHOLD           =   10;
        private static final int REPLACEALL_THRESHOLD     =   11;
        private static final int INDEXOFSUBLIST_THRESHOLD =   35;
    }

### Collections\#sort(List) &&Collections\#sort(List，Comparator<? super T>) ###

public static <T extends Comparable<? super T>> void sort(List<T> list) { 
            list.sort(null);
        } 	
    
    	public static <T> void sort(List<T> list, Comparator<? super T> c) { 
            list.sort(c);
        }

Collections 有两个 sort 方法，第一个方法是通过元素的自然顺序升序排序，要求 List 中的对象必须要实现了 Comparable 接口，而且传入的 List 必须是可修改的；而第二个方法则不要求实现 Comparable 接口，通过传入的自定义比较器排序，所以 List 中的元素必须能被 Comparator 比较，但两者底层实现都是通过 List 接口的默认方法 sort。

default void sort(Comparator<? super E> c) { 
            Object[] a = this.toArray();
            Arrays.sort(a, (Comparator) c);
            ListIterator<E> i = this.listIterator();
            for (Object e : a) { 
                i.next();
                i.set((E) e);
            }
        }

### Collections\#binarySearch(List<? extends Comparable<? super T>>, T) ###

使用二分查找算法查找对象。调用这个方法有两个前提：

1.  这个集合必须已经按照自然顺序升序
2.  这个集合的元素必须可以比较

如果没有排序，那查询出来的结果就没有什么意义。同样如果对象类型不同，无法进行比较将会抛出异常 ClassCastException。并且如果列表中包含要查询对象的多个重复对象，那么不保证每次找到的元素的位置相同。

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { 
            if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
                return Collections.indexedBinarySearch(list, key);
            else
                return Collections.iteratorBinarySearch(list, key);
        }

该方法会根据条件的不同调用两个私有的方法来进行查找。如果 **List 支持随机访问，并且小于二分查找的阈值 5000**，则调用indexedBinarySearch，时间复杂度是 log(n)，否则调用 iteratorBinarySearch 借助迭代器来进行访问，遍历的时间复杂度是 O(n)，比较的复杂度是 log(n)。

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;
                // 计算中间的元素值
                Comparable<? super T> midVal = list.get(mid);
                // 进行比较
                int cmp = midVal.compareTo(key);
    
                if (cmp < 0)
                    // 比传入的key小，需要继续在list的高位部分查找
                    low = mid + 1;
                else if (cmp > 0)
                    // 比传入的key大，需要继续在list的低位部分查询
                    high = mid - 1;
                else
                    // 相等，直接返回
                    return mid; // key found
            }
            // 没有找到，返回负数
            return -(low + 1);  // key not found
        }

而通过使用迭代器遍历的方式，则需要借助 Collections.get 方法来实现，这种实现会涉及到循环遍历，所以效率会稍微低些。

private static <T> int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key) { 
            int low = 0;
            int high = list.size()-1;
            // 通过ListIterator迭代器来进行查找
            ListIterator<? extends Comparable<? super T>> i = list.listIterator();
    
            while (low <= high) { 
                int mid = (low + high) >>> 1;
                 // 通过Collections.get方法获取中间索引处的元素值
                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
        }
    
    	private static <T> T get(ListIterator<? extends T> i, int index) { 
            T obj = null;
            // 获取下一个索引值
            int pos = i.nextIndex();
            // 循环判断获取的索引是否小于中间索引index
            // 如果小于，从前往后遍历，否则，从后往前遍历，最后返回元素值
            if (pos <= index) { 
                do { 
                    obj = i.next();
                } while (pos++ < index);
            } else { 
                do { 
                    obj = i.previous();
                } while (--pos > index);
            }
            return obj;
        }

### Collections\#binarySearch(List<? extends T>, T,Comparator<? super T>) ###

binarySearch 还有一个重载方法支持传入一个指定的比较器，可以在比较元素时使用指定的比较器进行比较。

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) { 
            if (c==null)
                return binarySearch((List<? extends Comparable<? super T>>) list, key);
    
            if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
                return Collections.indexedBinarySearch(list, key, c);
            else
                return Collections.iteratorBinarySearch(list, key, c);
        }
    
        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;
                T midVal = l.get(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
        }
    
        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);
                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
        }

### Collections\#reverse ###

列表反转方法，如果列表支持随机访问或者列表大小小于要反转的阈值18，则直接采用交换操作；否则采用双迭代操作，一个从头遍历，一个从尾遍历，然后交换。

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 { 
                // 迭代器遍历从头开始（forward）
                ListIterator fwd = list.listIterator();
                // 迭代器遍历从尾部开始（reverse）
                ListIterator rev = list.listIterator(size);
                for (int i=0, mid=list.size()>>1; i<mid; i++) { 
                    // 从头开始
                    Object tmp = fwd.next();
                    // 设置fwd下一个元素为rev前一个元素，交换
                    fwd.set(rev.previous());
                    rev.set(tmp);
                }
            }
        }

其中执行直接交换操作的 swap 方法很精妙，借助 List 的 set 方法返回旧值的属性，使用双重 set 方式来实现交换：

public static void swap(List<?> list, int i, int j) { 
            final List l = list;
            // 这里在设置j处为新的值的同时，会返回索引j处原来的值，然后再次set，很巧妙的实现了交换操作。
            l.set(i, l.set(j, l.get(i)));
        }

### Collections\#shuffle(List<?>) ###

shuffle 是重新洗牌的意思，该方法是将 list 原有数据打乱生成一个新的乱序列表。shuffle 方法再生成乱序列表的时候，所有元素发生交换可能性是近似相等的。

public static void shuffle(List<?> list) { 
            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();
            if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { 
                for (int i=size; i>1; i--)
                    swap(list, i-1, rnd.nextInt(i));
            } else { 
                // 转成数组进行处理
                Object arr[] = list.toArray();
    
                // 打乱顺序
                for (int i=size; i>1; i--)
                    swap(arr, i-1, rnd.nextInt(i));
    
                // 将数组放回列表中
                ListIterator it = list.listIterator();
                for (int i=0; i<arr.length; i++) { 
                    it.next();
                    it.set(arr[i]);
                }
            }
        }

从上面可以看出，如果列表支持随机访问或者列表大小小于重新打乱顺序的阈值 5，那么就进行交换。交换的规则是从当前列表的最后一个元素开始，依次和前面随机一个元素进行交换，这样交换整个列表，就可以认为这个列表是无序的。

如果列表不满足上述条件，就将列表先转为数组，然后按照相同的方式进行交换处理，最后再将数组放回列表中即可。

shuffle 还有另一个重载方法，可以传入指定种子数的 Random。也就是说一旦指定了种子数，那么每次将会产生相同的随机数，也就相当于这种随机生成的元素就是一种伪随机。我们可以根据需要调用相应的方法。

### fill(List<? super T> list, T obj) ###

将 List 的原有数据全部填充为一个固定的元素。同样也分两种情况，如果列表支持随机访问或者大小小于要填充的阈值，就直接遍历 List 进行 set操作即可；否则，使用 iterator 迭代器模式进行设值。

public static <T> void fill(List<? super T> list, T obj) { 
            int size = list.size();
    
            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);
                }
            }
        }

### copy(List<? super T> dest, List<? extends T> src) ###

将原集合中元素拷贝到另一个集合中。这里需要注意的一点就是，原列表的大小不能大于目标列表的大小。同样这里拷贝的方式也是有两种处理方式。

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");
    		// 同样分两种情况处理
            if (srcSize < COPY_THRESHOLD ||
                (src instanceof RandomAccess && dest instanceof RandomAccess)) { 
                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();
                for (int i=0; i<srcSize; i++) { 
                    di.next();
                    di.set(si.next());
                }
            }
        }

### min方法 && max方法 ###

min 方法返回指定集合的最小元素，根据自然顺序进行比较。需要注意的一点就是集合中的元素必须是可比较的（实现Comparable）。该方法通过使用迭代器迭代整个集合。

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();
                // 通过compareTo方法来进行比较
                if (next.compareTo(candidate) < 0)
                    candidate = next;
            }
            return candidate;
        }

该方法还有一个重载方法，可以指定比较器，实现相似

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

同理，max 方法是获取集合的最大元素，和 min 方法类似，也有两个重载方法。

### rotate(List<?> list, int distance) ###

对集合进行旋转操作，实际上就是集合里的元素右移操作，参数 distance 就是右移的距离。

public static void main(String[] args) { 
            List<Integer> list = new ArrayList<>();
            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.add(9);
            System.out.println("src list : " + list.toString()); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
            Collections.rotate(list, 2);
            System.out.println("rotate list : " + list.toString());// [8, 9, 1, 2, 3, 4, 5, 6, 7]
        }

右移两位就是将列表整体右移两位，最后两位移动到最前面而已。

public static void rotate(List<?> list, int distance) { 
            if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
                rotate1(list, distance);
            else
                rotate2(list, distance);
        }

rotate 方法也是分为两种情况，如果集合支持随机访问或者集合大小小于旋转的阈值，则执行 rotate1 操作；否则执行 rotate2 操作。

private static <T> void rotate1(List<T> list, int distance) { 
            int size = list.size();
            if (size == 0)
                return;
            // 距离取余，计算实际要移动距离
            distance = distance % size;
            // 考虑有可能是负数
            if (distance < 0)
                distance += size;
            if (distance == 0)
                return;
    		// 循环移动
            for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) { 
                T displaced = list.get(cycleStart);
                int i = cycleStart;
                do { 
                    // 通过distance来确定下标
                    i += distance;
                    if (i >= size)
                        i -= size;
                    displaced = list.set(i, displaced);
                    // nMoved是最终移动的次数
                    nMoved ++;
                } while (i != cycleStart);
            }
        }
    	// 需要借助于反转方法reverse方法来进行操作
        private static 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);
        }

rotate2 方法比较精妙。如果我们要对 \[1,2,3,4,5,6,7,8,9\] 进行 3 位旋转，则我们旋转的方式可以是：先对前 size-3 位进行反转，然后再对后 3 位进行反转，最后整体再进行反转就可以实现旋转的操作了。其中，mid 的值就是确定要前后反转的中间值。  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-91osbNLi-1599571087959)(G:\\学习记录\\Java 集合框架\\images\\微信截图\_20200901131928.png)\]][img-91osbNLi-1599571087959_G_Java _images_20200901131928.png]

### replaceAll(List list, T oldVal, T newVal) ###

替换集合中的某一个元素为新的元素，可以替换 null 元素。该方法同样分为两种操作，如果集合支持随机访问或者集合大小小于要替换的阈值大小，使用对象的 equals 方法加 lis t的 set 方法进行操作；否则，使用迭代器进行迭代操作。

public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) { 
            boolean result = false;
            int size = list.size();
            // 如果支持随机访问或者集合大小小于替换的阈值11
            if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) { 
                // 如果旧值为null
                if (oldVal==null) { 
                    // 遍历数组，将为null的都替换为新的值
                    for (int i=0; i<size; i++) { 
                        if (list.get(i)==null) { 
                            list.set(i, newVal);
                            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 { 
                // 获取迭代器，使用迭代器进行操作
                ListIterator<T> itr=list.listIterator();
                if (oldVal==null) { 
                    for (int i=0; i<size; i++) { 
                        if (itr.next()==null) { 
                            // 通过迭代器的set方法设置新值
                            itr.set(newVal);
                            result = true;
                        }
                    }
                } else { 
                    for (int i=0; i<size; i++) { 
                        if (oldVal.equals(itr.next())) { 
                            // 通过迭代器的set方法设置新值
                            itr.set(newVal);
                            result = true;
                        }
                    }
                }
            }
            return result;
        }

### indexOfSubList 方法 && lastIndexOfSubList方法 ###

查找集合包含子集合的下标索引，如果查找不到则返回 -1。indexOfSubList 是查找第一次出现的索引，而 lastIndexOfSubList 则是查找最后一次出现的索引。这两个方法的性能都不是太好，都是一种属于暴力搜索的算法，并且这里用到了 Java 中循环标签的概念。

public static int indexOfSubList(List<?> source, List<?> target) { 
            // 原集合大小
            int sourceSize = source.size();
            // 目标集合大小
            int targetSize = target.size();
            int maxCandidate = sourceSize - targetSize;
            // 如果原集合和目标集合都支持随机访问，或者原集合小于阈值
            if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
                (source instanceof RandomAccess&&target instanceof RandomAccess)) { 
            nextCand:
                // 双层遍历
                for (int candidate = 0; candidate <= maxCandidate; candidate++) { 
                    for (int i=0, j=candidate; i<targetSize; i++, j++)
                        if (!eq(target.get(i), source.get(j)))
                            // 使用循环标签跳转至最外层
                            continue nextCand;  // Element mismatch, try next cand
                    // 全部匹配，返回索引
                    return candidate;  
                }
            } else {   // Iterator version of above algorithm
                ListIterator<?> si = source.listIterator();
            nextCand:
                // 使用迭代器来进行循环
                for (int candidate = 0; candidate <= maxCandidate; candidate++) { 
                    ListIterator<?> ti = target.listIterator();
                    for (int i=0; i<targetSize; i++) { 
                        if (!eq(ti.next(), si.next())) { 
                            // 游标前移
                            for (int j=0; j<i; j++)
                                si.previous();
                            continue nextCand;
                        }
                    }
                    return candidate;
                }
            }
            // 查询不到，返回-1
            return -1;  
        }

### unmodifiable 系列方法 ###

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LGln9b3y-1599571087962)(G:\\学习记录\\Java 集合框架\\images\\微信截图\_20200901132422.png)\]][img-LGln9b3y-1599571087962_G_Java _images_20200901132422.png]

public static void main(String[] args) { 
            List<Integer> list = new ArrayList<> ();
            list.add(1);
            list.add(2);
            list.add(3);
            List list1 = Collections.unmodifiableList(list);
            list1.add(4);
            System.out.println(list1);// java.lang.UnsupportedOperationException
        }

Collections提供了一系列以 unmodifiable 开头的方法，用来在原集合基础上生成一个不可变的集合。

public static <T> List<T> unmodifiableList(List<? extends T> list) { 
            return (list instanceof RandomAccess ?
                    new UnmodifiableRandomAccessList<>(list) :
                    new UnmodifiableList<>(list));
        }
    
    	static class UnmodifiableList<E> extends UnmodifiableCollection<E>
                                      implements List<E> { 
            private static final long serialVersionUID = -283967356065247728L;
    
            final List<? extends E> list;
    
            UnmodifiableList(List<? extends E> list) { 
                super(list);
                this.list = list;
            }
    
            public boolean equals(Object o) { return o == this || list.equals(o);}
            public int hashCode()           { return list.hashCode();}
    
            public E get(int index) { return list.get(index);}
            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<? extends E> c) { 
                throw new UnsupportedOperationException();
            }
    
            @Override
            public void replaceAll(UnaryOperator<E> operator) { 
                throw new UnsupportedOperationException();
            }
            @Override
            public void sort(Comparator<? super E> c) { 
                throw new UnsupportedOperationException();
            }
    
            public ListIterator<E> listIterator()   { return listIterator(0);}
    
            public ListIterator<E> listIterator(final int index) { 
                return new ListIterator<E>() { 
                    private final ListIterator<? extends E> i
                        = list.listIterator(index);
    
                    public boolean hasNext()     { return i.hasNext();}
                    public E next()              { return i.next();}
                    public boolean hasPrevious() { return i.hasPrevious();}
                    public E previous()          { return i.previous();}
                    public int nextIndex()       { return i.nextIndex();}
                    public int previousIndex()   { return i.previousIndex();}
    
                    public void remove() { 
                        throw new UnsupportedOperationException();
                    }
                    public void set(E e) { 
                        throw new UnsupportedOperationException();
                    }
                    public void add(E e) { 
                        throw new UnsupportedOperationException();
                    }
    
                    @Override
                    public void forEachRemaining(Consumer<? super E> action) { 
                        i.forEachRemaining(action);
                    }
                };
            }
    
            public List<E> subList(int fromIndex, int toIndex) { 
                return new UnmodifiableList<>(list.subList(fromIndex, toIndex));
            }
    
            private Object readResolve() { 
                return (list instanceof RandomAccess
                        ? new UnmodifiableRandomAccessList<>(list)
                        : this);
            }
        }
    
    	static class UnmodifiableRandomAccessList<E> extends UnmodifiableList<E>
                                                  implements RandomAccess
        { 
            UnmodifiableRandomAccessList(List<? extends E> list) { 
                super(list);
            }
    
            public List<E> subList(int fromIndex, int toIndex) { 
                return new UnmodifiableRandomAccessList<>(
                    list.subList(fromIndex, toIndex));
            }
    
            private static final long serialVersionUID = -2542308836966382001L;
    
            /** * Allows instances to be deserialized in pre-1.4 JREs (which do * not have UnmodifiableRandomAccessList). UnmodifiableList has * a readResolve method that inverts this transformation upon * deserialization. */
            private Object writeReplace() { 
                return new UnmodifiableList<>(list);
            }
        }

可以看到在调用一些增删改方法的时候，直接抛异常来保证集合不可变。

### synchronized 系列方法 ###

![在这里插入图片描述][20200908212641953.png_pic_center]  
Collections 也提供了一系列以 synchronized 开头的方法，用来将原集合转成一个线程安全的集合。

public static <T> List<T> synchronizedList(List<T> list) { 
            return (list instanceof RandomAccess ?
                    new SynchronizedRandomAccessList<>(list) :
                    new SynchronizedList<>(list));
        }
    
    	static class SynchronizedList<E>
            extends SynchronizedCollection<E>
            implements List<E> { 
            private static final long serialVersionUID = -7754090372962971524L;
    
            final List<E> list;
    
            SynchronizedList(List<E> list) { 
                super(list);
                this.list = list;
            }
            SynchronizedList(List<E> list, Object mutex) { 
                super(list, mutex);
                this.list = list;
            }
    
            public boolean equals(Object o) { 
                if (this == o)
                    return true;
                synchronized (mutex) { return list.equals(o);}
            }
            public int hashCode() { 
                synchronized (mutex) { return list.hashCode();}
            }
    
            public E get(int index) { 
                synchronized (mutex) { return list.get(index);}
            }
            public E set(int index, E element) { 
                synchronized (mutex) { return list.set(index, element);}
            }
            public void add(int index, E element) { 
                synchronized (mutex) { list.add(index, element);}
            }
            public E remove(int index) { 
                synchronized (mutex) { return list.remove(index);}
            }
    
            public int indexOf(Object o) { 
                synchronized (mutex) { return list.indexOf(o);}
            }
            public int lastIndexOf(Object o) { 
                synchronized (mutex) { return list.lastIndexOf(o);}
            }
    
            public boolean addAll(int index, Collection<? extends E> c) { 
                synchronized (mutex) { return list.addAll(index, c);}
            }
    
            public ListIterator<E> listIterator() { 
                return list.listIterator(); // Must be manually synched by user
            }
    
            public ListIterator<E> listIterator(int index) { 
                return list.listIterator(index); // Must be manually synched by user
            }
    
            public List<E> subList(int fromIndex, int toIndex) { 
                synchronized (mutex) { 
                    return new SynchronizedList<>(list.subList(fromIndex, toIndex),
                                                mutex);
                }
            }
    
            @Override
            public void replaceAll(UnaryOperator<E> operator) { 
                synchronized (mutex) { list.replaceAll(operator);}
            }
            @Override
            public void sort(Comparator<? super E> c) { 
                synchronized (mutex) { list.sort(c);}
            }
    
            private Object readResolve() { 
                return (list instanceof RandomAccess
                        ? new SynchronizedRandomAccessList<>(list)
                        : this);
            }
        }

可以看到，synchronizedList 底层调用了 Collections 的静态内部类 SynchronizedList。SynchronizedList 内部的每个方法基本都使用了 synchronized关键字，mutex 是要同步的对象，位于 SynchronizedCollection 中。

### checked 系列方法 ###

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kjRhu5NR-1599571087966)(G:\\学习记录\\Java 集合框架\\images\\微信截图\_20200901132928.png)\]][img-kjRhu5NR-1599571087966_G_Java _images_20200901132928.png]  
Collections 提供了一系列以 checked 开头的方法，用于获取动态类型安全的集合，常用于泛型相关操作。比如说当我们想往集合中插入一组数据的时候，除了可以明确指定数据的类型（List），也可以使用 Collections 的 checked 方法来检查类型安全。

public static void main(String[] args) { 
            List list = new ArrayList<> ();
            list.add(1);
            list.add(2);
            list.add(3);
            // 将list1的对象设置为了字符串类型
            List list1 = Collections.checkedList(list, String.class);
            list1.add(4);
            System.out.println(list1); // ClassCastException
        }

需要注意的是，checked 方法只会检查新插入的元素，并不会校验列表中已经存在的元素。如果我们有需要，可以新创建一个新的 checked 列表，并调用 addAll 方法重新插入所有元素进行校验。

### empty 系列方法 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]  
Collections 也提供了一系列以 empty 开头的方法，用户获取空的集合。获取到的集合是无法修改的。一般用于接口返回空的数据。

public static final List EMPTY_LIST = new EmptyList<>();
    	public static final <T> List<T> emptyList() { 
            return (List<T>) EMPTY_LIST;
        }
        // 静态内部类
        private static class EmptyList<E>
            extends AbstractList<E>
            implements RandomAccess, Serializable { 
            private static final long serialVersionUID = 8842843931221139166L;
    
            public Iterator<E> iterator() { 
                return emptyIterator();
            }
            public ListIterator<E> listIterator() { 
                return emptyListIterator();
            }
    
            public int size() { return 0;}
            public boolean isEmpty() { return true;}
    
            public boolean contains(Object obj) { return false;}
            public boolean containsAll(Collection<?> c) {  return c.isEmpty(); }
    
            public Object[] toArray() {  return new Object[0]; }
    
            public <T> T[] toArray(T[] a) { 
                if (a.length > 0)
                    a[0] = null;
                return a;
            }
    
            public E get(int index) { 
                throw new IndexOutOfBoundsException("Index: "+index);
            }
    
            public boolean equals(Object o) { 
                return (o instanceof List) && ((List<?>)o).isEmpty();
            }
    
            public int hashCode() {  return 1; }
    
            @Override
            public boolean removeIf(Predicate<? super E> filter) { 
                Objects.requireNonNull(filter);
                return false;
            }
            @Override
            public void replaceAll(UnaryOperator<E> operator) { 
                Objects.requireNonNull(operator);
            }
            @Override
            public void sort(Comparator<? super E> c) { 
            }
    
            // Override default methods in Collection
            @Override
            public void forEach(Consumer<? super E> action) { 
                Objects.requireNonNull(action);
            }
    
            @Override
            public Spliterator<E> spliterator() {  return Spliterators.emptySpliterator(); }
    
            // Preserves singleton property
            private Object readResolve() { 
                return EMPTY_LIST;
            }
        }

### frequency(Collection<?> c, Object o) ###

该方法用于获取某一个元素在集合中出现的次数，并且可以统计 null，底层通过增强 for 循环比较来实现。

public static int frequency(Collection<?> c, Object o) { 
            int result = 0;
            if (o == null) { 
                for (Object e : c)
                    if (e == null)
                        result++;
            } else { 
                for (Object e : c)
                    if (o.equals(e))
                        result++;
            }
            return result;
        }

### disjoint(Collection<?> c1, Collection<?> c2) ###

disjoint 方法用于判断两个指定的集合是否互斥，即是否没有共同的元素，如果没有共同的元素，说明互斥返回 true，如果有说明不互斥，返回 false。

public static boolean disjoint(Collection<?> c1, Collection<?> c2) { 
            Collection<?> contains = c2;
            Collection<?> iterate = c1;
    
            // Performance optimization cases. The heuristics:
            // 1. Generally iterate over c1.
            // 2. If c1 is a Set then iterate over c2.
            // 3. If either collection is empty then result is always true.
            // 4. Iterate over the smaller Collection.
            if (c1 instanceof Set) { 
                // Use c1 for contains as a Set's contains() is expected to perform
                // better than O(N/2)
                iterate = c2;
                contains = c1;
            } else if (!(c2 instanceof Set)) { 
                // Both are mere Collections. Iterate over smaller collection.
                // Example: If c1 contains 3 elements and c2 contains 50 elements and
                // assuming contains() requires ceiling(N/2) comparisons then
                // checking for all c1 elements in c2 would require 75 comparisons
                // (3 * ceiling(50/2)) vs. checking all c2 elements in c1 requiring
                // 100 comparisons (50 * ceiling(3/2)).
                int c1size = c1.size();
                int c2size = c2.size();
                if (c1size == 0 || c2size == 0) { 
                    // At least one collection is empty. Nothing will match.
                    return true;
                }
    
                if (c1size > c2size) { 
                    iterate = c2;
                    contains = c1;
                }
            }
            // 遍历iterate集合，然后通过contains方法比较
            for (Object e : iterate) { 
                if (contains.contains(e)) { 
                   // 发现了相同的元素，直接返回false
                    return false;
                }
            }
    
            // 没有发现相同的元素
            return true;
        }

底层使用了两个临时变量 contain s和 iterate，iterate 适合于数据量小的集合，因为要遍历 iterate，而 contains 适用于数据量大的集合，因为可以使用集合的 contains 方法。这样做的原因是 contains 方法的复杂度要比遍历 iterate 的复杂度低，这是一种简单的优化方式。

### addAll(Collection<? super T> c, T… elements) ###

用于向集合中添加多个元素，其中 elements 是一个可变参数，可以传递多个值。底层通过循环调用集合的 add 方法来实现，然后通过位与运算来返回是否添加成功。

public static <T> boolean addAll(Collection<? super T> c, T... elements) { 
            boolean result = false;
            for (T element : elements)
                result |= c.add(element);
            return result;
        }

### newSetFromMap(Map<E, Boolean> map) ###

这个方法是基于指定的 Map 对象创建一个新的 Set 对象，它持有这个 Map 对象的引用，并且可以保持 Map 的顺序，并发和性能特征。在调用该方法时，指定的 map 对象必须是空的，并且对象的 value 属性是 boolean 类型。一般对这个类的最佳实践如下：

Set<String> concurrentSet = Collections.newSetFromMap(new IdentityHashMap<String, Boolean>());

由于在`java.util.concurrent`包下没有线程安全的 ConcurrentHashSet 的实现，我们可以借助于ConcurrentHashMap 来实现，而另一种实现方式就是通过这个方法；

Set<String> concurrentSet = Collections.newSetFromMap(new ConcurrentHashMap<String, Boolean>());

### reverseOrder() ###

返回对象集合排序的自然排序的逆序，通常我们可以如下使用：

public static void main(String[] args) { 
            List<Integer> list = new ArrayList<>();
            list.add(1);
            list.add(5);
            list.add(3);
            System.out.println(list); // [1, 5, 3]
            Collections.sort(list, Collections.reverseOrder());
            System.out.println(list);// [5, 3, 1]
        }

该方法也有一个重载方法，该方法就是返回我们所传入的比较器的逆序排序比较器。

public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)

### 其他方法 ###

Collections 中还有一些方法，比如 `singletonList(T o)`，返回包含指定对象的不可变列表；`asLifoQueue` 将 Deque 转成后进先出（LIFO）队列，也就是栈结构；`nCopies`，返回包含指定对象的 n 个不可变的列表；

public static void main(String[] args) { 
            List<String> list = Collections.nCopies(5, "Java");
            for (String object : list) { 
                System.out.println("object : " + object);
            }
        }
    	// object : Java
    	   object : Java
           object : Java
           object : Java
    	   object : Java

[img-91osbNLi-1599571087959_G_Java _images_20200901131928.png]: /images/20221123/2e33c383bb074b99a9840be0b48dc3a4.png
[img-LGln9b3y-1599571087962_G_Java _images_20200901132422.png]: /images/20221123/3e83eea82df1417085de40bb09158a89.png
[20200908212641953.png_pic_center]: /images/20221123/111b8e776ead4dd58eda7ef6782e30be.png
[img-kjRhu5NR-1599571087966_G_Java _images_20200901132928.png]: /images/20221123/9f0e3310ea3747ce8bf3db9ef34ba62a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d8d1d1ac38a146e5b1fad275d4686ef9.png