Collection简介

背景

Java编程中集合类可以说给我们提供了很多的便利,在享受它带来的便利的时候,有时候也会想它的内部是怎么实现的,近期给自己定了个小目标,就是把Collection接口相关的jdk源码看一下,进行一个系统的总结和梳理,一方面提升自己源码阅读的能力,另一方面,通过阅读大神的代码,是自己对于集合这块的数据结构有个更加深刻的了解,对自己以后的使用相信也会有很大的益处。因为自己平时其他的事情也比较多,而且jdk1.8中相关的类也比较多,就先定一个月的时间吧,截止日期12月1日,希望可以完成。

Collection体系综述

阅读源码首先得有一个总体的结构认识,不然直接一头扎到类中的每个方法实现细节,只能是盲人摸象,摸到啥算啥。因此,我决定从Java SE 1.8的官方API入手,先梳理Collection这个核心接口,搞清楚它的父接口、子接口以及实现类,形成一个宏观的认识,然后再对它的子接口及其实现类分模块进行梳理,相信会对之后的阅读有一个引导作用。

Collection接口的关系图如下:

  • 上图中菱形代表的是接口,矩形代表的是类,箭头所指的方向为父类或父接口

Collection继承了Iterable接口,Iterable接口在1.8之前都只有一个抽象方法,叫做iterator,返回一个Iterator对象,也就是说,该接口赋予了Collection遍历自己的能力。因此,一个Collection的子类拥有如下的特点:

  • 元素的集合,{element1, element2, …, elementn}
  • 可以通过返回的Iterator进行遍历
  • 具有add、remove方法,可以添加或删除元素、集合。
  • 1.8之后,removeIf方法可以传入lambda表达式,通过条件判断进行删除

Collection子接口综述

由上图可以看出,Collection接口的主要子接口为Set、List、Queue(BeanContext并不属于Collection 框架中的成员,且其位于java.beans.beancontext包中,暂时不进行讨论),三个子接口的特点如下:

  • Set接口表示的一类集合,该集合中element不可重复,且没有先后顺序
  • List接口表示的类似于数组的一类集合,该集合有先后顺序且可以通过下标进行访问,且可以存放重复元素
  • Queue通常表示的为FIFO序列,优先队列根据优先级弹出,Queue也就是队列的一个统一接口

除了上面的三个直接子接口,Map接口也是Collection Framework中重要的一员,它代表的是一组键值对,也可以称为hash表,可以通过key值来访问指定的元素。

Collection的相关子接口、子类关系如下表所示:

接口名 Hash表 变长数组(Resizable Array) 平衡树(Balanced Tree) 链表(Linked List) 链表实现的Hash表
Set HashSet TreeSet(红黑树) LinkedHashSet
List ArrayList LinkedList
Deque ArrayList LinkedList
Map HashMap TreeMap(红黑树) LinkedHashMap

Collections类

Collections类并不是Collection接口的一个实现类,但它却和Collection接口息息相关,因为该类是集合的一个工具类,方法均为静态方法,传入参数大多数为List,也有一部分为Collection。该类是一个集合算法的工具类,提供了诸如集合排序和查找的算法,下面对提供的算法进行一个总结。

改变元素顺序的方法

sort方法提供了对List及其子类的排序功能(毕竟Set无序),内部实现的算法是归并排序的算法,该方法是快速和稳定的。

  • 快速:保证时间复杂度在O(n logn)
  • 稳定:不重排列相等的元素,这在多次排序中很重要,第二次排序希望第一次排完序的部分保持

sort方法的方法头如下

1
public static <T> void sort(List<T> list, Comparator<? super T> c)
  • 可以自定义Comparator实现升序、降序排序

swap方法提供了对List指定两个位置元素进行交换的方法,声明为public static void swap(List<?> list, int i, int j),将位于i,j的元素进行交换

shuffle方法提供了对List及其子类的乱序功能,它可以利用一个Random对象,随机的将位于i的元素和位于random.nextInt(i)的元素交换,核心代码如下

1
2
for (int i=size; i>1; i--)
swap(list, i-1, rnd.nextInt(i));
  • 在i-1的位置时,从i到size的元素已经被乱序,因此使用nextInt(i)随机的与前i个元素中的一个进行交换
  • 该方法在形成测试数据时很适用

reverse方法将List首尾倒置,该方法的时间复杂度为O(n),核心代码如下

1
2
for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
swap(list, i, j);

改变元素值的方法

fill方法将List的每个元素设置为指定的元素,该方法在进行数组的初始化时适用。

replaceAll方法将List中指定的旧值设置为新值。

copy方法将src list中的元素全部拷贝到dest list中,并覆盖dest list.

查询类方法

max方法和min方法分别返回序列中的最大值和最小值,通过遍历找到最大、最小值。

binarySearch方法在一个排好序的方法使用二分查找的方法查找一个元素的位置,该方法对于实现了RandomAccess接口的序列可以在logn时间内找到该元素,但对于未实现该接口,该方法将使用遍历的算法进行查找。

1
2
3
4
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);

disjoint方法传入两个集合,如果两个集合没有交集,则返回true,否则,返回false.

序列初始化

empty*方法可以返回空List、Set等。

synchronized*方法可以将传入的List、Set等,返回线程安全的List、Set,适用于多线程编程,但其内部使用的synchronized同步语句,因此并发度不高。

小结

Collection Framework是Java集合编程的一个重要的工具,通过梳理Collection接口,基本理清了涉及到的接口和对象,接下来将按照List、Set、Queue、Map的顺序依次进行各自模块的梳理。