java集合框架

JCF是Java CollectionsFramework的缩写,是Java提供的对集合进行定义、操作、管理的一组接口和类的体系结构。它主要包括两种主要类型Collection和Map,并且提供了对应的Collection和Map接口。JCF框架的核心接口如下图所示:

JCF架构图

从图上可以看出,List、Set、Queue继承了Collection,而Map则独成一体。这些接口Collection、List、Set、SortedSet、Map、SortedMap、Iterator、ListIterator、Queue的特点如下:

  • Collection:表示对象的集合,是所有集合类的根。
  • List:有序的Collection。特点是此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引(在列表中的位置)访问元素,并搜索列表中的元素。
  • Set:无序的Collection。特点是不包含重复元素的collection,或者说set不包含满足e1.equals(e2)的元素对e1和e2,并且最多包含一个null元素。
  • SortedSet:经过排序的Set。特点是可以按照元素的自然顺序(实现了Comparable接口)进行排序,或者按照创建有序集合时提供的Comparator进行排序。
  • Map:由键值对组成的无序元素集合。特点是将键映射到值的对象,并且一个映射不能包含重复的键;每个键最多只能映射一个值。
  • SortedMap:经过排序的Map。特点是可以按照键的自然顺序(实现了Comparable接口)进行排序,或者按照创建有序集合时提供的Comparator进行排序。
  • Iterator:对集合进行迭代的迭代器。特点是允许调用方在迭代期间从迭代器所指向的集合移除元素(这是和Enumeration比较的结果)。
  • ListIterator:List列表的迭代器。特点是允许程序员按任一方向遍历列表、修改列表,并获得迭代器在列表中的当前位置。
  • Queue:队列集合.特点是此接口提供了具有FIFO(先进先出,但是该特性不是必需的)的队列集合,同时还提供其他的插入、提取和检查操作。

而上面的所有接口在JDK1.5后都提供了泛性的扩展。

Collection接口

Collection接口

Collection接口继承了Iterable接口,在JDK1.5以后提供了foreach循环来遍历集合或者数组,并且foreach循环是基于Iterator的所以会继承Iterable接口。

看下Iterable接口的实现。

1
2
3
4
5
6
7
8
9
public interface Iterable<T> {

/**
* Returns an iterator over a set of elements of type T.
*
* @return an Iterator.
*/
Iterator<T> iterator();
}

AbstractCollection抽象类

下面是JDK文档对AbstractCollection抽象类的描述:

此类提供 Collection 接口的骨干实现,以最大限度地减少了实现此接口所需的工作。

要实现一个不可修改的 collection,编程人员只需扩展此类,并提供 iterator 和 size 方法的实现。(iterator 方法返回的迭代器必须实现 hasNext 和 next。)

要实现可修改的 collection,编程人员必须另外重写此类的 add 方法(否则,会抛出 UnsupportedOperationException),iterator 方法返回的迭代器还必须另外实现其 remove 方法。

按照 Collection 接口规范中的建议,编程人员通常应提供一个 void (无参数)和 Collection 构造方法。

List接口

Collection接口有三大子接口分别是:List、Set、Quene。

有序的 collection(也称为序列)。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引(在列表中的位置)访问元素,并搜索列表中的元素。

List 接口提供了多种对列表元素进行定位(索引)访问方法。列表(像 Java 数组一样)是基于 0 的。注意,这些操作可能在和某些实现(例如 LinkedList 类)的索引值成比例的时间内执行。因此,如果调用者不知道实现,那么用迭代器来遍历通常优于索引遍历。

List 接口提供了特殊的迭代器,称为 ListIterator,除了允许 Iterator 接口提供的正常操作外,该迭代器还允许元素插入和替换,以及双向访问。还提供了一个方法来获取从列表中指定位置开始的列表迭代器。

下面是List接口新增的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void add(int index, E element);

boolean addAll(int index, Collection<? extends E> c);

E get(int index);

int indexOf(Object o);

int lastIndexOf(Object o);

ListIterator<E> listIterator();

ListIterator<E> listIterator(int index);

E remove(int index);

E set(int index, E element);

List<E> subList(int fromIndex, int toIndex);

AbstractList抽象类

此类提供 List 接口的骨干实现,以最大限度地减少实现“随机访问”数据存储(如数组)支持的该接口所需的工作。对于连续的访问数据(如链表),应优先使用 AbstractSequentialList,而不是此类。

要实现不可修改的列表,编程人员只需扩展此类,并提供 get(int) 和 size() 方法的实现。

要实现可修改的列表,编程人员必须另外重写 set(int, E) 方法(否则将抛出 UnsupportedOperationException)。如果列表为可变大小,则编程人员必须另外重写 add(int, E) 和 remove(int) 方法。

按照 Collection 接口规范中的建议,编程人员通常应该提供一个 void(无参数)和 collection 构造方法。

与其他抽象 collection 实现不同,编程人员不必 提供迭代器实现;迭代器和列表迭代器由此类在以下“随机访问”方法上实现:get(int)、set(int, E)、add(int, E) 和 remove(int)。

下面是实现迭代器的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
private class Itr implements Iterator<E> {

int cursor = 0;

int lastRet = -1;

int expectedModCount = modCount;

public boolean hasNext() {
return cursor != size();
}

public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}

public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

Itr类是AbstractList的内部类,迭代的功能也是使用了List接口中定义的功能来实现。

AbstractList下的常见实现类:

  1. LinkedList:List接口的链接列表实现。它使用链表方式保存的数据,并且允许NULL元素.该类提供了优化的顺序访问性能,同时可以高效率地在列表中部进行插入和删除操作。但在进行随机访问时,速度却相当慢,此时应换用ArrayList。另外它还提供额外的addFirst、addLast、getFirst、getLast、removeFirst、removeLast方法实现对首、尾元素的操作,这些操作使LinkedList可被用作堆栈,队列、双向队列。该对象是非线程安全的。
  2. ArrayList:List接口的大小可变数组的实现。由于它是数组方式的实现,因此该类还提供了一些方法来操作存储数据的数组的大小。当其中的元素超过它的初始大小时,该类将自动增加原始大小的一半长度。该对象是非线程安全的。
  3. Vector:该类可以实现可增长的对象数组。它的功能非常类似于ArrayList,但是它是同步的、线程安全的。默认情况下当其中的元素超过它的初始大小时,该类将自动增加原始大小同样大小的空间。
  4. Stack:Stack继承自Vector,实现一个后进先出的堆栈。

Set接口

一个不包含重复元素的 collection。更确切地讲,set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2,并且最多包含一个 null 元素。正如其名称所暗示的,此接口模仿了数学上的 set 抽象。

在所有构造方法以及 add、equals 和 hashCode 方法的协定上,Set 接口还加入了其他规定,这些规定超出了从 Collection 接口所继承的内容。

对这些构造方法的其他规定是,所有构造方法必须创建一个不包含重复元素的 set。

注:如果将可变对象用作 set 元素,那么必须极其小心。如果对象是 set 中某个元素,以一种影响 equals 比较的方式改变对象的值,那么 set 的行为就是不确定的。此项禁止的一个特殊情况是不允许某个 set 包含其自身作为元素。

某些 set 实现对其所包含的元素有所限制。例如,某些实现禁止 null 元素,而某些则对其元素的类型所有限制。试图添加不合格的元素会抛出未经检查的异常,通常是 NullPointerException 或 ClassCastException。试图查询不合格的元素是否存在可能会抛出异常,也可能简单地返回 false;某些实现会采用前一种行为,而某些则采用后者。概括地说,试图对不合格元素执行操作时,如果完成该操作后不会导致在 set 中插入不合格的元素,则该操作可能抛出一个异常,也可能成功,这取决于实现的选择。此接口的规范中将这样的异常标记为“可选”。

Set接口并没有新增方法,只是对原来Collection接口当中的一些方法进行了重新的描述定义。

AbstractSet抽象类

此类提供 Set 接口的骨干实现,从而最大限度地减少了实现此接口所需的工作。

通过扩展此类来实现一个 set 的过程与通过扩展 AbstractCollection 来实现 Collection 的过程是相同的,除了此类的子类中的所有方法和构造方法都必须服从 Set 接口所强加的额外限制(例如,add 方法必须不允许将一个对象的多个实例添加到一个 set 中)。

注意,此类并没有重写 AbstractCollection 类中的任何实现。它仅仅添加了 equals 和 hashCode 的实现。

继承AbstractSet抽象类的常见子类:

  • EnumSet
  • HashSet
  • TreeSet

Queue接口

在处理元素前用于保存元素的 collection。除了基本的 Collection 操作外,队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式:一种抛出异常(操作失败时),另一种返回一个特殊值(null 或 false,具体取决于操作)。插入操作的后一种形式是用于专门为有容量限制的 Queue 实现设计的;在大多数实现中,插入操作不会失败。

操作 抛出异常 返回特殊值
插入 add(e) offer(e)
移除 remove() poll()
检查 element() peek()

队列通常(但并非一定)以 FIFO(先进先出)的方式排序各个元素。不过优先级队列和 LIFO 队列(或堆栈)例外,前者根据提供的比较器或元素的自然顺序对元素进行排序,后者按 LIFO(后进先出)的方式对元素进行排序。无论使用哪种排序方式,队列的头都是调用remove() 或 poll() 所移除的元素。在 FIFO 队列中,所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue 实现必须指定其顺序属性。

如果可能,offer 方法可插入一个元素,否则返回 false。这与 Collection.add 方法不同,该方法只能通过抛出未经检查的异常使添加元素失败。offer 方法设计用于正常的失败情况,而不是出现异常的情况,例如在容量固定(有界)的队列中。

remove() 和 poll() 方法可移除和返回队列的头。到底从队列中移除哪个元素是队列排序策略的功能,而该策略在各种实现中是不同的。remove() 和 poll() 方法仅在队列为空时其行为有所不同:remove() 方法抛出一个异常,而 poll() 方法则返回 null。
element() 和 peek() 返回,但不移除,队列的头。

Queue 接口并未定义阻塞队列的方法,而这在并发编程中是很常见的。BlockingQueue 接口定义了那些等待元素出现或等待队列中有可用空间的方法,这些方法扩展了此接口。

Queue 实现通常不允许插入 null 元素,尽管某些实现(如 LinkedList)并不禁止插入 null。即使在允许 null 的实现中,也不应该将 null 插入到 Queue 中,因为 null 也用作 poll 方法的一个特殊返回值,表明队列不包含元素。

Queue接口新增的方法定义如下:

1
2
3
4
5
6
7
boolean offer(E e);

E poll();

E element();

E peek();

AbstractQueue抽象类

此类提供某些 Queue 操作的骨干实现。此类中的实现适用于基本实现不允许包含 null 元素时。add、remove 和 element 方法分别基于 offer、poll 和 peek 方法,但是它们通过抛出异常而不是返回 false 或 null 来指示失败。

扩展此类的 Queue 实现至少必须定义一个不允许插入 null 元素的 Queue.offer(E) 方法,该方法以及 Queue.peek()、Queue.poll()、Collection.size() 和 Collection.iterator() 都支持 Iterator.remove() 方法。

它的直接子类有:

  • ArrayBlockingQueue
  • ConcurrentLinkedQueue
  • DelayQueue
  • LinkedBlockingDeque
  • LinkedBlockingQueue
  • PriorityBlockingQueue
  • PriorityQueue
  • SynchronousQueue

总结

Collection接口下的一些主要类和接口已经介绍完成,剩下的Map在后续的文章中进行介绍,以及一些集合当中实现类的实现方式的源码分析。

—EOF—