接口
集合核心接口（core collection interfaces）包含了多种类型的集合。如下图所示：
图表 1：集合核心接口
所有的接口都是泛型接口，声明形式如下：
public interface Collection<E>...
当创建一个集合实例时，需要指定放入集合的数据类型。指定集合数据类型使得编译器能检查放入集合的数据类型是否正确，从而减少运行时错误，关于泛型更多知识，请参看泛型相关章节。
Collection接口
遍历Collection
Collection的批量操作
Collection和数组间的转换
Set接口
Set接口基本操作
Set接口批量操作
Set和数组间的转换
List接口
与Vector的比较
List接口基本操作
按位置访问和查询
List迭代器
List子集合操作
List算法
Queue接口
Map接口
Map接口基本操作
Map接口批量操作
集合视图
对象排序
编写自己的可比较类型
比较器
SortedSet接口
SortedSet基本操作
标准构造函数
终端点操作
SortedMap接口
接口小结
Collection接口
Collection接口是所有集合接口的基类，提供了集合接口的通用操作。其定义如下：
public interface Collection<E> extends Iterable<E> {
// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element); //optional
boolean remove(Object element); //optional
Iterator<E> iterator();
// Bulk operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c); //optional
boolean removeAll(Collection<?> c); //optional
boolean retainAll(Collection<?> c); //optional
void clear(); //optional
// Array operations
Object[] toArray();
<T> T[] toArray(T[] a);
}
通过这些操作函数，我们可以进行获取集合中元素的个数 (size, isEmpty)，判断集合中是否包含某个元素(contains)，在集合中增加或删除元素(add, remove)，获取访问迭代器(iterator)等操作。
遍历Collection
有两种方式可以实现对集合的遍历：
for-each 循环
for-each 循环能以一种非常简洁的方式对集合中的元素进行遍历，如下所示：
for (Object o : collection)
System.out.println(o);
迭代器
迭代器（Iterator）可以用来遍历集合并对集合中的元素进行删操作。 可以通过集合的iterator 函数获取该集合的迭代器。 Iterator接口如下所示：
public interface Iterator<E> {
boolean hasNext();
E next();
void remove(); //optional
}
当集合中还有元素供迭代器访问时，hasNext函数返回true。此时，可以通过next函数返回集合中的下一个元素。 函数remove删除next()最后一次从集合中访问的元素。
注意：Iterator.remove是在迭代过程中修改collection的唯一安全的方法，在迭代期间不允许使用其它的方法对collection进行操作。
下列情况下，需要使用迭代器代替for-each循环：
· 删除当前节点： for-each隐藏了迭代器，故无法调用remove函数。正因如此，for-each不能用来对集合过滤。
· 在多重集合上进行并行迭代
下列代码演示了如何使用 Iterator对 Collection元素过滤（遍历集合，并删除特定元素）：
static void filter(Collection<?> c) {
for (Iterator<?> it = c.iterator(); it.hasNext(); )
if (!cond(it.next()))
it.remove();
}
Collection的批量操作
集合的批量操作接口函数如下：
containsAll— 检查集合中是否包含指定集合addAll— 在集合中加入指定集合removeAll— 在集合中删除包含于指定集合的元素retainAll—删除集合中不包含于指定集合的元素clear— 删除集合中所有元素
在addAll, removeAll及 retainAll 操作中，如果集合的元素被更改，则返回true。
下列代码演示了如何从一个集合中移除所有包含特定值的元素：
c.removeAll(Collections.singleton(e));
另外一个常用的批量操作是移除集合中所有的null元素：
c.removeAll(Collections.singleton(null));
Collection和数组间的转换
数组转化为集合：
List<String> c = new ArrayList<String>(…);
集合转化为数组：
String[] a = c.toArray(new String[0]);
Set接口
Set 是一个不包含重复元素的集合（Collection）。Set接口中的函数都是从Collection继承而来。 但限制了add 的使用，需要其不能添加重复元素。
Set接口声明如下：
public interface Set<E> extends Collection<E> {
// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element); //optional
boolean remove(Object element); //optional
Iterator<E> iterator();
// Bulk operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c); //optional
boolean removeAll(Collection<?> c); //optional
boolean retainAll(Collection<?> c); //optional
void clear(); //optional
// Array Operations
Object[] toArray();
<T> T[] toArray(T[] a);
}
Java平台中包含了三个通用的Set的实现： HashSet, TreeSet, 和 LinkedHashSet. HashSet通过hash表存储集合元素。TreeSet通过红黑数存储集合元素。LinkedHashSet通过链表存储集合元素。
假如你有一个集合c，并且你想创建一个包含c中所有不重复元素的集合，可以通过如下方式实现：
Collection<Type> noDups = new HashSet<Type>(c);
如果想在新的Set中保留原始集合的顺序，可以通过如下方式：
Collection<Type> noDups = new LinkedHashSet<Type>(c);
该操作可以通过泛型函数封装如下：
public static <E> Set<E> removeDups(Collection<E> c) {
return new LinkedHashSet<E>(c);
}
Set接口基本操作
Set基本操作和Collection类似，这里就不再累叙
Set的一个基本应用如下所示：
import java.util.*;
public class FindDups {
public static void main(String[] args) {
Set<String> s = new HashSet<String>();
for (String a : args)
if (!s.add(a))
System.out.println("Duplicate detected: " + a);
System.out.println(s.size() + " distinct words: " + s);
}
}
该程序能找出一个字符串中的重复单词，将其打印出来，并且返回所有不重复的单词。
运行程序，
java FindDups i came i saw i left
输出结果如下：
Duplicate detected: i
Duplicate detected: i
4 distinct words: [i, left, saw, came]
Set接口批量操作
Set的批量操作和离散数学的集合操作的概论结合的非常好，假如s1和s2是两个Set，它们间的批量操作如下：
s1.containsAll(s2) —判断s2是否是s1的子集s1.addAll(s2) —将s1转化为s1和s2的并集s1.retainAll(s2) —将s1转化为s1和s2的交集s1.removeAll(s2) —将s1转化为s1和s2的差集
我们来继续看一下前面的FindDups程序。这次我们需要知道那些单词重复出现过，哪些单词只出现过一次，可以修改程序为如下所示：
import java.util.*;
public class FindDups2 {
public static void main(String[] args) {
Set<String> uniques = new HashSet<String>();
Set<String> dups = new HashSet<String>();
for (String a : args)
if (!uniques.add(a))
dups.add(a);
// Destructive set-difference
uniques.removeAll(dups);
System.out.println("Unique words: " + uniques);
System.out.println("Duplicate words: " + dups);
}
}
输入和前面同样的参数(i came i saw i left)，输出结果如下：
Unique words: [left, saw, came]
Duplicate words: [i]
Set和数组间的转换
Set和数组间的转换和Collection和数组间的转换一致，请参看前面相关章节。
List接口
List是一个顺序的Collection（通常被称作序列）。List可以包含重复元素。List接口基本功能如下：
按位置访问 — 通过元素在list中的位置索引访问元素。查询 — 获取某元素在list中的位置迭代 — 扩展了Iterator的接口能实现更多功能List子集合 — 获取List某个位置范围的子集合
List接口如下：
public interface List<E> extends Collection<E> {
// Positional access
E get(int index);
E set(int index, E element); //optional
boolean add(E element); //optional
void add(int index, E element); //optional
E remove(int index); //optional
boolean addAll(int index,
Collection<? extends E> c); //optional
// Search
int indexOf(Object o);
int lastIndexOf(Object o);
// Iteration
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
// Range-view
List<E> subList(int from, int to);
}
Java平台中包含了两个泛型的List的实现：ArrayList和LinkedList。
List与Vector有许多相似之处。List对Vector的一些常用的Api进行了改进，使之更加简单易用。
对于如下元素赋值操作：
a[i] = a[j].times(a[k]);
Vector：v.setElementAt(v.elementAt(j).times(v.elementAt(k)), i);
List：v.set(i, v.get(j).times(v.get(k)));
可以看到，List的元素的获取和设置操作比Vector的更加简洁。
此外，List的add(int, E)对应与Vector的insertElementAt(Object, int)操作，用subList操作统一代替了Vector的indexOf, lastIndexOf和setSize三个操作。
List接口基本操作
List接口实现了所有Collection接口定义的功能，这里就不再累述。
另外，可以通过addAll和inserts进行元素的批量插入操作。
和Set接口一样，List接口增强了两个函数：equals 和hashCode。用以实现比较两个List是否相等（在相同的位置包含相同的元素）。
按位置访问的操作有：get, set, add 和 remove。这些和Vector的相关方法的功能基本一致。
查询操作可以通过indexOf函数返回某元素在List的索引位置信息。
List迭代器
List提供了更加强大的迭代器，能够在迭代过程中能够进行进行添加及修改操作，获取当前位置信息等。ListIterator接口定义如下：
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove(); //optional
void set(E e); //optional
void add(E e); //optional
}
该接口中有三个函数继承自Iterator (hasNext, next, and remove)，并且实现同样的功能。hasPrevious和previous函数使用方式和hasNext和next类似，通过它们组合使用可以实现向前迭代，方式如下：
for (ListIterator<Type> it = list.listIterator(list.size());
it.hasPrevious(); ) {
Type t = it.previous();
...
}
注意listIterator的构造方式，List提供两个函数用来构造listIterator。listIterator()函数返回list起始位置的迭代器，listIterator(index)函数返回list某个位置的迭代器,若某个list的长度为n，则index的取值范围为0到n，如下图所示：
图表 2: 迭代器游标位置
List子集合操作
通过subList(int fromIndex, int toIndex)函数能获取List某个范围的子集合,其中[romIndex, toIndex)是一个左闭右开的半开区间，类似for循环中的区间方式：
for (int i = fromIndex; i < toIndex; i++) {
...
}
由于List子集也是一个List，任何作用与List的操作同样也可以作用与List子集。
List算法
大多数集合算法可以应用于List的，通过这些算法，可以快速有效的实现List的相关操作。常用操作如下：
sort —通过归并排序（merge sort）算法对List进行快速，可靠的排序。shuffle —对List中的元素进行随机放置reverse —对List进行逆序操作rotate — rotates all the elements in a List by a specified distance.swap —交换List中的特定位置的元素replaceAll —替换所有满足特定条件的元素fill — overwrites every element in a List with the specified value.copy —实现对源List和目标List的数据拷贝binarySearch —使用二分查找算法查询List中的元素（List已经排序）indexOfSubList —返回某元素在Sub子集中的位置信息
Queue接口
Queue 是一种保证元素处理顺序（通常是FIFO，但不一定）的集合。除了基本的集合操作外，Queue还提供了自己的插入，访问及删除元素的操作。Queue接口如下所示：
public interface Queue<E> extends Collection<E> {
E element();
boolean offer(E e);
E peek();
E poll();
E remove();
}
Queue函数操作失败有两种处理方式：(1)抛出异常 (2) 返回失败码 (通常是null或false)。下表显示了常用操作的失败处理方式：
|
Queue Interface Structure |
||
|
|
Throws exception |
Returns special value |
|
Insert |
add(e) |
offer(e) |
|
Remove |
remove() |
poll() |
|
Examine |
element() |
peek() |
bounded是一种可以限制元素的数目Queue。java.util.concurrent中定义了一些bounded的实现，java.util中的Queue的实现都不是bounded。
在Queue中插入元素可以通过add函数（继承自Collection）和inserts函数进行，它们的区别是出错时的处理方式不同。
访问Queue中的元素可以通过remove函数（继承自Collection）和poll函数进行，它们的区别是出错时的处理方式不同。
此外，也可以通过element函数（继承自Collection）和peek函数访问Queue中的元素，它们的区别是出错时的处理方式不同。与remove和poll函数不同的是，它们访问Queue后并不删除Queue的元素。
Queue 实现通常通常不允许插入null元素，但LinkedList（实现了Queue接口）却是个例外（由于某些历史原因）。但在使用过程中，应尽量避免将null插入到其中，因为它也是元素访问函数poll和peek执行失败的返回值。
Queue接口中定义的方法都不是阻塞式的，如果要使用阻塞式的Queue，请使用java.util.concurrent.BlockingQueue接口的相应实现类。
下列代码演示了一个Queue作为计时器的应用：
import java.util.*;
public class Countdown {
public static void main(String[] args)
throws InterruptedException {
int time = Integer.parseInt(args[0]);
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = time; i >= 0; i--)
queue.add(i);
while (!queue.isEmpty()) {
System.out.println(queue.remove());
Thread.sleep(1000);
}
}
}
Map接口
Map 是一种包含键值对的元素的集合。Map不能包含重复的键，并可通过键实现对值的快速访问。Map接口如下所示：
public interface Map<K,V> {
// Basic operations
V put(K key, V value);
V get(Object key);
V remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();
// Bulk operations
void putAll(Map<? extends K, ? extends V> m);
void clear();
// Collection Views
public Set<K> keySet();
public Collection<V> values();
public Set<Map.Entry<K,V>> entrySet();
// Interface for entrySet elements
public interface Entry {
K getKey();
V getValue();
V setValue(V value);
}
}
Java平台中包含了三种通用的Map实现：HashMap, TreeMap和LinkedHashMap。 此外，哈希表（Hashtable）也实现了Map接口。
Map接口基本操作
Map的基本操作(put, get, containsKey, containsValue, size, and isEmpty) 和哈希表非常相似。下面程序演示了如何从输入字符串中创建单词频度表。
import java.util.*;
public class Freq {
public static void main(String[] args) {
Map<String, Integer> m = new HashMap<String, Integer>();
// Initialize frequency table from command line
for (String a : args) {
Integer freq = m.get(a);
m.put(a, (freq == null) ? 1 : freq + 1);
}
System.out.println(m.size() + " distinct words:");
System.out.println(m);
}
}
运行程序：
java Freq if it is to be it is up to me to delegate
输出参数如下：
8 distinct words:
{to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}
与Set和List接口类似，Map也加强了equals和hashCode函数，使得可以比较两个Map对象是否包含相同的集合元素。
为了转换方便，所有的泛型Map实现都提供了如下形式的构造函数：
Map<K, V> copy = new HashMap<K, V>(m);
Map接口批量操作
Map接口批量操作主要为clear和putAll两个函数，这里就不多介绍了。
Map的集合视图方法使得Map可以以集合的形式展现其元素。Map的集合视图有如下三种形式：
keySet — Map中包含的键的数据集values — Map中包含的值的数据集entrySet — Map中包含的键值对的数据集
通过Map的集合视图可以实现对Map中的元素遍历,方式如下：
for (Map.Entry<KeyType, ValType> e : m.entrySet())
System.out.println(e.getKey() + ": " + e.getValue());
对象排序
Java平台中提供了Comparable接口实现对象间的大小比较。Java平台中实现了Comparable接口的常用类有：
|
Classes Implementing Comparable |
|
|
Class |
Natural Ordering |
|
Byte |
Signed numerical |
|
Character |
Unsigned numerical |
|
Long |
Signed numerical |
|
Integer |
Signed numerical |
|
Short |
Signed numerical |
|
Double |
Signed numerical |
|
Float |
Signed numerical |
|
BigInteger |
Signed numerical |
|
BigDecimal |
Signed numerical |
|
Boolean |
Boolean.FALSE < Boolean.TRUE |
|
File |
System-dependent lexicographic on path name |
|
String |
Lexicographic |
|
Date |
Chronological |
|
CollationKey |
Locale-specific lexicographic |
如果List的元素实现了Comparable接口，可以通过sort方法实现对List中的元素排序，使之顺序排列。
如果List的元素没有实现Comparable接口，调用sort函数则会ClassCastException抛出异常，因为sort函数不知道如何比较List中的元素大小。
Comparable接口声明如下：
public interface Comparable<T> {
public int compareTo(T o);
}
compareTo的返回值表示的意义如下：
<0:表明源对象小于目标对象=0： 表明源对象等于目标对象>0:表明源对象大于目标对象
下列代码实现了一个可以比较大小的人名对象：
import java.util.*;
public class Name implements Comparable<Name> {
private final String firstName, lastName;
public Name(String firstName, String lastName) {
if (firstName == null || lastName == null)
throw new NullPointerException();
this.firstName = firstName;
this.lastName = lastName;
}
public String firstName() { return firstName; }
public String lastName() { return lastName; }
public boolean equals(Object o) {
if (!(o instanceof Name))
return false;
Name n = (Name)o;
return n.firstName.equals(firstName) &&
n.lastName.equals(lastName);
}
public int hashCode() {
return 31*firstName.hashCode() + lastName.hashCode();
}
public String toString() {
return firstName + " " + lastName;
}
public int compareTo(Name n) {
int lastCmp = lastName.compareTo(n.lastName);
return (lastCmp != 0 ? lastCmp :
firstName.compareTo(n.firstName));
}
}
下列代码演示了建立一个人名序列，并对其排序：
import java.util.*;
public class NameSort {
public static void main(String[] args) {
Name nameArray[] = {
new Name("John", "Lennon"),
new Name("Karl", "Marx"),
new Name("Groucho", "Marx"),
new Name("Oscar", "Grouch")
};
List<Name> names = Arrays.asList(nameArray);
Collections.sort(names);
System.out.println(names);
}
}
运行程序，输出结果如下：
[Oscar Grouch, John Lennon, Groucho Marx, Karl Marx]
如果两个对象没有实现Comparable 接口，可以通过自比较器对象实现对象的大小比较。比较器对象是一个实现了Comparator接口的对象。Comparable接口声明如下：
public interface Comparator<T> {
int compare(T o1, T o2);
}
该接口的compare函数接受两个对象参数，通过返回值表示两个对象的大小。
假定现在有一个如下所示的Employee类：
public class Employee implements Comparable<Employee> {
public Name name() { ... }
public int number() { ... }
public Date hireDate() { ... }
...
}
默认的排序方式是按名称排序，但我们需要按雇佣日期实现对雇员信息重新排序，可以通过如下方式实现：
import java.util.*;
public class EmpSort {
static final Comparator<Employee> SENIORITY_ORDER =
new Comparator<Employee>() {
public int compare(Employee e1, Employee e2) {
return e2.hireDate().compareTo(e1.hireDate());
}
};
// Employee database
static final Collection<Employee> employees = ... ;
public static void main(String[] args) {
List<Employee>e = new ArrayList<Employee>(employees);
Collections.sort(e, SENIORITY_ORDER);
System.out.println(e);
}
}
SortedSet接口
SortedSet是一类特殊的Set，在SortedSet中的元素是按大小顺序排列的。
SortedSet接口声明如下：
public interface SortedSet<E> extends Set<E> {
// Range-view
SortedSet<E> subSet(E fromElement, E toElement);
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement);
// Endpoints
E first();
E last();
// Comparator access
Comparator<? super E> comparator();
}
SortedSet基本操作
SortedSet 继承自Set，大多数操作是一致，SortedSet操作的特殊之处在于：
迭代器是按照元素大小遍历toArray返回的数组是按照元素大小排序的
此外，尽管接口中没有强制要求，Java平台下的SortedSet实现的toString 函数返回的字符串中的元素也是顺序打印的。
为了转换方便, 所有Collection实现都提供了一个标准的构造函数，使之能从另一个Collection初始化数据。SortedSet实现也不例外，除此之外，SortedSet构造函数一般还能加上一个比较器的参数，使之按照自定义比较算法排序。
SortedSet接口提供了first和last两个函数来返回集合的起始和结尾的元素。如下所示：
Object predecessor = ss.headSet(o).last();
SortedMap接口
SortedMap是一类键按大小顺序排列的特殊的Map。 接口定义如下：
public interface SortedMap<K, V> extends Map<K, V>{
Comparator<? super K> comparator();
SortedMap<K, V> subMap(K fromKey, K toKey);
SortedMap<K, V> headMap(K toKey);
SortedMap<K, V> tailMap(K fromKey);
K firstKey();
K lastKey();
}
SortedMap的特性和SortedSet类似，这里就不多做接受了。
接口小结
集合接口interfaces使得集合操作独立于其具体实现。Java集合框架继承结构由两颗接口树构成：
第一棵树的根节点为Collection接口，它定义了所有集合的基本操作——如添加、删除、遍历等。它的子接口为——Set, List和 Queue。它们提供了更加特殊的功能。Set接口不包含重复元素。它有一个子接口——SortedSet，SortedSet 中的元素是按大小顺序排列的。List接口保存了元素的位置信息，可以通过位置索引来访问List中的元素。Queue接口保证了元素的访问顺序（FIFO等）。第二棵树根节点为Map接口，和哈希表类似，保持的是键值对的集合，可以通过键来实现对值元素的快速访问。Map接口的子接口为SortedMap，SortedMap中的键是按照大小顺序排列的。