Collections源码阅读
Collections源码阅读
提供了许多对collection的操作，对于操作的collection，一般有随机存储和链式存储，有时候需要分别考虑，链式或者数据量比较大的话，一般采用迭代器的思路
方法
sort
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);
}
如果类型实现了Comparable，就用第一个，没有的话，就需要传入比较函数，调用了list.sort,list的Sort方法实际调用的是Arrays中的sort
binarySearch 二分查找
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);
}
如果是随机存储的，则二分查找时直接算出中点比较即可，否则使用迭代器方法顺序遍历到中点。如果是该方法会返回一个查找的key的index，如果没找到，就会记录这个值可以插入数组的index，返回-（index+1）
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);
}
如果类没有实现Comparable或其他情况，那么查找的时候也要把比较函数传进来
reverse、shuffle、swap、copy、fill、min。max
一些常用的，没有太特别的地方，就不贴出来了，注意判断一下是不是随机存储的选择用index或者ListIterator
rotate 轮转函数
public static void rotate(List<?> list, int distance) {
if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
rotate1(list, distance);
else
rotate2(list, distance);
}
整个list循环一样的平移，比如a=｛1，2，3｝，rotate（a，1）后，a就是｛3，1，2｝，rotate（a，-1）后，a就是｛2，3，1｝ 再具体看下rotate1和2.
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);
}
}
仔细想了下，应该是有规律的，即每次循环一遍后如果cyclestart后面紧挨着的元素已经交换过了，就说明所有元素都已经交换了过了，这时候nMoved==size了，所以并不会造成二次交换
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);
}
首先翻转点的选取，因会翻转，所以翻转点与distance相比是从后面算起的
对subList的翻转进行了两次，所以没有打乱subList内部的顺序。同时两个subList也交换了顺序，相当于只是交换两个subList的次序。
replaceAll
public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)
把旧值替换成新值，没什么特别的，注意一下val为null和存储方式即可
indexOfSubList、lastIndexOfSubList
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; // All elements of candidate matched target
}
} 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())) {
// Back up source iterator to next candidate
for (int j=0; j<i; j++)
si.previous();
continue nextCand;
}
}
return candidate;
}
}
return -1; // No candidate matched the target
}
有点像字符串匹配，不过这里只用了简单的两层循环比较的方法
unmodifiableCollection
public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
return new UnmodifiableCollection<>(c);
}
返回一个静态内部类UnmodifiableCollection，这个类只可读，对c的修改会影响UnmodifiableCollection，举个例子;
List< Integer > list1 = new ArrayList<> ();
list1.add (1);
Collection list2=Collections.unmodifiableCollection (list1);
System.out.println (list1.toString ());
System.out.println (list2.toString ());
list1.add (2);
System.out.println (list1.toString ());
System.out.println (list2.toString ());
list2.add (3);//error
输出：
[1]
[1]
[1, 2]
[1, 2]
报错
Collections还有许多unmodifiable类似的方法，就不一一列举了
synchronizedCollection
public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
return new SynchronizedCollection<>(c);
}
在hashTable中用到了，但是hashTable要被弃用了，暂时先不管了，util.current包中提供了更好的
checkedCollection
public static <E> Collection<E> checkedCollection(Collection<E> c,
Class<E> type) {
return new CheckedCollection<>(c, type);
}
提供了一个自带安全检查的集合，若把该Collection传递给其他调用者，其他调用者加入不安全的类型时会报错，例如：
public List getCards() {
return Collections.checkedList(list, Integer.class);
}
List newList = list.getCards();
newList.add("hello world")//error
这样调用就会报错
newSetFromMap
public static <E> Set<E> newSetFromMap(Map<E, Boolean> map)
传入一个空的map，得到一个set，应用场景：可以用来得到并发set
disjoint
public static boolean disjoint(Collection<?> c1, Collection<?> c2)
判断交集，代码没什么特别的地方
// 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)).
注意一下用长度长的Collection来判断是否包含，短的用来遍历。（我个人感觉其实差不多呀，要是短的偶数，长的为奇数）不就是(4 * ceiling(49/2)) vs (49 * ceiling(4/2)，或许这种情况的差别比注释里的差别要更小吧，所以考虑短的来遍历
frequency
public static int frequency(Collection<?> c, Object o)
返回出现次数
reverseOrder
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)
返回一个比较规则相反的Comparator
singleton
public static <T> List<T> singletonList(T o) {
return new SingletonList<>(o);
}
返回一个只有一个元素的集合，可以禁止别人加入元素，个人感觉意义不大呀，虽说final作用于集合，还是可以往里面添加元素，不过直接写成final的变量不行吗，或许是还有我没想到的场景吧。
removeAll的时候可以用一下，比如：
a={1,2,1}
List removeTemp=Collections.singletonList(1)
a.removeAll(removeTemp)//a={2};
