Java Collections源码剖析
Collections以静态方法的方式提供了很多通用算法和功能，这些功能大概可以分为以下两类。
一类是对容器接口对象进行操作，包括查找、排序、添加和修改。
另一类返回一个容器接口对象，适配器：将其他类型的数据转换为容器接口对象+装饰器：修饰一个给定容器接口对象，增加某种性质。
操作容器
查找
Arrays类有针对数组对象的二分查找方法，而Collections提供了针对List接口的二分查找，如下所示：
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的每个元素实现Comparable接口，另一个不需要，但要求提供Comparator。二分查找假定List中的元素是从小到大排序的。List的二分查找的基本思路与Arrays中的是一样的，数组可以根据索引直接定位任意元素，实现效率很高，但List就不一定了，具体分为两种情况，如果List可以随机访问（如数组），即实现了RandomAccess接口，或者元素个数比较少，则实现思路与Arrays一样，根据索引直接访问中间元素进行比较，否则使用选代器的方式移动到中间元素进行比较。从效率角度，如果List支持随机访问，效率O(log2(N)),如果通过选代器，那么比较的次数为O(log2(N)),但遍历移动的次数为O(N),N为列表长度。
此外Collections提供了如下查找最大值/最小值的方法，实现思路也很简单，就是通过迭代器进行比较：
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;
}
还可以查找元素出现次数，返回元素o在容器c中出现的次数，o可以为null，实现思路就是通过迭代器进行比较计数。
public static int frequency(Collection<?> c, Object o)Collections还提供了查找元素位置的方法，在List中查找target的位置：
public static int indexOfSubList(List<?> source, List<?> target)
public static int lastIndexOfSubList(List<?> source, List<?> target)indexOfSubList从开头找，lastIndexOfSubList从结尾找，没找到返回-1，找到返回第一个匹配元素的索引位置。这两个方法的实现都是属于“暴力破解”型的，将target列表与source从第一个元素开始的列表逐个元素进行比较，如果不匹配，则与source从第二个元素开始的列表比较，再不匹配，与source从第三个元素开始的列表比较，以此类推。
排序
针对List接口对象，Collections除了提供基础的排序，还提供了若干调整顺序的方法，包括交换元素位置、翻转列表顺序、随机化重排、循环移位等。
Arrays类有针对数组对象的排序方法，Collections提供了针对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)内部是通过Arrays.sort实现的，先将List元素复制到一个数组中，然后使用Arrays.sort,排序后，再复制回List。代码如下所示：
public static <T extends Comparable<? super T>> void sort(List<T> list) {Object[] a = list.toArray();Arrays.sort(a);ListIterator<T> i = list.listIterator();for(int j=0; j<a.length; j++) {i.next();i.set((T)a[j]);}
}
交换元素位置的方法为：
public static void swap(List<?> list, int i, int j)交换List中第i个和第j个元素的内容。实现代码为：
public static void swap(List<?> list, int i, int j) {final List l = list;l.set(i, l.set(j, l.get(i)));
}
翻转列表顺序的方法为：
public static void reverse(List<?> list)将List中的元素顺序翻转过来。实现思路就是将第一个和最后一个交换，第二个和倒数第二个交换，以此类推，直到中间两个元素交换完毕。如果List实现了RandomAccess接口或列表比较小，根据索引位置，使用上面的swap方法进行交换，否则，由于直接根据索引位置定位元素效率比较低，使用一前一后两个listIterator定位待交换的元素，具体代码为：
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 {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);}}
}Collections还直接提供了对List元素洗牌的方法：
public static void shuffle(List<?> list)
public static void shuffle(List<?> list, Random rnd)实现思路为：从后往前遍历列表，逐个给每个位置重新赋值，值从前面的未重新赋值的元素中随机挑选。如果列表实现了RandomAccess接口，或者列表比较小，直接使用前面swap方法进行交换，否则，先将列表内容复制到一个数组中，洗牌，再复制回列表。代码为：
public static <T> void shuffle(List<T> list, Random rnd) {int size = list.size();if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {for (int i = size; i > 1; i--) {int swapIndex = rnd.nextInt(i);Collections.swap(list, i - 1, swapIndex);}} else {Object[] arr = list.toArray();for (int i = size; i > 1; i--) {int swapIndex = rnd.nextInt(i);Object temp = arr[i - 1];arr[i - 1] = arr[swapIndex];arr[swapIndex] = temp;}ListIterator<T> it = list.listIterator();for (int i = 0; i < arr.length; i++) {it.next();it.set((T) arr[i]);}}}添加和修改
Collections也提供了几个批量添加和修改的方法
批量添加，方法为：
public static <T> boolean addAll(Collection<? super T> c, T... elements)批量填充固定值，方法为：
public static <T> void fill(List<? super T> list, T obj)这个方法与Arrays类中的fill方法是类似的，给每个元素设置相同的值。
批量复制，方法为：
public static <T> void copy(List<? super T> dest, List<? extends T> src)将列表src中的每个元素复制到列表dest的对应位置处，覆盖dest中原来的值，dest的列表长度不能小于src,dest中超过src长度部分的元素不受影响。
返回容器
适配器
适配器，就是将一种类型的接口转换成另一种接口，类似于电子设备中的各种USB转接头，一端
连接某种特殊类型的接口，一段连接标准的USB接口。Collections类提供了几组类似于适配器的方法：
·空容器方法：类似于将null或“空”转换为一个标准的容器接口对象。
·单一对象方法：将一个单独的对象转换为一个标准的容器接口对象。
·其他适配方法：将Map转换为Set等。
空容器方法返回一个不包含任何元素的容器接口对象，分别返回一个空的List、Set、Map和Iterator对象。实际使用中，空容器对象经常用作方法返回值。
public static final <T> List<T> emptyList()
public static final <T> Set<T> emptySet()
public static final <K,V> Map<K,V> emptyMap()
public static <T> Iterator<T> emptyIterator()Collections中还有一组方法，可以将一个单独的对象转换为一个标准的容器接口对象，比如：
public static <T> Set<T> singleton(T o)
public static <T> List<T> singletonList(T o)
public static <K,V> Map<K,V> singletonMap(K key, V value)这些方法也经常用于构建方法返回值，相比新建容器对象并添加元素，这些方法更为简洁方便，此外，它们的实现更为高效，它们的实现类都针对单一对象进行了优化。
装饰器
装饰器接受一个接口对象，并返回一个同样接口的对象，不过，新对象可能会扩展一些新的方法或属性，扩展的方法或属性就是所谓的“装饰”，也可能会对原有的接口方法做一些修改，达到一定的“装饰"目的。Collections有三组装饰器方法，它们的返回对象都没有新的方法或属性，但改变了原有接口方法的性质，经过“装饰”后，它们更为安全了，具体分别是写安全、类型安全和线程安全。
public static <T> Collection<T> unmodifiableCollection(
Collection<? extends T> c)
public static <T> List<T> unmodifiableList(List<? extends T> list)
public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m)
public static <T> Set<T> unmodifiableSet(Set<? extends T> s)这组unmodifiableXXX方法是使容器对象变为只读的，写入会报UnsupportedOperationException异常。典型场景是：需要传递一个容器对象给一个方法，这个方法可能是第三方提供的，为避免第三方误写，所以在传递前，变为只读的。
这些方法是如何实现的呢？每个方法内部都对应一个类，这个类实现了对应的容器接口，它内部是待装饰的对象，只读方法传递给这个内部对象，写方法抛出异常。比如unmodifiableCollection方法的代码为：
public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {return new UnmodifiableCollection<>(c);
}
所谓类型安全是指确保容器中不会保存错误类型的对象。
如果我们创建了一个Integer类型的List对象，但添加了字符串类型的对象"hello",编译没有错误，运行也没有异常，程序输出为"[hello]"。
之所以会出现这种情况，是因为Java是通过擦除来实现泛型的，而且类型参数是可选的。正常情况下，我们会加上类型参数，让泛型机制来保证类型的正确性。但是，由于泛型是Java5以后才加入的，之前的代码可能没有类型参数，而新的代码可能需要与老的代码互动。为了避免老的代码用错类型，确保在泛型机制失灵的情况下类型的正确性，可以在传递容器对象给老代码之前，使用类似如下方法“装饰”容器对象：
public static <E> List<E> checkedList(List<E> list, Class<E> type)
public static <K, V> Map<K, V> checkedMap(Map<K, V> m,
Class<K> keyType, Class<V> valueType)
public static <E> Set<E> checkedSet(Set<E> s, Class<E> type)使用这组checkedXXX方法，都需要传递类型对象，这些方法都会使容器对象的方法在运行时检查类型的正确性，如果不匹配，会抛出ClassCastException异常。
当多个线程同时读写同一个容器对象，是不安全的。Collections提供了一组方法，可以将一个容器对象变为线程安全的，比如：
public static <T> Collection<T> synchronizedCollection(Collection<T> c)
public static <T> List<T> synchronizedList(List<T> list)
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)这些方法都是通过给所有容器方法加锁来实现的，这种实现并不是最优的。对此，Java提供了很多专门针对并发访问的容器类。