下面按照Collection、Set、List、Map的顺序分别讲述Java平台的集合接口，最后讲述集合的同步方法。
（1）单元素添加、删除操作。
boolean add(Object o)：将对象添加到集合中。
boolean remove(Object o)：从集合中删除对象o，如果对象o在集合中存在。
【例6-4】下面的代码说明了add( )方法的用法。
import java.util.*;
public class CollectionOp1 {
public static void main(String args[]) {
Collection c = new ArrayList();
for (int i=0; i < args.length ; i++)
c.add(args[i]);
System.out.println("Collection: " + c);
}
}
如果运行的参数为：
E:>java CollectionOp1 a b c d
则运行结果如下：
Collection: [a, b, c, d]
（2）查询操作。
int size( )：返回当前集合中元素的个数。
boolean isEmpty( )：判断集合是否为空集合。
boolean contains(Object o)：查找集合中是否含有对象o。
Iterator iterator( )：返回一个迭代器，用以访问集合中的各个元素。
【例6-5】本例说明了Collection的查询操作。
import java.util.*;
public class CollectionOp2 {
private static String str[] = {"one","two","three","four", "five"};
public static void main(String args[]) {
Collection c = new ArrayList();
for (int i=0; i < str.length ; i++)
if (c.add(str[i]))
System.out.println("adding \""+ str[i] + "\"");
if(c.remove(str[0]))
System.out.println("removing \"" + str[0] + "\"");
System.out.println("Collection: " + c);
System.out.println("Collection's size: " + c.size());
System.out.println("Is collecion empty? " + c.isEmpty());
System.out.println("Does collection contain " + str[0] + "? " +
c.contains(str[0]));
System.out.println("Does collection contain " + str[1] + "? " +
c.contains(str[1]));
}
}
这个例子的输出如下：
adding "one"
adding "two"
adding "three"
adding "four"
adding "five"
removing "one"
Collection: [two, three, four, five]
Collection's size: 4
Is collecion empty? false
Does collection contain one? false
Does collection contain two? true
（3）组操作，作用于元素组或整个集合。
boolean containsAll(Collection c)：查找集合中是否含有集合c中所有元素。
boolean addAll(Collection c)：将集合c中所有元素添加到该集合中。
void clear( )：删除集合中所有元素。
void removeAll(Collection c)：从集合中删除集合c 中的所有元素。
void retainAll(Collection c)：从集合中删除集合c 中不包含的元素。
（4）将Collection转换为Object数组。
Object[ ] toArray( )：返回一个内含集合所有元素的array。
Object[ ] toArray(Object[ ] a)：返回一个内含集合所有元素的array。运行时返回的array和参数a的类型相同，需要转换为正确类型。toArray方法可作为集合和数组之间的一个桥梁，它允许将一个Collection的内容转换为一个数组。没有参数的简单形式创建了一个新的Object（对象）数组。更复杂的形式允许调用者提供一个数组或选择这个输出数组的运行时类型。例如，假设c是一个Collection，如下程序可将c的内容倾卸到一个新分配的Object数组中，数组的长度与c中元素的数量相同。
Object[] a = c.toArray();
假设已知c仅包含字符串。下列程序则将c的内容倾卸到一个新分配的String数组中，数组的长度与c中元素的数量相同。
String[] a = (String[]) c.toArray(new String[0]);
Collection不提供get()方法。如果要遍历Collectin中的元素，就必须用Iterator（迭代器）。
Collection接口的iterator()方法返回一个Iterator。Iterator接口方法能以迭代方式逐个访问集合中各个元素，并安全地从Collection中除去适当的元素。它有以下3个方法。
boolean hasNext( )：判断是否存在另一个可访问的元素。
Object next( )：返回要访问的下一个元素。如果到达集合结尾，则抛出NoSuchElement Exception。
void remove( )：删除上次访问返回的对象。本方法必须紧跟在一个元素的访问后执行。如果上次访问后集合已被修改，方法将抛出IllegalStateException。
需要注意的是，如果正在用Iterator 遍历集合，而另一个线程正在修改底层集合，Iterator就会抛出ConcurrentModificationException（另一种RuntimeException）并立刻失败。
AbstractCollection 类提供了对java.util.Collection 接口中除iterator( )和size( )方法以外的所有方法的实现。AbstractCollection类提供了一个Collection接口的实现框架，这个框架为实现Collection接口提供了方便。开发者可以通过继承AbstractCollection类来实现Collection接口，只需要提供iterator( )和size( )方法。
Set接口继承Collection 接口，而且它不允许集合中存在重复项，每个具体的Set接口实现类依赖添加的对象的equals( )方法来检查唯一性。Set接口没有引入新方法，所以Set就是一个Collection接口，只不过其行为不同。
哈希表（Hash Table）是一种数据结构，用来快速查找对象。哈希表利用一个哈希函数为每个对象计算出一个值，这个值就是哈希码。哈希表是个链接式列表的阵列。每个列表称为一个桶（Bucket）。对象的位置计算按照下面的公式。
index = HashCode % buckets
其中，HashCode为对象的哈希码，buckets为桶的总数。
添加元素时，哈希表根据哈希函数计算出元素的哈希码，并根据上述的公式计算出元素应该处于的位置，然后把这个元素放入相应的桶。
有时会遇到这种情况：某两个元素的哈希码完全一样，导致这两个元素的位置一样，这种情况称为哈希冲突。如果哈希码是合理地随机分布的，并且桶的数量足够大，那么哈希冲突的数量就会减少。同时，也可以通过设定一个初始的桶的数量来更好地控制哈希表的运行。初始哈希表元的数量为buckets = size * 150% + 1 (size为预期元素的数量)。
如果哈希表中的元素放得太满，就必须进行再哈希（Rehashing）。再哈希使哈希表元数量增倍，并将原有的对象重新导入新的桶中，而原始的哈希表元被删除。负载因子（Load Factor）决定何时要对哈希表进行再哈希。在Java语言中，负载因子默认值为0.75，默认哈希表元为101。
equals( )方法实现了如下等价关系。
· 自反性：对于任何对象x，x.equals(x)必须返回true。
· 对称性：对于任何对象x和y，如果有x.equals(y)==true，则y.equals(x)==true。
· 传递性：对于任何对象x、y和z，如果x.equals(y)==true和y.equals(z)==true，则x.equals(z)==true。
· 一致性：对于任何对象x和y，只要没有对x、y进行修改，多次的x.equals(y) 调用应该返回相同的值。
对于任何non-null对象x，都有x.equals(null)==false。
Object类中这个方法被实现为严格相等，也就是说，如果比较的两个对象是同一对象，即“==”操作为true，则返回true。所以如果想在集合中搜索内容相等的成员对象，或在map中获取内容相等的键映射的值，成员对象（或键对象）的类必须覆盖equals(Object o)方法。
hashCode( )方法返回一个对象的Hash 代码，在哈希表数据结构实现的集合中，它决定了这个对象被放到哪个桶中；而equals( )方法则是进一步到桶中寻找具体对象的依据。
为了哈希表数据结构能正常工作，hashCode( )方法的通用协议是：equals( )方法定为相等的两个对象的hashCode( )返回的值一定相同，只有这样才能在哈希表数据结构中找到这个对象；而equals( )方法定为不相等的两个对象的hashCode( )返回的值可以不相同，如果相同将导致哈希冲突。所以尽量保证equals( )方法定为不相等的对象的hashCode( )值不相同。
类Object实现的hashCode( )方法使用对象的内部地址转化为整数返回，在调用o1.equals(o2)这个方法时，只有o1.hashCode( )== o2.hashCode( )为true, ol.equals(o2)才会为true。
Java集合框架提供了两种比较接口：Comparable接口和Comparator接口。
String、Integer等内建类通过实现Comparable接口以提供比较的功能。Comparable接口声明了唯一一个方法：
int compareTo(Object o)
这个方法比较当前实例对象与对象o，如果位于对象o之前，返回负值；如果两个对象在排序中位置相同，则返回0；如果位于对象o后面，则返回正值。
Comparable接口用于实现“自然排序”，例如：BigDecimal、BigInteger、Byte、Double、Float、Integer、Long、Short等类按照其代表的数字的大小排序；Character类按照其代表的字符的Unicode值的大小排序；String类按照字符串中的字符的Unicode值的大小排序。
利用Comparable接口创建自己的类的排序顺序，只需要实现这个接口的compareTo( )方法，同时应该覆盖equals( )和hashCode( )方法以确保两个相等的对象返回同一个哈希码。
利用Comparable接口创建自己的类的排序顺序还需要注意的是，对compareTo( )方法的实现必须满足：如果x.compareTo(y)的值为0，则y.compareTo(x)值为0；如果x.compareTo(y)的值为正数，则y.compareTo(x)值为负数，反之亦然；如果x.compareTo(y)抛出异常，则y.compareTo(x)也应当抛出异常。
而且，对compareTo( )方法的实现必须有传递性，即对任何x、y、z，有：(x.compareTo(y)>0 && y.compareTo(z)>0) 则x.compareTo(z)>0。
最后，对compareTo( )方法的实现必须保证：如果x.compareTo(y)==0，则x.compareTo(z)和y.compareTo(z)返回值的正负符号一样。
对集合C中的任何e1和e2，当且仅当(e1.compareTo((Object)e2) == 0) 和e1.equals ((Object)e2) 的布尔值一样时，称C的自然排序和equals是一致的。对compareTo( )方法的实现最好保证这种一致性。不过，因为null不是任何一个类的实例，因此即使e.equals(null)返回false，e.compareTo(null)也应当抛出一个NullPointerException。
【例6-6】下面的代码是一个实现了Comparable接口的Name类。
import java.util.*;
public class Name implements Comparable {
private 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(Object o) {
Name n = (Name)o;
int lastCmp = lastName.compareTo(n.lastName);
return (lastCmp!=0 ? lastCmp :
firstName.compareTo(n.firstName));
}
}
如果由于某种原因不能实现java.lang.Comparable，或者某个类默认的Comparable的行为不能适应任务，则可以实现Comparator接口，实现自己的比较方法，从而定义一个比较器。
这个接口对一个集合的对象作全序排序，实现了这个接口的类的对象能在Collections
.sort( )方法、TreeSet和TreeMap等数据结构中控制排序结果。
对于一个集合中的成员来说，一个Comparator对象和equals 一致，当且仅当这个对象的方法compare( )对于任意两个成员e1和e2，(compare((Object)e1, (Object)e2)==0)和e1.equals((Object)e2)有同样的逻辑值时。和Comparable接口一样，强烈要求保持这种一致性。
对Comparator接口的compare( )方法的要求如下：
当e1的位置在e2前面时，compare((Object)e1, (Object)e2) < 0。
当e1的位置在e2后面时，compare((Object)e1, (Object)e2) > 0。
当两个对象无法比较时，应该抛出ClassCastException 异常。
一个类只能实现一次Compareble接口，也就是说，某个类实现了Compareble接口，它的compareTo()行为就固定下来了；而对于某一个类，Comparator接口可以实现多个，以适应不同情况下的使用。例如某个Student类，如下所示：
import java.util.*;
public class Student implements Comparable {
public Name name;
public int age;
……
}
我们可以实现一个根据其name排序的Comparator接口，还可以实现一个根据其age排序的Comparator接口。
Comparator接口提供以下两个操作。
int compare(Object o1, Object o2)：对两个对象o1和o2进行比较，如果o1位于o2的前面，则返回负值；如果在排序顺序中认为o1和o2是相同的，返回0；如果o1位于o2的后面，则返回正值。与Comparable接口相似，0返回值不表示元素相等，只是表示两个对象排在同一位置。
boolean equals(Object obj)：指示对象obj是否和比较器相等。
该方法覆盖Object类的equals( )方法，检查的是Comparator接口实现的等同性，不是处于比较状态下的对象。
【例6-7】本例说明了Comparator的使用方法，并且实现了一个Comparator接口，用于对Student类的age进行排序。
import java.util.*;
public class StudentSort {
static final Comparator AGE_ORDER = new Comparator() {
public int compare(Object o1, Object o2) {
Student r1 = (Student) o1;
Student r2 = (Student) o2;
return r1.age < r2.age? -1: r1.age==r2.age ? 0:1;
}
};
static final Student students[] = {
new Student("John", "Lennon", 14),
new Student("Karl", "Marx", 15),
new Student("Groucho", "Marx",12),
new Student("Oscar", "Grouch", 13)
};
public static void main(String args[]) {
List st = Arrays.asList(students);
Collections.sort(st, AGE_ORDER);
System.out.println(st);
}
}
这个例子的输出如下：
[{Groucho Marx,12}, {Oscar Grouch,13}, {John Lennon,14}, {Karl Marx,15}]
可以看到，输出的结果是按照age排序的。
SortedSet接口是保持元素有序顺序的一种Set。SortedSet接口提供了一些方法，使其可以访问这个Set的第一个元素、最后一个元素或者是中间的某些元素。在Java集合框架中，TreeSet类是SortedSet接口的唯一实现。
不难理解，SortedSet的元素必须实现Comparable接口，否则必须给它的构造函数提供一个Comparator接口的实现。因为SortedSet中的元素排列是有序的，所以要求它的元素必须是可以比较的。
因为Set中的元素是唯一的，给Set添加元素时会引起元素的比较，如果两个元素相等，也就是Comparable的compareTo( )方法或Comparator的compare( )方法返回0，那么新元素就没有添加进去。
SortedSet接口的方法如下。
· Comparator compare( )：返回对元素进行排序时使用的比较器；如果使用Compa-
rable接口的compareTo( )方法对元素进行比较，则返回null。
· Object first( )：返回有序集合中第一个（最低）元素。
· Object last( )：返回有序集合中最后一个（最高）元素。
· SortedSet subSet (Object fromElement, Object toElement)：返回从fromElement（包括）至toElement（不包括）范围内元素的SortedSet的子集。
· SortedSet headSet (Object toElement)：返回SortedSet的一个子集，其内各元素皆小于toElement。
· SortedSet tailSet (Object fromElement)：返回SortedSet的一个子集，其内各元素皆大于或等于fromElement。
这些方法的使用如例6-8所示。
【例6-8】程序示例。
import java.util.*;
public class testSortedSet {
static final Student students[] = {
new Student("John", "Lennon", 14),
new Student("Karl", "Marx", 15),
new Student("Groucho", "Bush",12),
new Student("Oscar", "Grouch", 13)
};
public static void main(String args[]) {
List st = Arrays.asList(students);
SortedSet stSet = new TreeSet(st);
System.out.println(stSet);
Student firstst = (Student)stSet.first();
System.out.println("first: " + firstst);
Student lastst = (Student)stSet.last();
System.out.println("last: " + lastst);
SortedSet headset = stSet.headSet(students[1]);
System.out.println("headSet: " + headset);
SortedSet tailset = stSet.tailSet(students[1]);
System.out.println("tailSet: " + tailset);
SortedSet subset = stSet.subSet(students[2],students[0]);
System.out.println("subSet: " + subset);
}
}
这个程序的运行结果如下：
[{Groucho Bush,12}, {Oscar Grouch,13}, {John Lennon,14}, {Karl Marx,15}]
first: {Groucho Bush,12}
lastS: {Karl Marx,15}
headSet: [{Groucho Bush,12}, {Oscar Grouch,13}, {John Lennon,14}]
tailSet: [{Karl Marx,15}]
subSet: [{Groucho Bush,12}, {Oscar Grouch,13}]
可以看到，整个SortedSet为：
[{Groucho Bush,12}, {Oscar Grouch,13}, {John Lennon,14}, {Karl Marx,15}]
因为Student类实现了Compareble接口，其排序行为是按name排序；而Name类实现Compareble接口的排序行为是先比较lastName，如果一样则再比较firstName。所以first()返回的是：
{Groucho Bush,12}
last( )返回的是：
{Karl Marx,15}
【例6-9】本例程序改写了上例的testSortedSet，而且实现了根据age排序的Comparator接口，并且利用构造函数TreeSet(comparator c)构造了TreeSet。
import java.util.*;
public class testSortedSet2 {
static final Comparator AGE_ORDER = new Comparator() {
public int compare(Object o1, Object o2) {
Student r1 = (Student) o1;
Student r2 = (Student) o2;
return r1.age < r2.age? -1: r1.age==r2.age ? 0:1;
}
};
static final Student students[] = {
new Student("John", "Lennon", 14),
new Student("Karl", "Marx", 15),
new Student("Groucho", "Bush",12),
new Student("Oscar", "Grouch", 13)
};
public static void main(String args[]) {
List st = Arrays.asList(students);
SortedSet stSet = new TreeSet(AGE_ORDER);
stSet.addAll(st);
System.out.println(stSet);
Student firstst = (Student)stSet.first();
System.out.println("firstSet: " + firstst);
Student lastst = (Student)stSet.last();
System.out.println("lastSet: " + lastst);
SortedSet headset = stSet.headSet(students[1]);
System.out.println("headSet: " + headset);
SortedSet tailset = stSet.tailSet(students[1]);
System.out.println("tailSet: " + tailset);
SortedSet subset = stSet.subSet(students[2],students[0]);
System.out.println("subSet: " + subset);
}
}
可以看到，这个程序的输出和testSortedSet不一样了。
[{Groucho Bush,12}, {Oscar Grouch,13}, {John Lennon,14}, {Karl Marx,15}]
firstSet: {Groucho Bush,12}
lastSet: {Karl Marx,15}
headSet: [{Groucho Bush,12}, {Oscar Grouch,13}, {John Lennon,14}]
tailSet: [{Karl Marx,15}]
subSet: [{Groucho Bush,12}, {Oscar Grouch,13}]
AbstractSet类覆盖了Object类的equals()和hashCode()方法，以确保两个相等的集合返回相同的哈希码。若两个集合大小相等且包含相同元素，则这两个集合相等。按照定义，集合的哈希码是Set中元素哈希码的总和。因此，不论集合的内部顺序如何，两个相等的集合会有相同的哈希码。
Java集合框架支持Set接口两种普通的实现：HashSet和TreeSet（TreeSet实现SortedSet接口）。HashSet类的元素是以哈希表的方式存放的，而TreeSet类的元素存放在被称为红黑树（Red-Black Tree）的平衡二叉树中。
HashSet类查找元素要快得多（对大多数操作是对数时间之于常数时间的差别），但HashSet类不提供排序保证。如果需要使用SortedSet中的操作，或者按顺序迭代很重要，那么应该使用TreeSet；否则，使用HashSet。
必须注意的是：HashSet和TreeSet都是非同步的，这意味着如果程序中有多个线程并发访问一个HashSet或者TreeSet，且至少有一个对其进行修改时，开发人员需要做同步处理。
HashSet类的方法如下。
· HashSet( )：构建一个空的HashSet。
· HashSet(Collection c)：构建一个HashSet，并且添加集合c中所有元素。
· HashSet(int initialCapacity)：构建一个拥有特定容量的空HashSet。
· HashSet(int initialCapacity, float loadFactor)：构建一个拥有特定容量和负载因子的空哈希集。LoadFactor是0.0～1.0之间的一个数。
TreeSet类的方法如下。
· TreeSet( )：构建一个空的TreeSet。
· TreeSet(Collection c)：构建一个TreeSet，并且添加集合c中所有元素。
· TreeSet(Comparator c)：构建一个TreeSet，并且使用特定的比较器对其元素进行排序。comparator比较器没有任何数据，它只是比较方法的存放器。这种对象有时称为函数对象。函数对象通常在运行过程中被定义为匿名内部类的一个实例。
· TreeSet(SortedSet s)：构建一个TreeSet，添加s中所有元素，并且使用与有序集合s相同的比较器排序。
为优化HashSet空间的使用，HashSet类提供了调优初始容量和负载因子的方法。而TreeSet不包含调优选项，因为树总是平衡的。
【例6-10】本例说明了HashSet和TreeSet在元素存储速度上的区别。在下面的程序中，让HashSet和TreeSet分别做5000次循环，每次循环插入、删除1000个元素。分别记下它们所消耗的时间并打印出来。
import java.util.*;
public class HashSetAndTreeSet {
private static String str[] = new String[1000];
public static void main(String args[]) {
for(int i=0;i<1000;i++)
str[i]=new String("String"+i);
HashSet hset = new HashSet();
long t1 = Calendar.getInstance().getTimeInMillis();
for(int k=0;k<5000;k++){
for(int i=0;i<1000;i++)
hset.add(str[i]);
for(int i=0;i<1000;i++)
hset.remove(str[i]);
}
long t2 = Calendar.getInstance().getTimeInMillis();
System.out.println("HashSet : " + ((t2-t1)/1000) +" Seconds");
TreeSet tset = new TreeSet();
t1 = Calendar.getInstance().getTimeInMillis();
for(int k=0;k<5000;k++){
for(int i=0;i<1000;i++)
tset.add(str[i]);
for(int i=0;i<1000;i++)
tset.remove(str[i]);
}
t2 = Calendar.getInstance().getTimeInMillis();
System.out.println("TreeSet : " + ((t2-t1)/1000) +" Seconds");
}
}
这个程序的运行结果如下：
HashSet : 5 Seconds
TreeSet : 51 Seconds
可以看到，HashSet和TreeSet的速度区别是非常明显的。
LinkedHashSet类扩展了HashSet类。LinkedHashSet类提供跟踪添加给HashSet的元素的顺序的方法。LinkedHashSet的迭代器按照元素的插入顺序来访问各个元素。它提供了一个可以快速访问各个元素的有序集合。同时，它也增加了实现的代价，因为哈希表元中的各个元素是通过双重链接式列表链接在一起的。
· LinkedHashSet( )：构建一个空的链接式哈希集。
· LinkedHashSet(Collection c)：构建一个链接式哈希集，并且添加集合c中所有元素。
· LinkedHashSet(int initialCapacity)：构建一个拥有特定容量的空链接式哈希集。
· LinkedHashSet(int initialCapacity, float loadFactor)：构建一个拥有特定容量和负载因子的空链接式哈希集。LoadFactor是0.0～1.0之间的一个数。
【例6-11】从本例中可以看到LinkedHashSet类和HashSet类的区别。
import java.util.*;
public class testHashSet {
private static String str[] = {"one","two","three","four", "five"};
public static void main(String args[]) {
Collection c1 = new HashSet();
for (int i=0; i < str.length ; i++)
if (c1.add(str[i]));
Collection c2 = new LinkedHashSet();
for (int i=0; i < str.length ; i++)
if (c2.add(str[i]));
System.out.println("HashSet:");
System.out.print("[");
for(Iterator it = c1.iterator();it.hasNext();){
String element = (String)it.next();
System.out.print(element+" ");
}
System.out.println("]");
System.out.println("LinkedHashSet:");
System.out.print("[");
for(Iterator it = c2.iterator();it.hasNext();){
String element = (String)it.next();
System.out.print(element+" ");
}
System.out.println("]");
}
}
这个程序的输出如下：
HashSet:
[one two five four three ]
LinkedHashSet:
[one two three four five ]
List接口继承了Collection接口以定义一个允许重复项的有序集合。该接口不但能够对列表的一部分进行处理，还添加了面向位置的操作。
（1）面向位置的操作包括插入某个元素的操作和Collection的功能，还包括获取、删除和更改元素的功能。在List中搜索元素可以从列表的头部或尾部开始，如果找到元素，还将报告元素所在的位置。
· void add(int index, Object element)：在指定位置index上添加元素element。
· boolean addAll(int index, Collection c)：将集合c的所有元素添加到指定位置index。
· Object remove(int index)：删除指定位置上的元素。
· Object get(int index)：返回List中指定位置的元素。
· int indexOf(Object o)：返回第一个出现元素o的位置，如果没有这个元素则返回-1。
· int lastIndexOf(Object o)：返回最后一个出现元素o的位置，如果没有这个元素则返回-1。
· Object set(int index, Object element)：用元素element取代位置index上的元素，并且返回旧的元素。
对List中位置i和位置j的元素交换位置的函数如下：
private static void swap(List a, int i, int j) {
Object tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
【例6-12】本例利用swap( )函数把一个List的元素按原来顺序的倒序重新排列。
import java.util.*;
public class swapList {
private static String str[] = {"One","Two","Three","Four", "Five"};
private static void swap(List a, int i, int j) {
Object tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
public static void main(String args[]) {
List list = new ArrayList();
for(int i=0; i<str.length; i++){
list.add(str[i]);
}
System.out.println(list);
for(int i=0;i<list.size()/2;i++){
swap(list,i,list.size()-i-1);
}
System.out.println(list);
}
}
这个程序的输出结果如下：
[One, Two, Three, Four, Five]
[Five, Four, Three, Two, One]
（2）List 接口不但以位置序列迭代遍历整个列表，还能处理集合的子集。
· ListIterator listIterator( )：返回一个列表迭代器，用来访问列表中的元素。
· ListIterator listIterator(int index)：返回一个列表迭代器，用来从指定位置index开始访问列表中的元素。
· List subList(int fromIndex, int toIndex)：返回从指定位置fromIndex（包含）到toIndex（不包含）范围中各个元素的列表视图。
ListIterator接口继承Iterator接口以支持添加或更改底层集合中的元素，还支持双向访问。ListIterator没有当前位置，光标位于调用previous( )和next( )方法返回的值之间。例如，一个长度为n的列表，有n+1个有效索引值，如下所示：
Element(0) Element(1) Element(2) …Element(n)
^ ^ ^ ^ ^
Index：0 1 2 3 n+1
ListIterator接口有以下操作。
（1）元素操作。
· void add(Object o)：将对象o添加到当前位置的前面。
· void set(Object o)：用对象o替代next( )或previous( )方法访问的上一个元素。如果上次调用后列表结构被修改了，那么将抛出IllegalStateException。
（2）查询操作。
· boolean hasPrevious( )：判断向后迭代时是否有元素可访问。
· Object previous( )：返回上一个对象。
· int nextIndex( )：返回下次调用next( )方法时将返回的元素的索引。
· int previousIndex( )：返回下次调用previous( )方法时将返回的元素的索引 。
使用这些方法，可以反向遍历一个链表，如下所示：
ListIterator listItr = list.listIterator(list.size()-1);
while(listItr.hasPrevious()) {
System.out.println(listItr.previous());
}
或者，在一个迭代操作中可以免去使用计数器，如下所示：
ListIterator listItr = list.listIterator();
while(listItr.hasNext()) {
Object obj = listItr.next();
if(someImaginaryTest(obj)) {
anotherList.set(listItr.previousIndex(), obj);
}
}
可以修改正在迭代的链表。下面一个方法是在一个链表中将所有整数设置为0。
ListIterator listItr = list.listIterator();
Integer zero = new Integer(0);
while(listItr.hasNext()) {
Object obj = listItr.next();
listItr.set(zero);
}
利用ListIterator提供的add()方法可以在迭代过程的当前位置之后加入一个对象。例如，要递归迭代一个目录下的所有文件，就可以使用以下代码。
LinkedList list = new LinkedList(new File("/"));
ListIterator listItr = list.listIterator();
while(listItr.hasNext()) {
File file = (File)listItr.next();
if(file.isDirectory()) {
File[] contents = file.listFiles();
for(int i=0; i<contents.length; i++) {
listItr.add(contents[i]);
}
} else {
// do something to the File
}
}
正常情况下，不用ListIterator改变某次遍历集合元素的方向：向前或者向后。虽然在技术上可以实现，但previous( )方法后立刻调用next( )方法，返回的是同一个元素；把调用next( )方法和previous( )方法的顺序颠倒一下，结果相同。
这里还需要再解释一下add( )操作。添加一个元素会导致新元素立刻被添加到隐式光标的前面。因此，添加元素后调用previous( )方法会返回新元素，而调用next( )方法则不起作用，它返回添加操作之前的下一个元素。
有两个抽象的List实现类：AbstractList和AbstractSequentialList。像AbstractSet类一样，它们覆盖了equals( )和hashCode( )方法以确保两个相等的集合返回相同的哈希码。若两个列表大小相等且包含顺序相同的相同元素，则这两个列表相等。这里的hashCode( )在List接口中定义了hashCode( )方法，而在AbstractList实现了这个方法。
除了equals( )和hashCode( )方法，AbstractList和AbstractSequentialList抽象类实现了其余List方法的一部分。因为数据的随机访问和顺序访问是分别实现的，所以使得具体列表实现的创建更为容易。
在Java集合框架中有两种常规的List实现：ArrayList和LinkedList。使用两种List实现中的哪一种取决于特定的需要。ArrayList可以快速随机访问，但当元素的安插或移除发生在List中央位置时，效率很差，因此不宜用ArrayList来进行安插和移除操作。与ArrayList相反，LinkedList适合用来进行安插和移除，但随机访问的速度较慢。此外，可以通过LinkedList来实现stack、queue和deque。
ArrayList和LinkedList都不是同步的，所以涉及到多线程读写时，开发人员需要自己进行同步。
ArrayList 和LinkedList 都实现Cloneable接口，都提供了两个构造函数，一个无参数，一个接受另一个Collection。
LinkedList类添加了一些处理列表两端元素的方法，如下所示。
· void addFirst(Object o)：将对象o添加到列表的开头。
· void addLast(Object o)：将对象o添加到列表的结尾。
· Object getFirst( )：返回列表开头的元素。
· Object getLast( )：返回列表结尾的元素。
· Object removeFirst( )：删除并且返回列表开头的元素。
· Object removeLast( )：删除并且返回列表结尾的元素。
LinkedList类有以下两个构造方法。
· LinkedList( )：构建一个空的链接列表。
· LinkedList(Collection c)：构建一个链接列表，并且添加集合c中的所有元素。
使用这些新方法，就可以轻松地把LinkedList 当作一个堆栈、队列或其他面向端点的数据结构。下面是一个非常简单的Stack的实现，这个Stack支持两个操作：push和pop。
class Stack{
LinkedList list = new LinkedList();
public void push(Object x){
list.addLast( x );
}
public Object pop(){
return list.removeLast();
}
}
ArrayList类封装了一个动态再分配的Object[]数组。每个ArrayList对象都有一个capacity。这个capacity表示存储列表中元素的数组的容量。当元素添加到ArrayList对象时，它的capacity在常量时间内自动增加。
在向一个ArrayList对象添加大量元素的程序中，可使用ensureCapacity()方法增加capacity。这可以减少重分配的数量。
void ensureCapacity(int minCapacity)：将ArrayList对象容量增加minCapacity。
void trimToSize( )：整理ArrayList对象容量为列表当前大小。程序可使用这个操作减少ArrayList对象存储空间。
ArrayList类还实现了RandomAccess接口。这是一个特征接口，该接口没有任何方法，不过可以使用该接口来测试某个集合是否支持有效的随机访问。实现了这个接口的类还有Vector。
【例6-13】本例是用ArrayList实现的一个模拟发牌程序。这个程序首先生成52张扑克牌，然后用Collections.shuffle( )方法打乱牌的顺序，这个操作即模拟洗牌操作，之后根据运行参数进行模拟发牌。发牌函数是dealHand(List deck, int n)，参数n指明每人需要发多少张牌。
import java.util.*;
class Deal {
public static List dealHand(List deck, int n) {
int deckSize = deck.size();
List handView = deck.subList(deckSize-n, deckSize);
List hand = new ArrayList(handView);
handView.clear();
return hand;
}
public static void main(String args[]) {
int numHands = Integer.parseInt(args[0]);
int cardsPerHand = Integer.parseInt(args[1]);
String[] suit = new String[] {"spades", "hearts","diamonds", "clubs"};
String[] rank = new String[]
{"ace","2","3","4","5","6","7","8",
"9","10","jack","queen","king"};
List deck = new ArrayList();
for (int i=0; i<suit.length; i++)
for (int j=0; j<rank.length; j++)
deck.add(rank[j] + " of " + suit[i]);
Collections.shuffle(deck);
for (int i=0; i<numHands; i++)
System.out.println(dealHand(deck, cardsPerHand));
}
}
如果运行命令为：
java Deal 4 5
它的一个可能的输出如下所示：
[ace of spades, 10 of hearts, 2 of spades, 3 of spades, 4 of spades]
[6 of hearts, 4 of clubs, 6 of spades, 10 of clubs, jack of diamonds]
[jack of spades, 7 of hearts, 5 of clubs, 9 of spades, jack of hearts]
[9 of hearts, 7 of spades, 8 of hearts, queen of clubs, 10 of diamonds]
Map接口不是Collection接口的直接继承。Map接口用于维护键-值对(Key-Value Pairs)。该接口描述了从不重复的键到值的映射。
（1）添加、删除操作。
· Object put(Object key, Object value)：将互相关联的一个关键字与一个值放入该Map。如果该关键字已经存在，那么与此关键字相关的新值将取代旧值，方法返回关键字的旧值；如果关键字原先并不存在，则返回null。
· Object remove(Object key)：从Map中删除与key相关的映射。
· void putAll(Map t)：将来自特定Map的所有元素添加给该映像。
· void clear( )：从映像中删除所有映射。
键和值都可以为null。但是不能把Map作为一个键或值添加给自身。
（2）查询操作。
· Object get(Object key)：获得与关键字key相关的值，并且返回与关键字key相关的对象，如果没有在该Map中找到该关键字，则返回null。
· boolean containsKey(Object key)：判断Map中是否存在关键字key。
· boolean containsValue(Object value)：判断Map中是否存在值value。
· int size( )：返回当前Map中元素的数量。
· boolean isEmpty( )：判断Map中是否为空。
（3）视图操作，处理Map中键-值对组。
· Set keySet( )：返回Map中所有关键字的视图集。
因为Map中键必须是唯一的，所以返回的是一个Set类型。从所返回的Set中删除元素会导致关键字和它相关的值从Map中被删除，因此从所返回的Set中不能删除元素。
· Collection values( )：返回Map中所有值的视图集。
因为Map中值不是唯一的，所以返回的是Collection类型。从所返回的Collection中删除元素会导致值和它的关键字从Map中被删除，因此，同样不能从所返回的Collection中删除元素。
· Set entrySet( )：返回Map.Entry对象的视图集，即Map中的关键字-值对。
因为Map中键-值对是唯一的，因此返回的是一个Set类型。从所返回的Set中删除元素会导致关键字和它相关的值从Map中被删除，因此从所返回的Set中不能删除元素。
【例6-14】本例说明了Map各个方法的使用。
import java.util.*;
public class testMaps{
public static void printKeys(Map m){
System.out.print("Size = " + m.size());
System.out.println(" , Keys: " + m.keySet());
}
public static void printValues(Map m){
System.out.println("Values: " + m.values());
}
public static void test(Map m){
for( int i=1; i<10; i++)
m.put("key" + i, "VALUE" + i);
printKeys(m);
printValues(m);
System.out.println("key1 -> " + m.get("key1"));
Set keys = m.keySet();
Collection values = m.values();
keys.remove("key2");
values.remove("VALUE1");
System.out.println("key1 -> " + m.get("key1"));
printKeys(m);
printValues(m);
}
public static void main(String[] args){
System.out.println("Testing HashMap");
test(new HashMap());
}
}
这个程序的执行结果如下：
Testing HashMap
Size = 9 , Keys: [key1, key3, key7, key6, key8, key5, key2, key9, key4]
Values: [VALUE1, VALUE3, VALUE7, VALUE6, VALUE8, VALUE5, VALUE2, VALUE9, VALUE4]
key1 -> VALUE1
key1 -> null
Size = 7 , Keys: [key3, key7, key6, key8, key5, key9, key4]
Values: [VALUE3, VALUE7, VALUE6, VALUE8, VALUE5, VALUE9, VALUE4]
从程序的执行结果可知，对通过keySet( )和values( )函数取得的值进行修改会反映到Map本身。首先删除了键key2，之后删除的是值为VALUE1的值，结果表明，Map中删除了两个对应的键-值对。
Map接口的entrySet( )方法返回一个实现Map.Entry接口的对象集合。集合中每个对象都是底层Map中一个特定的键-值对。
通过这个集合的迭代器，可以获得每一个健-值对的键或值，并对值进行更改。当条目通过迭代器返回后，除非是迭代器自身的remove( )方法或者迭代器返回的条目的setValue( )方法，其余对源Map外部的修改都会导致此条目集变得无效，同时产生条目行为未定义。
· Object getKey( )：返回健-值对的关键字。
· Object getValue( )：返回健-值对的值。
· Object setValue(Object value)：将相关健-值对中的值改为value，并且返回旧值。
Java集合框架提供了一个特殊的Map接口：SortedMap。这个接口可以保持键的有序顺序。
与SortedSet接口类似，SortedMap接口为Map接口的子集，包括两个端点的访问提供了方法。除了排序是作用于Map的键以外，处理SortedMap和处理SortedSet一样。
添加到SortedMap实现类的元素必须实现Comparable接口，否则必须给它的构造函数提供一个Comparator接口的实现。TreeMap类是它的唯一实现。
因为对于Map来说，每个键只能对应一个值，如果在添加一个键-值对时比较两个键相等（通过Comparable的compareTo( )方法或通过Comparator的compare( )方法），那么，原始键所对应的值被新的值替代。
下面是SortedMap接口的方法。
· Comparator compare( )：返回对关键字进行排序时使用的比较器，如果使用Compa-
rable接口的compareTo( )方法对关键字进行比较，则返回null。
· Object firstKey( )：返回映像中第一个（最低）关键字。
· Object lastKey( )：返回映像中最后一个（最高）关键字。
· SortedMap subMap(Object fromKey, Object toKey)：返回从fromKey（包括）至toKey（不包括）范围内元素的SortedMap子集。
· SortedMap headMap(Object toKey)：返回SortedMap的一个视图，其内各元素的key皆小于toKey。
· SortedSet tailMap(Object fromKey)：返回SortedMap的一个视图，其内各元素的key皆大于或等于fromKey。
和其他AbstractSet类相似，AbstractMap 类覆盖了equals( )和hashCode( )方法以确保两个相等的Map返回相同的哈希码。如果两个Map大小相等，包含同样的键且每个键在这两个Map中对应的值都相同，则这两个Map相等。Map的哈希码是Map中所有元素哈希码的总和，其中每个元素都是Map.Entry接口的一个实现。因此，不论Map内部顺序如何，两个相等的Map会返回相同的哈希码。
Java集合框架提供两种常规的Map实现：HashMap和TreeMap（TreeMap实现Sorted-
Map接口）。在Map中插入、删除和定位元素，HashMap是最好的选择。但如果需要按自然顺序或自定义顺序遍历键，那么就应该用TreeMap。
HashMap和TreeMap都不是同步的。因此当多线程对同一个HashMap或者TreeMap进行读写时，开发人员必须自己做同步处理。
为了优化HashMap空间的使用，可以通过其提供的构造函数调优初始容量和负载因子。HashMap类有以下构造函数。
· HashMap( )：构建一个空的HashMap。
· HashMap(Map m)：构建一个HashMap，并且添加m中所有的元素。
· HashMap(int initialCapacity)：构建一个拥有特定容量的空的HashMap。
· HashMap(int initialCapacity, float loadFactor)：构建一个拥有特定容量和负载因子的空的HashMap。
TreeMap没有调优选项，因为该树总处于平衡状态。TreeMap的构造函数如下。
· TreeMap( )：构建一个空的TreeMap。
· TreeMap(Map m)：构建一个TreeMap，并且添加m中所有元素。
· TreeMap(Comparator c)：构建一个TreeMap，并且使用特定的比较器对关键字进行排序。
· TreeMap(SortedMap s)：构建一个TreeMap，添加s中所有元素，并且使用与s相同的比较器排序。
【例6-15】本例比较了HashMap、TreeMap和LinkedHashMap。
import java.util.*;
public class MapSample {
public static void main(String[] args) {
try {
// HashMap
Map hashMap = new HashMap();
putData(hashMap);
System.out.println("HashMap : " + hashMap);
// TreeMap
Map treeMap = new TreeMap();
putData(treeMap);
System.out.println("TreeMap : " + treeMap);
// LinkedHashMap
Map linkedHashMap = new LinkedHashMap();
putData(linkedHashMap);
System.out.println("LinkedHashMap : " + linkedHashMap);
} catch (Exception e) {
e.printStackTrace();
}
}
static void putData(Map map) {
map.put("5" , "Five");
map.put("4" , "Four");
map.put("3" , "Three");
map.put("2" , "Two");
map.put("1" , "One");
}
}
下面是这个程序的输出结果。
HashMap : {3=Three, 5=Five, 2=Two, 4=Four, 1=One}
TreeMap : {1=One, 2=Two, 3=Three, 4=Four, 5=Five}
LinkedHashMap : {5=Five, 4=Four, 3=Three, 2=Two, 1=One}
LinkedHashMap类扩展了HashMap类，以插入顺序将键-值对添加到LinkedHashMap中。与LinkedHashSet类似，LinkedHashMap内部也采用双重链接式列表。
· LinkedHashMap( )：构建一个空LinkedHashMap。
· LinkedHashMap(Map m)：构建一个LinkedHashMap，并且添加m中所有元素。
· LinkedHashMap(int initialCapacity)：构建一个拥有特定容量的空的LinkedHashMap。
· LinkedHashMap(int initialCapacity, float loadFactor)：构建一个拥有特定容量和负载因子的空的LinkedHashMap。
· LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)：构建一个拥有特定容量、负载因子和访问顺序排序的空LinkedHashMap。
如果将accessOrder设置为true，那么LinkedHashMap将使用访问顺序而不是插入顺序来迭代各个映像。每次调用get( )或者put( )方法时，相关的键-值便从它的当前位置上删除，然后放到LinkedHashMap的结尾处（只有LinkedHashMap列表中的位置才会受到影响，哈希表元则不受影响。哈希表映射总是待在对应于关键字的哈希码的哈希表元中）。
该特性对于实现高速缓存的删除最近最少使用的原则很有用。例如，可以将最常访问的映射保存在内存中，并且从数据库中读取不经常访问的对象。当在表中找不到某个映射，并且该表中的映射已经放得非常满时，可以让迭代器进入该表，将它枚举的开头几个映射删除掉，这些都是最近最少使用的映射。
【例6-16】下面是使用LinkedHashMap的一个例子。
import java.util.*;
import java.text.*;
public class LinkedHashMapSample {
public static void main(String[] args) {
String[]
englishMonths =
new DateFormatSymbols(Locale.ENGLISH).getMonths(),
chineseMonths =
new DateFormatSymbols(Locale.CHINESE).getMonths();
Map orderedMap = new LinkedHashMap();
Map unorderedMap = new HashMap();
for (int i = 0, n = englishMonths.length; i < n; i++) {
orderedMap.put(englishMonths[i], chineseMonths[i]);
unorderedMap.put(englishMonths[i], chineseMonths[i]);
}
System.out.println("Ordered: " + orderedMap);
System.out.println("Unordered: " + unorderedMap);
}
}}
这个程序的输出如下：
Ordered: {January=一月, February=二月, March=三月, April=四月, May=五月, June=
六月, July=七月, August=八月, September=九月, October=十月, November=十一月,
December=十二月, =}
Unordered: {March=三月, December=十二月, April=四月, November=十一月,
September=九月, October=十月, May=五月, June=六月, August=八月, January=一月,
February=二月, July=七月, =}
protected boolean removeEldestEntry(Map.Entry eldest)：如果想删除最早的映射，则覆盖该方法以便返回true；当某个映射已经添加给Map之后，便调用该方法。它的默认实现方法返回false，表示默认条件下早的映射没有被删除；但可以重新定义本方法，以便有选择地在最早的映射符合某个条件或者映像超过了某个大小时，返回true。例如：
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest){
return size() > MAX_ENTRIES;
}
WeakHashMap类是Map接口的一个特殊实现，它使用WeakReference（弱引用）来存放哈希表关键字。使用这种方式时，当映射的键在WeakHashMap 的外部不再被引用时，垃圾收集器会将它回收；但它将把到达该对象的弱引用纳入一个队列，WeakHashMap的运行将定期检查该队列，以便找出新到达的弱引用。当一个弱引用到达该队列时，就表示关键字不再被任何人使用，并且它已经被收集起来，然后WeakHashMap便删除相关的映射。
· WeakHashMap( )：构建一个空WeakHashMap。
· WeakHashMap(Map t)：构建一个WeakHashMap，并且添加映像t中所有映射。
· WeakHashMap(int initialCapacity)：构建一个拥有特定容量的空的WeakHashMap。
· WeakHashMap(int initialCapacity, float loadFactor)：构建一个拥有特定容量和负载因子的空的WeakHashMap。
IdentityHashMap类也是Map接口的一个特殊实现。在这个类中，关键字的哈希码不应该由hashCode( )方法来计算，而应该由System.identityHashCode( )方法进行计算（即使已经重新定义了hashCode( )方法）。这是Object.hashCode( )根据对象的内存地址来计算哈希码时使用的方法。另外，为了对各个对象进行比较，IdentityHashMap将使用“==”，而不使用equals( )方法。
换句话说，不同的关键字对象，即使它们的内容相同，也被视为不同的对象。Identity HashMap类可以用于实现对象拓扑结构转换（Topology-Preserving Object Graph Transform-
ations），例如实现对象的串行化或深度拷贝。在进行转换时，需要一个节点表跟踪那些已经处理过的对象的引用。即使碰巧有对象相等，节点表也不应视其相等。另一个应用是维护代理对象，例如，调试工具希望在程序调试期间维护每个对象的一个代理对象。
IdentityHashMap类不是一般意义上的Map实现，它的实现有意地违背了Map接口要求通过equals( )方法比较对象的约定。这个类仅使用在很少发生的需要强调等同性语义的情况。
· IdentityHashMap( )：构建一个空的IdentityHashMap，默认预期最大尺寸为21。预期最大尺寸是映像期望控制的键-值映射的最大数目。
· IdentityHashMap (Map m)：构建一个IdentityHashMap，并且添加映像m中所有映射。
· IdentityHashMap (int expectedMaxSize)：构建一个拥有预期最大尺寸的空的Identi-
tyHashMap。当放置超过预期最大尺寸的键-值映射时，将引起内部数据结构的增长，有时可能很费时。