本章主要讲Collections工具类以及该类提供的一些有用的成员类。
Collections是一个静态工具类，构造方法已经私有化，故只能提供静态方法被调用，不能被实例化。看Guava的很多工具类也和这个一个，都是在目标类的结尾加s来代表工具类，比如Guava给List提供的工具类就叫Lists。 注意，本系列文章都使用JDK1.8作为源码学习，可能有些实现变化比较大。 它有如下比较有用的方法： ### Sort 用来针对List进行排序的，如果只传List，那么要求List里面包含的对象实现Comparable接口，如果还传了Comparator就无所谓，按照Comparator定义的规则排序。 在JDK1.7以前，此处排序使用的是归并排序，有人说是快排，我看了1.6源码，是归并排序。1.7之后，使用了新型排序算法Timsort，似乎是归并排序的改良版，更好地支持入参数组已经被倒着排好序的情况。 这个方法目前时间复杂度最坏情况是O(NlogN)，如果数组已经几乎排好序了，那就是O(N)即线性时间。而且，这个方法是稳定排序，相同的元素，无论比较多少次，相对顺序都不会变。 具体算法的介绍就不深究了，以后另开帖子讨论。 ### binarySearch 顾名思义，二分查找来找到某个元素在List中的index。入参是已经自然排序的List和要查找的元素key。如果入参List没有排序，那么返回的结果是不确定的。 如果没有找到key，返回的一定是个负值，且为-(insertPoint+1)，此处，insertPoint指的是第一个比key大的元素的index，如果没有这样的元素那就是size。加一之后再取反，相当于是那个比key大的元素在数组中1-base开始算起的位置取负数。 有意思的是，该方法底层分成了两个方法，如果List实现了RandomAccess接口或者该List小于Collecions定义的一个常量BINARYSEARCH_THRESHOLD，就使用indexedBinarySearch，如果不满足这个条件，使用的是iteratorBinarySearch。 其中，BINARYSEARCH_THRESHOLD是5000，这是一个经验值，JDK的作者们总结经验得出来的。 下面给出那种不同算法的代码： 首是先是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; 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 }
然后是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 } private static <T> T get(ListIterator<? extends T> i, int index) { T obj = null; int pos = i.nextIndex(); if (pos <= index) { do { obj = i.next(); } while (pos++ < index); } else { do { obj = i.previous(); } while (--pos > index); } return obj; }
可以看出，二分查找法挺简单的。就是拿目标元素和中间的元素去比较，找到目标元素有可能落入的区间，继续比较，直到找到目标元素。 理论上，这个算法有O(logN)的时间复杂度，比我们直接遍历一遍快多了。但是这只是indexedBinarySearch的情形。 如果我们的List不是那种可以直接用index获取元素的List，比如LinkedList，很遗憾，时间复杂度要算上取元素的时候遍历的，就应该是O(KlogN)，其中K是每次遍历获取元素要遍历的元素个数，N是数组长度。 ### reverse 将传入的List颠倒顺序，同样有两种底层实现，针对实现了接口RandomAccess或者size少于REVERSE_THRESHOLD（是18）的List，采用下面介绍的swap方法直接从两头开始相互交换元素。 如果没有实现那个接口或者元素大于等于18个，就用迭代器ListIterator来获得元素，同样还是从两头开始遍历相互交换元素。 无论哪种方法，都是在线性时间完成倒转顺序。 ### shuffle 随机打乱入参List内部元素的顺序。线性时间复杂度。 原理是用Random类，随机生成int来交换元素。 和上面一样，有个常量SHUFFLE_THRESHOLD等于5的，代表如果List实现了RandomAccess接口或者小于5，就直接用get,set方法来交换。如果不满足就把List内部的数组toArray出来，然后再做随机交换操作，然后用迭代器从头再把打乱后的原生数组一个一个插入回去。显然第二种情况toArray的时候有拷贝数组的行为，性能肯定要差一些，一个一个插回去也等于遍历一遍，相当于交换和插入遍历了2遍，性能肯定差一些。 ### swap 比较简单的方法，入参是(List，int index1,int index2)，就是交换List两个index位置的元素 ### fill 入参是(List,E)，这个有些粗暴，就是把List里面所有的元素都换成E元素。线性时间复杂度。 ### copy 入参是(List dest,List src)，就是吧src这个List的内容拷贝到dest，因此dest肯定要比src长才行，否则肯定拷贝不进去报错。拷贝后dest多出来的半截里如果本来有元素，不受影响。 线性时间复杂度 ### min 寻找最小值的。这个入参是Collection，并且要求内部的元素类型一定实现Comparable接口，当然，如果第二个参数传入了Comparator就不需要。线性时间复杂度。 ### max 寻找最大值的。要求同上。线性时间复杂度。 ### rotate 入参是List，和一个int值。意为旋转，但是其实由于我们的List是一维的，根本没有旋转的概念。所以其实是移位。这个方法就是将List内的元素同时向右移动int值个位置，最右边的元素移位会移到最左边。 比如rotate([a,b,c,d]，2)，移动以后就变成[c,d,a,b]。 同样有一个常量ROTATE_THRESHOLD，值是100，List如果实现了RandomAccess或者size小于100，就使用第一种算法：
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 { i += distance; if (i >= size) i -= size; displaced = list.set(i, displaced); nMoved ++; } while (i != cycleStart); } }
可以看到主要就是用get和set方法，认为这两个方法是常数时间。然后从头开始，往后移位。超过了size就减掉size来保证指针不会越界。 有元素移动的时候就nMoved加1，直到nMoved和size相等说明所有的元素都被移位过了就停止。 如果List没实现RandomAccess接口并且size大于等于100，厉害了，就用一种新的算法：
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); }
讲真看到这个算法我是很吃惊的，居然这么简单就搞定了。reverse已经说过了，就是反转。把List切成两部分，两部分先反转，再反转整个，竟然就完成了移位！天哪噜。 其中最重要的就是切点，怎么切分两部分？就是-distance % size。我自己实验，如果100个元素，传入2，会得到-2，然后加上size之后就是98。说白了，如果你传的是个正值，得到的就是从右边起数distance个元素的位置。如果是负值，就是从左边起数|distance|（绝对值）个元素的位置。
无论是上面哪种方法，我们得到的时间复杂度都是O(N)，不过要注意，肯定还是第一种快，原因是第二种其实是O(2N)，整个List遍历了2遍。但是没办法啊，如果不是RandomAccess的话，第一种就要算上get和set查找的时间了，那就比2N还惨了。 ### replaceAll 参数(List<T> list, T oldVal, T newVal)，没啥好说的，就是单纯地把List内所有oldVal换成新的newVal。 线性时间复杂度。 ### indexOfSubList 参数(List<?> source, List<?> target)，假设target是source的subList，找出它在source中第一个元素的index。或者说，从source中找出和target一模一样的SubList，并返回它的起始index。 这个方法性能比较差，平方级时间复杂度。采用穷举的方法。如果没找到这样的subList，就返回-1。有常量INDEXOFSUBLIST_THRESHOLD，作用和上面提到的类似。值得一提的是，如果是没实现RandomAccess接口或者比常量大的话，就用迭代器来获得元素，这导致时间复杂度变成立方级。 ### lastIndexOfSubList 这个参数和上面的相同，作用也类似，只不过找到的是最后一个匹配的subList。 有趣的是，这个地方有个bug。在上面的方法中，识别是否应该使用迭代器来获取元素，除了大于常量INDEXOFSUBLIST_THRESHOLD以外，还要求source和target两个入参List都实现RandomAccess接口。很不幸，这个地方作者似乎漏掉了，只判断了source，这样如果target没实现RandomAccess接口，后果就是时间复杂度变成立方级。当然，这也无所谓，反正换成用迭代器那个方法也是立方级时间复杂度。
在第一章我们讲Collection接口下面的子类们的时候，遗留了很多包装类没讲，几乎都作为成员类放在Collections这个工具类中。有必要稍微了解一下。 ### UnmodifiableCollection系列 Collections类中有一系列方法，可以包装Collection或者它下面的List，Set，Queue等，使这些结构失去可变的能力，变成不可变的集合。 #### unmodifiableCollection方法 入参就是一个Collection啦，返回的就是一个UnmodifiableCollection(注意这里和下面所有返回的地方，都指的是实际返回的类型，而方法签名实际上返回的是入参类型，也即泛型化了)，这是典型的装饰器模式，在我设计模式的文章里有讲到。 怎么实现不可变呢？简单，所有add，remove等等有关改变的方法全部抛出UnsupportedOperationException，其余方法直接调用它装饰的原始Collection的方法来放回结果就OK了。 甚至连迭代器也是一样，虽然用匿名内部类来返回迭代器，但是这个匿名类其实还是调用的原始Collection的迭代器。 #### unmodifiableSet方法 入参是一个Set，返回是一个UnmodifiableSet，这个类继承了上面的类，所以它几乎什么也不用做就完成了不可变………… #### unmodifiableSortedSet方法 入参是一个SortedSet，返回UnmodifiableSortedSet，该类继承了unmodifiableSet，所以也不需要实现很多方法，原理也是装饰器，它实现的方法全部都是引用我们的入参对象SortedSet完成的。 #### unmodifiableNavigableSet方法 和上面类同，可见Collections工具类要做就做全套，把我们上一章讲到的所有接口都提供了一个包装方法来获得不可变的实例。不过要注意，没有Queue和Deque什么事儿 #### unmodifiableList方法 包装List主要是分成两种情况，一种是入参实现了RandomAccess接口，那返回的就是UnmodifiableRandomAccessList装饰器类，如果没实现，就返回UnmodifiableList装饰器类。 两者区别不大，其中UnmodifiableRandomAccessList继承了UnmodifiableList。 #### unmodifiableMap方法 入参是Map，返回UnmodifiableMap。这个实现起来就比较复杂了，毕竟Map本身就是很复杂的结构，Map本来内部就用到了一种Entry的结构，还要返回Set和Collection类型的视图，因此为了实现不可变，在这些地方都分别构造了不可变版本。比如在entrySet方法返回的地方，为了返回的东西是不可变的，专门写了UnmodifiableEntrySet类来包装Map的entrySet。而这个类内部又定义有UnmodifiableEntry用来包装原来的可变的Entry。 #### unmodifiableSortedMap方法 入参是SortedMap，返回UnmodifiableSortedMap，Map结构还没来得及介绍，这个UnmodifiableSortedMap毫无悬念继承了UnmodifiableMap，所以没有太多内容。 #### unmodifiableNavigableMap方法 入参是NavigableMap，返回是UnmodifiableNavigableMap。继承了UnmodifiableSortedMap。也没什么好讲的。 #### 注意事项 由于是装饰器模式，最好要装饰的类在创建的时候立马就用这个方法装饰起来，不要之后再装饰，如果拿的到原始对象的引用，还是可以修改的，不可变就没有意义了。 ### SynchronizedCollection系列 和UnmodifiableCollection差不多，不同之处在于这个系列的目的是想要让那些不支持线程安全的数据结构支持数据安全。 说实话这个系列做的并不好，只是简单地使用synchronized关键字来锁住代码块。 差不多每个类内部都有一个Object域，单纯地用来做对象锁。当然了，这个域其实就是this，类的实例。 本来我以为会直接在方法上加synchronized关键字完事呢，就像Vector那样，但是事实证明是每个方法内部用同步代码块加锁的。这两种效果应该是一样的，不知道为什么要这么做，有空查查资料。 #### 都支持哪些 Set SortedSet NavigableSet List Map SortedMap NavigableMap 把Set、List、Map三大接口都承包了，但是注意，没有Queue和Deque（它们的线程安全版本在并发包里）。 #### 注意事项 和UnmodifiableCollection不同，这个系列并没有自己实现迭代器，而是直接将被装饰的那个对象的迭代器返回给了用户。 因此，所有通过该系列返回的Collection，它们的迭代器都是非线程安全的，用户要自己来手动搞定迭代器的同步过程。 举例如下：
NavigableSet s = Collections.synchronizedNavigableSet(new TreeSet()); ... synchronized (s) { Iterator i = s.iterator(); // Must be in the synchronized block while (i.hasNext()) foo(i.next()); } NavigableSet s = Collections.synchronizedNavigableSet(new TreeSet()); NavigableSet s2 = s.headSet(foo, true); ... synchronized (s) { // Note: s, not s2!!! Iterator i = s2.iterator(); // Must be in the synchronized block while (i.hasNext()) foo(i.next()); }
不管是迭代器还是子视图的迭代器，都要通过同步代码块来获取和操作，而且要注意：同步代码块的锁是Synchronized方法返回的对象，不能是子视图！更不能是其他东西。 Map的例子：
Map m = Collections.synchronizedMap(new HashMap()); ... Set s = m.keySet(); // Needn't be in synchronized block ... synchronized (m) { // Synchronizing on m, not s! Iterator i = s.iterator(); // Must be in synchronized block while (i.hasNext()) foo(i.next()); }
可以看到，此处keySet获取放在外面，因为它内部已经实现线程安全了。锁也必须是返回的Map，不能是Set。 ### CheckedCollection系列 这个系列目的是提供运行时的类型安全Collection，那么问题来了，我们上一章介绍的Collection都不类型安全吗？ 还真不是，在没有泛型的情况下，这些Collection都是想塞什么就塞什么进去，不同类型的对象也完全没问题，反正所有对象都是Object的子对象。 所以这个系列就是在没有泛型的情况下，保证类型安全的手段，在add，addAll这种方法上检查类型，如果要插入的对象不符合你想要的类型，直接抛出异常。 值得一提的是，这个系列还支持了Queue接口，之前都没他什么事儿。 至于具体实现，就不多说了，现在泛型问世，已经很少用到这些方法了。 ### Empty系列 有时候我们需要获得空的Collection对象，见《Effective Java第二版》第四十三条。 Collections工具类已经为我们提供了便利的方法集，能够类型安全地获得各种空的Collection对象，而且保证不可变。 用法如下：
List<String> s = Collections.emptyList();
它支持List，Set，Map三大接口下面所有的接口，同时支持返回空的Iterator和ListIterator。也支持返回空的Enumeration（作用和Iterator一样，这是遗留接口，已废弃） ### Singleton系列 这个系列方法目的是返回只包含一个元素的不可变Collection，不过它只支持Set、Iterator、Spliterator、List、Map这5种类型。 我想这个更多地是方便与遗留代码一起协作，某个遗留代码需要一个Collection，而你手上只有一个Object，而且你确定遗留代码只需要这个Object就行了，那你就使用该系列来对接遗留代码。当然，如果遗留代码后续还在你返回的Collection里面增减元素搞事情，那就不要用这个了。 ### 其他一些零散的东西 #### nCopies方法 这个方法很有意思，它也使用了特殊的实现类CopiesList。入参是(int n, T o)。目的是假如你有一个不可变集合，里面所有的元素都是o对象，只不过重复了n次，那么你可以使用这个方法直接构造这样的集合，而且你不需要真的存储o对象n次，这个CopiesList只存o对象1次，但是它会给你已经存了n次的错觉。甚至你遍历啊，根据index获取啊，都完全可以，不会露馅。 #### reverseOrder方法 没有入参，获得一个Comparator，这个Comparator可以在比较的时候颠倒顺序，本来排序是正序，用了它就是逆序。当然了，它的目标对象必须先实现Comparable接口，不然不行。 还要一个有入参的版本，入参是Comparator，返回的是个ReverseComparator2，这个对象是个装饰器，会把两个对象颠倒顺序然后给Comparator比较，比较的结果当然就是颠倒的了。 #### enumeration方法 入参是Collection，返回是Enumeration，Enumeration是个废弃接口，这是为了遗留代码。 还要个list方法，也是为了遗留代码，不看了。 #### frequency方法 入参(Collection<?> c, Object o)，统计集合c中o出现的次数。 #### disjoint方法 入参(Collection<?> c1, Collection<?> c2)，两个集合如果没有相同的元素就返回true，否则返回false。 如果两个集合都是空集合，返回true。 #### addAll方法 使用例子如下：