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提供了一组方法,可以将一个容器对象变为线程安全的,比如:文章来源:https://www.toymoban.com/news/detail-825687.html
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提供了很多专门针对并发访问的容器类。文章来源地址https://www.toymoban.com/news/detail-825687.html
到了这里,关于Java Collections源码剖析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!