【标题】：Java集合框架(J2SE1.6)
【关键字】：Java,J2SE1.6
【来源】：http://blog.csdn.net/linyt/archive/2007/04/12/1562197.aspx

Java集合框架(J2SE1.6)

Java集合框架是sun公司发布的Java应用程序接口(API)的重要组成部分，并放在java.util包里面。Java平台的集合框架提供了一个表示和操作对象集合的统一架构，允许用户独立地操作各种数据结构而不需要了解具体的实现。Java集合框架中包含了大量集合接口，以及这些接口的实现类和操作它们的算法。依此，可用如下公式表示Java集合框架。

Java集合框架 = 集合接口+实现+算法

Java是一个比较C++更纯的面向对象语言，因此Java的出现，伴随着很多良好的面向对象设计思想的出现。Java是一个提倡面向接口编程而非实现编程的语言，因此Java所提供的应用程序接口(API)中出现大量的接口，目的是使接口与实现分离，允许用户基于接口编程，同时也提供很好的互操作性。

Java集合框架中的数据结构

Java集合框架作为java应用程序中的工具类，是为了为开发人员提供一个良好的应用程序接口。Java集合框架为开始提供了大量的数据结构，包括列表(List)，队列(Queue)，栈(Stack)以及一个键值映射数据结构(Map)。同时这些数据结构的实现中还涉及到红黑树，哈希表等数据结构，并且为程序员提供使用的方便。

上图是Java1.6中API集合框架中所提供的主要数据结构接口，提供List、Set、Queue和Map等数据结构。从上面的类图结构可以看到，Collection类是所有除Map以外其它接口的基类，它提实该问一组对象的基本接口，以确保它们的实现具互操作性和实现独立性。下面详细说明各个接口的功能和主要方法。

Collection接口

Collection是整个集合框架的基础，它表示不同类型的Collections(Collections表示不同的数据结构，如List，Set和Queue等等)。

Collection从概念上来说，是一个抽象，它里面储存一组对象。该组对象是否有序，是否允许重复，具体依赖它的不同实现。它只是提供维护一组对象的基本接口。下面是主要方法的介绍。

方法概述

boolean

add(E e)

把元素e加入Collection对象中，如果改变Collection对象则返回true，否则返回false。

boolean

addAll(Collection<? extends E> c)

把c中所有元素加入当前Collection中。

void

clear()

清除Collection中的所有元素。

boolean

contains(Object o)
当前Collection是否包含对象o，如是则返回true，否则为false。

boolean

containsAll(Collection<?> c)
当前Collection是否包含c中的所有元素，如是则返回true，否则为false。

boolean

equals(Object o)

当前Collection与对象o是否相等，所谓相等应遵从Object类中equals方法的要求，详见Object.equals方法说明。

int

hashCode()

返回当前Collection中的哈希码。

boolean

isEmpty()

返回当前Collection对象是否为空，如是空则为true,否则为false。

Iterator<E>

iterator()

返回当前Collection元素的迭代器。

boolean

remove(Object o)

删除当前Collection中对象为o的元素，如果有多个只删除一个。如果删除成功则返回true，否则为false。

boolean

removeAll(Collection<?> c)

删除当前Collection中在c出现的所有元素。如果当前Collection改变就返回true，否则返回false。

boolean

retainAll(Collection<?> c)

只保留当前Collection中在c所出现的元素。如果Collection改变则返回true，否则false。

int

size()

返回Collection中元素的个数。

Object[]

toArray()

返回包含Collection所有元素的数组。

<T> T[]

toArray(T[] a)

返回包含Collection所有元素的数组，数组元素类型由运行时类型T指定。

在Collection所提供的方法中，以Collection类型作为参数的函数，都为Collection的实现类提供了互操作的功能。如可以把一个List中所有元素加到一个Set中，反之亦然。toArray方法可以把一个Collection转换成相应的数组，为Collection使用数组的算法提供了方便。特别是某些算法如排序，对数组的运行效率最高。因此，如果要对一个Collection里面的元素进行排序的话，通常是先转换成数组再排序。

List接口

List接口是Collection的一个子接口，它提供了线性表的操作接口。Java集合所提供的List接口与我们数据结构上的线性表是一致的。List又称为有序的Collection，此接口允许用户对列表中的每个元素的插入和删除位置进行精确的控制。因此，List是可提了一个随机访问接口的线性表。同时List通常允许存在重复的元素。下面是List接口中在Collection的基础上新增的方法。

方法概述
void	add(int index, E element) 在列表的指定下标增加元素。
boolean	addAll(int index, Collection<? extends E> c) 在列表指定下标增加c中所有元素到列表中。
E	get(int index) 访问列表中指定下标的元素。
int	indexOf(Object o) 返回对象o在列表中第一次出现的下标，如列表不包含元素o则返回-1。
int	lastIndexOf(Object o) 返回元素o在列表中最后一次出现的下标，如列表不包含则返回-1。
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) 返回子列表[fromIndex, toIndex)。

在List接口中，增加的方法主要是为随机访问提供方便。通常这些函数的参数都指定了要访问元素的下标；再者是返回元素的下标和得到列表的子列表。至于List的基于不同的物理结构，有不同的实现（如ArrayList和LinkedList）和随机访问的代价不同，提供了列表迭代器对元素进行操作。使访问元素独立于具体的实现。

Set

Set接口同样是Collection接口的一个子接口，它表示数学意义上的集合概念。Set中不包含重复的元素，即Set中不存两个这样的元素e1和e2，使得e1.equals(e2)为true。由于Set接口提供的数据结构是数学意义上集合概念的抽象，因此它需要支持对象的添加、删除，而不需提供随机访问。故Set接口与Collection的接口相同，在此对里面的方法不作介绍。

Queue

Queue为用户提供了队列的操作接口，同样是Collection的子接口。除于提供基本的Collection操作外，Queue还提供了供其他的插入、提取和检查操作。从数据结构来说，Queue应提供一个先进先出的数据结构(FIFO)；但在Java集合框架中，这并非一成不变的要求。优先级队列和 LIFO 队列就是一个例外。因此，我们可以认为Java集合框架中的Queue是这样的一个数据结构；Queue为用户提代了一个在尾端插入，在头端删除这样的数据结构，元素与元素的关系依赖于具体实现。如一般的队列存在先进先出的关系，但在优先队列中，存在元素按大小的关系。因此在Queue的实现中，必须说明元素之间的关系，即元素间的顺序属性。下面是提供列队操作方法的说明。

方法概述
E	element() 检过队头元素，但不删除。如果队列为空则抛出`NoSuchElementException异常。`
boolean	offer(E e) 进队操作。
E	peek() 检索队头元素，但不删除。如果队列为空则返回null。
E	poll() 删除并返回队头元素，如果队列为空则返回null。
E	remove() 删除并返回队头元素，如果队列为空抛出`NoSuchElementException异常。`

队列接口为用户提供了一个进队方法，两个检索队头元素的方法和两个出队的方法，如果队列为空时，分别有一个返回null值，另一个抛出NoSuchElementException异常。用户可根据自己的需进行选取。

Deque

Deque是”double ended queue”，即为双端队列。相信在很多数据结构的书都把双端队列称为高级数据结构的一种。双端队列提供的灵活性比队列要大，但它的逻辑意义和实现绝对不会比队列要难很多，因此，在我们看来，双端队列还是很容易使用的。

Deque从Queue接口继承而来，因而能提供基本的队列操作。然而它最富有特色的地方是可以在两端进行插入和删除操作。下面是该接口的详细说明。

方法概述
void	addFirst(E e) 在前端插入元素。
void	addLast(E e) 在尾端插入元素。
Iterator<E>	descendingIterator() 返回双端队列中元素的逆序迭代器。
E	getFirst() 查看前端元素，但不删除。
E	getLast() 查看尾端元素，但不删除。
Iterator<E>	iterator() 返回双端队列元素的迭代器。
boolean	offerFirst(E e) 在前端插入元素。
boolean	offerLast(E e) 在尾端插入元素。
E	peekFirst() 查看前端元素。
E	peekLast() 查看尾端元素。
E	pollFirst() 查看并删除前端元素。
E	pollLast() 查看并删除尾端元素。
void	push(E e) 在前端插入元素，此时双端队列可看作栈进行操作。
E	pop() 在前端删除元素，此时又端除列可看栈进行操作。
E	removeFirst() 查看并删除前端元素。
E	removeLast() 查看并删除尾端元素。

从双端队列提供的接口中可以看出来，它与队列的接口很类似。对在两端进行查看，和删除都提供了两种方法，在处理双端队列为空时一个返回null值，一个抛出NoSuchElementException

异常。此外，双端队列还提供栈的接口，push和pop这两个方法是专为栈而设置的。最后双端队列仍然是一个队列。

Map

写到这里，突然想到Java集合框架里面还有一个接口，那就是Map。它提供一个从键映射到值的数据结构，我们姑且把它称为映射吧。映射中不能包含重复的键，每个键最多映射到一个值上。从直观上分析Map也应是Collection，因为Map里面装着很多元素，不同的是元素是一个<Key-Value>对而已。但API设计人员并没有把Map从Collection中扩展而来，这与Eclipse不从Circle中扩展而来有异曲同工之妙：两者有功能是具有相同的部分，但在细节和接口上还是有很多的差别。在面向对象中，代码的复用和互操作并不一定得表现在继承上，引用另一个对象也是一种表现方式。Map的设计者采用了后，进而减少两个接口的依赖。下面是Map的主要方法介绍。

方法概述
boolean	containsKey(Object key) 返回映射是否包含键key，如是返回true，否则false。
boolean	containsValue(Object value) 返回映射是否有键映射到值value中，如有则返回true，否则false。
Set<Map.Entry<K,V>>	entrySet() 返回映射中的所有<key-value>对的集合。
V	get(Object key) 返回映射中键key所对应的值，如不存在key则返回null。
boolean	isEmpty() 如果映射不<key-value>对，则返回true，否则为false。
Set<K>	keySet() 返回映射中所有键的集合。
V	put(K key, V value) 指定键key所关联的值value。
void	putAll(Map<? extends K,? extends V> m) 把m中所有<key-value>对加入当前映射中。
V	remove(Object key) 删除键key所对应的<key-value>对。
Collection<V>	values() 返回映射中所有值的Collection形式。

Map虽然不从Collection中扩展而来，但它与Collection的关系还是很紧密地联系在一起。Map主要提供了增加、更改和删除<.key-value>对的操作。同时还返回<key-value>对、键以及值的集合视图，以方便使用。

Java集合框架中Collection的实现

上面分析了Java集合框架提供的接口，这一节点我们继续对它的各种实现进行剖析。Java API的设计者想人所想，对不同接口根据不同的物理结构，分别作出不同的实现，如有的采用链表进行实现，也有采用哈希散列的方法以及红黑树（一种平衡二叉树）等方法进行实现。Collections中的所有实现中，类名都采用了<Implementation-style><Interface>这样的命名方式，下表是各种接口在不同的物理结构下实现。

		Implementations
		Hash Table	Resizable Array	Balanced Tree	Linked List	Hash Table + Linked List
Interfaces	Set	HashSet		TreeSet		LinkedHashSet
	List		ArrayList		LinkedList
	Deque		ArrayDeque		LinkedList
	Map	HashMap		TreeMap		LinkedHashMap

上面的各种实现，所提供的接口与它直接implements的接口有一样的方法。因此它们在implements过程中没有提供额外的方法。在此，我们需要分析各种实现的性能和效率。

Resizable Array实现方式

Resizable Array方式类似于动态数组，对象分配一个数组，也即物理结构上分配在一块连续内存区域里面。由于Java中不存在动态数组，它是采用基本数据功能而完成的。首先是对象先new一定固定大小的数据对象，大小可以根据默认值或用户指定；此后把要加入Collections的对象依次放到数组中，如果数组放满时，再申请一个原来更大的数组，然后把原来数组的内存拷贝到新数组中，然后再加入元素。采用Resizable Array实现方式的数据结构有ArrayList和ArrayDeque。对于ArrayList来说，由于采用数组的结构方式，所以ArrayList所提供的随机访问方法很高效，同时有列表最后位置添加和删除元素的效率也很高，不适合在其它位置频繁进行插入和删除元素操作，因此它要对数组中很大部分元素要进行移动才能完成，这就使得插入和删除元素的代价为O(n)，n为元素个数。ArrayDeque采用数据结构上的循环队列来储存对象。当分配的数组大小不够的时候，重新分配一个原来大小两倍的数组，然后再拷贝过去。原来的队列和队尾位置信息不变。通过采用循环队列的组织形式，双端队列的在两端的插入和删除元素的代价均为O(1)。

Linked List实现方式

Linked List方式采用双向链表的实现方式，List和Deque接口均由LinkedList对象实现。LinkedList由于采用了双向链表的实现形式，它与ArrayList有着互补的特性。它支持高效的频繁插入和删除元素操作，但随机访问的效率却很低。不要忘记LinkedList也实现了Deque接口，LinkedList除了是链表，同时也是队列和双端队列，并且也可以把它看作栈（它提供了栈操作的两个方法）。LinkedList作为队列来说，它在两端的插入和删除元素操作的代价同样是O(1)，但由于里面要维护双向链表的数结构，与ArrayDeque相比，效率稍低一点。

Balanced Tree实现方式

Balanced Tree即平衡二叉树。它里面维护是的二叉树的数据结构，并且是平衡的。每个子树的高度相差不过1，使得插入、删除和查找元素的代价为O(logn)。Java集合框架中的平衡二叉树采用红黑树，而非采用AVL平等二叉树（很多类库如STL都采用红黑树来实现set类）。采用了平衡二叉树的数据结构，在结构是有序的，即元素间是可比较的，因此，插入元素和删除元素以及查找元素的代价均为O(logn)。采用这种实现方式的类有TreeSet和TreeMap，在内部结构都采红黑树作为底层数据结构。使用TreeSet或TreeMap类的好处是，他们内部是有序的，当操作它们要求元素的大小有严格要求时（如每次取出最小的），它提供的方法是相当高效的。

Hash Table实现方式

Hash Table即哈希表，它的神奇之处是通各对象的哈希码值映射到对象所储存的物理地址。当元素间有哈希冲突时，Java集合框架采用链地址法，即把具有相同hash Code的对象放在一个链表中。学习过哈希表的朋友还会记得哈希表中有一个重要的参数，那就是装填因子a，它表示哈希表的装满程度。装填因子越小，则产生冲突的机会就会越小，反之亦然。哈希表的平均查找长度跟有直接的关系，如果采用链地址法解决哈希冲突问题，那么哈希表的查找长度为1+a/2。通常Java集合框架中的装填因子默认值为0.75，也可以用户自行指定。从哈希表方式的平均查找长度可以得知，它的查找方法是相当高效的，平均长度不超1.5，能快速定位，而基于平衡二叉树的平均查找长度是O(logn)。因此，需要快速查找元素的应用可以使用哈希表的实现方式。但是，哈希表的实现形式由于装填因子小于1，因此浪费了部分无用的储存空间，即要求系统为n个元素的哈希表分配多于n个元素的空间，通常是成倍数关系并且与装填因子有关。HashSet和HashMap都采用哈希表的实现方式，能提供快速的查找方法，代价是常数级的。基于哈希表和平衡二叉树实现方式的实现各有千秋：哈希表实现方式查找方法快速高效，而平衡二叉树需要对数级的代价；平衡二叉树的实现方式提供按元素大小关系的访问方式，这点是哈希表实现方式所不能及的。如果在应用中需在快速查找，同时也需要利用元素的大小关系进行操作，最好的方法莫过于利用两种对种的组合：分别生成两个类的对象各一个，保持两个对象数据的一致性；如需要快速查找时，只需用哈希表方式实现的对象进行查找，而要利用大小关系时，可访问平衡二叉树方式实现的对象；这样的优点是运行效率高，缺点是点用系统内存更大。

Hash Table + Linked List实现方式

Hash Table+LinkedList实现方式即哈希表与双向连表的实现方式，这种方式与Hash table方式大致相同，不同的地方是在原来的结构上增加了一个双向链表维护容纳的对象。由于增加了维护链接列表的开支，其性能很可能会比Hash Table稍逊一筹，但有一点是例外的：在Hash Table+LinkedList实现方式中迭代所有元素需要的时间与集合的大小成正比，而与容量无关；在Hash实现方式中迭代所有元素很可能支出较大，因为它所需迭代时间与其容量成正比。基于此实现方式的类有HashLinkedListSet和HashLinkedMap，都类于HashSet和HashMap，提供的接口也一致。

线程安全问题

上述的Collections实现都是非线程安全的。如果多个线程同时访问同一个Collections时，则它必须保持外部同步。一般通过对自然封装该集合的对象进行同步操作来完成，如果不存在这样的对象，则应该使用Collections.synchronizedSet 方法来“包装”该集合。最好在创建时完成这一操作，以防止意外的非同步访问：

List l = Collections.synchronizedList(new LinkedList(…));

Set s = Collections.synchronizedSet(new LinkedHashSet(...));

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

这三个方法是Collections类（一个算法类）提供生产线程安全的集合，更详细说明请参考Java API说明文档。

Java集合框架中的算法

Java.util包里面除了提供丰富的数据结构会，还提供了大量的算法，这些算法在Collections类中。Collections是集合的算法类，所提供的算法通过static方法来实现，下面对Collections提供的算法进行说明。

排序算法（sort）

Collections类为列表(List)提供了排序算法，可按自然顺序或用户指定排序进行排序。Collections提供的排序算法是改进的合并排序算法，并且是稳定的排序算法，能保证性能是nlog(n)。它将列表先转换成数组，然后再对数组进行排序，这是由于排序过程中要实现随机访问过程。

查找算法(binarySearch)

Collections类为列表提供了一个高效的查找算法，二分查找算法。在调用此算法前，列表必须是有序的，否则结果不可预知。

除了上述两个为List提供的重要算法外，Collections类为所有Collection提供了很多通用的算法，如copy(复制)、fill(填充)、max(最大值)、min（最小值）和reverse(逆序)等算法，更多的算法请参考Java API的说明文档。

Java集合框架的基础类(Infrastructure)

Java库类的开发人员把迭代器，顺序称为集合框中的基础设施，我们这里把它称作基础类。

使用迭代器，可以有效地遍历集合的所有元素而不需了解它的物理结构，提供了一种透明的访问机制。Iterator是一种单向的迭代器，沿着next进行该问所有元素，只能删除元素，而不能改更元素对象；ListIterator是一种双向的迭代器，可以向前和向后访问，同时能够删除元素，也能更元素。迭代器是整个集合框中所有集合的粘合剂，无须了解集合的物理结构就可以遍历集合的所有元素。除了List接口提了了按下标访问集合元素外，其它集合都没有提供。因此，要遍历这些集合中的元素，只能通常迭代器遍历或转换成数组再进行随机访问。故迭代器在集合框架中功不可没。

部分集合（如TreeSet和TreeMap）要求元素是有序的，即可能相互比较的。Java集合框架中使用Comparable和Comparator这两个接口来实现元素的相互比较。一个类implements Comparable接口，那么它的对象是自然有序的，可排序的。如果某个类没有implements Comparable接口，那么可以使用另外一个类implements Comparator接口，来制定该类中对象的排序依据，使它在外界对象（比较器）的作用，也是可以有序的。值得一提的是，Comparable和Comparator这两个接口之中并没有重复的部分，也就是不能说一个类implements了Comparator，就不需要提供它的Comparator，这不是绝对的。String类implemetns了Comparable接口，如果想改变它的比较方法的话，那就显得无能为力了；但是我们可能以通过提供另一个比较器