声明：本系列博文为"爱校码.中国"原创博文，版权所有，未经授权，不得转载或抄袭，若发现将依法追责。

9.1任务1 基于 Collection 接口及其实现类设计聊天系统的相关对象容器

9.1.1 任务目标

• 理解对象容器的概念
• 了解java.util 包
• 理解Collection集合框架接口
• 掌握 ArrayList类的使用
• 掌握 LinkedList类的使用
• 掌握遍历对象容器的迭代器的使用

9.1.2 任务陈述

面向多用户的聊天系统，需要管理类似User数据对象的用户信息，将把数据对象添加到某个Collection 接口类型的容器对象。然后针对容器对象进行遍历，操作其中的数据对象。容器对象的数据结构设计可根据实际功能的需要采用链表或可变数组。

9.1.3相关知识点

1. 对象容器的基本概念

在情景2介绍数组的时候，一旦数组定义后，它就成为单下标和双下标的固定大小的数据结构，并且其中只能容纳相同数据类型的数据，这种数据可以是原始数据类型，也可以是引用数据类型。本情景任务将介绍的动态数据结构的大小在程序运行时根据需要增长和收缩。例如链表是一种线性行的数据项的集合，可以在链表的任意处插入和删除数据项；堆栈在编译器和操作系统中很重要，插入和删除只在堆栈的顶端进行；队列代表了一种等待行，插入在其尾部进行，而删除在其前端操作；二叉数结构促进了高速的搜索和数据排序，可以高效的消除重复数据项，表示文件系统的目录，将程序表达语言编译成机器语言，以及其他有趣的应用。

本情景将讨论每一种数据结构的主要类型和产生、操作它们的实现程序，使用类、继承和组合来产生和包装这些数据结构，以便提高其重用性和可维护性。这样的数据结构称为对象容器，它们只能容纳对象，严格的说是对象引用，即引用数据类型。要是存放原始数据类型的数据，只能使用原始数据类型的包装类的对象。

Java的对象容器都定义在java.util包中，该包及其子包为Java程序提供了一系列的工具，除了对象容器之外，还包括操作日期时间的工具及压缩解压缩数据的工具等。

Java API按对象容器存放的对象将容器分为两种 ：一种称为集合（collection）容器，它是Java的集合（collection）框架，通过接口Collection描述该容器的基本操作，而其实现类使得程序员可以访问预包装的数据结构，同时提供了操作这些数据结构的算法。使用集合代替产生的数据结构，程序员简单的使用已有的数据结构，而不用关心数据结构是如何实现的，程序员能够快速编程，获得期望的性能，达到最大的执行速度和最少的内存消耗。集合容器存放的基本单位是单个对象；另一种称为映射（map）容器，用接口Map描述这种容器的基本操作，其中存放的基本单位是键值对，包含键（key）对象和值（value）对象。

2. 集合接口(Collection:List,Set,Queue)

Java集合框架为程序员提供一个良好的应用程序接口，将多个元素组成一个单元的对象 ，它们定义了可以完成各种类型集合的操作，集合框架提供了一个表示和操作对象集合的统一架构，允许独立地操作各种数据结构而不需要了解具体的实现，用于存储、检索和操纵数据。集合框架提供了包括列表(List)，队列(Queue)，堆栈(Stack)以及二叉树、哈希表等数据结构。

Java集合框架中包含了大量集合接口，以及这些接口的实现类和操作它们的算法。这些接口包括Collection、Set、List和Queue，继承结构如图所示。

Collection是整个集合框架的基础，它是所有除Map以外其它接口的基接口，提供了访问一组对象的基本方法.

Collection接口方法:

             方法                           说明

boolean add(E e)                  把元素e加入Collection对象中，如果改变Collection对象则返回true，
                                  否则返回false。
boolean addAll(Collection c)      把c中所有元素加入当前Collection中。
boolean equals(Object o)          比较此 collection 与指定对象是否相等。
void clear()                      移除此 collection 中的所有元素。
boolean contains(Object o)        当前Collection是否包含对象o，如是则返回true，否则为false。
boolean containsAll(Collection c) 当前Collection是否包含c中的所有元素，如是则返回true，否则为false。
int hashCode()                    返回当前Collection的哈希码。
boolean isEmpty()                 返回当前Collection对象是否为空，如是空则为true,否则为false。
Iterator 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接口是Collection的一个子接口，它提供了线性表的操作接口。List又称为有序的Collection，此接口允许用户对列表中的每个元素的插入和删除位置进行精确的控制。List通常允许存在重复的元素，同时提供了随机访问的方法，其实现类为LinkedList。基于不同的物理结构，List有不同的实现类（ArrayList），将在后面讨论，List接口的实现如图所示。

Set接口同样是Collection接口的一个子接口，Set中的元素是无序的，且不包含重复的元素，即Set中不存两个这样的元素e1和e2，使得e1.equals(e2)为true。Set接口支持对象的添加、删除，而不需要提供随机访问。具有与Collection接口相同的方法。Set接口的实现如图所示。

Queue接口和Deque接口提供了队列和双端队列的操作，其实现如图所示。

3. 集合接口实现类

针对Java集合框架不同接口，依据不同的物理结构，可以分别作出不同的实现，例如可以采用链表形式进行实现，也可以采用哈希散列的途径实现以及采用二叉树等方式进行实现。

 集合框架接口实现                                    实现类
                   散列表       长度可变数组     二叉树      链表       散列表与链表
     List                       ArrayList                LinkedList
     Set           HashSet                     TreeSet               LinkedHashSet
     Deque                      ArrayDeque               LinkedList

实现类与它们实现的接口具有一样的方法，因此它们在implements过程中没有提供额外的方法。在此，来分析各种实现的性能和效率。

⑴ 长度可变数组实现方式

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

⑵ 链表的实现方式

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

⑶平衡二叉树的实现方式

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

⑷散列表实现方式

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

⑸散列表与链表实现方式

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

⑹线程安全问题

上述的集合框架的接口实现都是非线程安全的。关于线程的讨论将会在后续情景中进行，如果多个线程同时访问同一个集合时，则它必须保持外部同步。一般通过对自然封装该集合的对象进行同步操作来完成，如果不存在这样的对象，则应该使用Collections类中的同步方法synchronizedCollection、synchronizedList、synchronizedSet等来“包装”该集合。有关Collections类的讨论，将在扩展知识点中进行，此类完全由在集合上进行操作或返回集合的静态方法组成。最好在创建集合时完成这一操作，以防止意外的非同步访问:

List list = Collections.synchronizedList(new LinkedList(…));
Set set = Collections.synchronizedSet(new LinkedHashSet(...));

更详细的说明请参阅Java API文档。

４. 链表类(LinkedList)与可变数组类(ArrayList)

⑴链表类(LinkedList)

链表是由若干个称为结点的对象组成的自我引用的线性集合数据结构，结点之间通过引用链连接。若每个结点含有一个数据和下一个结点的引用，则称之为单链表，如图单链表所示；若在单链表中，最后一个结点包含的引用是第一个结点，则称之为循环链表，如图循环链表所示；若每个结点含有一个数据和下一个结点的引用以及前一个结点的引用，则称之为双链表，如图双链表所示。

单链表：

循环链表：

双链表：

对链表的操作有插入、遍历、删除、修改、排序等，如图在单链表头上插入结点所示 显示了在单链表头上插入结点，如图在链表的中间或末尾插入结点所示显示了在链表的中间或末尾插入结点。

在单链表头上插入结点：

在链表的中间或末尾插入结点：

在Java中，java.util.LinkedList 类用于创建链表数据结构，它继承 AbstractSequentialList类并实现 List 接口，如图LinkedList类的继承关系和实现的接口所示，实现所有可选的链表操作，除此之外，LinkedList 类还为在链表的开头及结尾get、remove 和 insert元素提供了统一的命名方法。使用 LinkedList的好处在于它具有访问、检索和删除数据的方法，添加或移除对象时，表现出更好的性能。

LinkedList类的继承关系和实现的接口:

LinkedList类的构造方法：

   构造方法                         描述
LinkedList()                  创建一个空链表。
LinkedList(Collection  c)     根据给定集合的元素创建链表。

LinkedList类的常用方法：

     方法                               描述
public boolean add(E o)       将指定元素追加到此链表的结尾。类型：E - 在此集合中保持的元
                              素的类型。以下方法的参数E的含义相同。
public void add(int index,    在此链表中指定的位置插入指定的元素。移动当前在该位置处的元
        E element)            素（如果有），所有后续元素都向右移（在其索引中添加 1）。
public boolean addAll(Collection c)  追加指定 collection 中的所有元素到此链表的结尾，
                              顺序是指定collection 的迭代器返回这些元素的顺序。
public void addFirst(E o)     将给定元素插入此链表的开头。
public void addLast(E o)      将给定元素追加到此链表的结尾。（与 add 方法功能相同；包括它
                              只是出于一致性考虑。）
public void clear()           从此链表中移除所有元素。
public Object clone()         返回此 LinkedList 的浅表复制。（这些元素本身没有克隆。）
public boolean contains(Object o)    如果此链表包含指定元素，则返回 true。
public E element()            找到但不移除此链表的头（第一个元素）。
public E get(int index)       返回此链表中指定位置处的元素。
public E getFirst()           返回此链表的第一个元素。
public E getLast()            返回此链表的最后一个元素。
public int indexOf(Object o)  返回此链表中首次出现的指定元素的索引，如果链表中不包含此元素，则返回-1。
public int lastIndexOf(Object o) 返回此链表中最后出现的指定元素的索引，如果链表中不包含此元素，则返回 -1。
public ListIterator<E>        返回此链表中的元素的链表迭代器（按适当顺序），从链表中指定位置开始。
     listIterator(int index)
public boolean offer(E o)     将指定元素添加到此链表的末尾（最后一个元素）。
public E peek()               找到但不移除此链表的头（第一个元素）。
public E poll()               找到并移除此链表的头（第一个元素）。
public E remove()             找到并移除此链表的头（第一个元素）。
public E remove(int index)    移除此链表中指定位置处的元素。将任何后续元素向左移（从索引
                              中减 1）。返回从链表中删除的元素。
public boolean remove(Object o) 移除此链表中首次出现的指定元素。如果链表不包含该元素，
                              则不作更改。
public E removeFirst()        移除并返回此链表的第一个元素。
public E removeLast()         移除并返回此链表的最后一个元素。
public E set(int index,       将此链表中指定位置的元素替换为指定的元素。
       E element)
public int size()             返回此链表的元素数。
public Object[] toArray()     以正确顺序返回包含此链表中所有元素的数组。
public T[] toArray(T[] a)     以正确顺序返回包含此链表中所有元素的数组；返回数组的运行时
                              类型即为指定数组的类型。如果链表适合指定数组，则在其中返回
                              该链表。否则，分配具有指定数组的运行时类型和此链表的大小的
                              新数组。T表示类型，即包含集合的数组的运行时类型。

可以使用add、addFirst和addLast方法建立链表，使用get、getFirst和getLast方法得到某位置处的元素，使用set方法设置元素的值，使用remove、removeFirst和removeLast删除元素。

清单 9-1 链表的建立、添加元素和删除元素

1: import java.util.*;
2: public class LinkedListDemo {
3:   public static void main(String[] args) {
4:      List list=new LinkedList();
5:      list.add("Happy");
6:      list.add("new");
7:      list.add("year");
8:      int number=list.size();
9:      for (int i=0;i<number;i++){
10:         String str=(String)list.get(i);
11:         System.out.println("第"+i+"个结点的数据是："+str);           
12:     }
13:     list.remove("new");
14:     System.out.println(list);
15:     list.set(0,"Hello");
16:     list.set(1,"World");
17:     System.out.println(list);
18:  }
19:}

运行结果：

第0个结点的数据是：Happy
第1个结点的数据是：new
第2个结点的数据是：year
[Happy, year]
[Hello, World]

9-2 使用ListIterator接口

1: import java.util.*;
2: public class ListIteratorDemo {
3:  public static void main(String[] args) {
4:      LinkedList linkedlist=new LinkedList();
5:      linkedlist.add("A");
6:      linkedlist.add("B");
7:      linkedlist.add("C");
8:      linkedlist.add("D");
9:      linkedlist.add("E");
10:     linkedlist.add("F");
11:     ListIterator listiterator=linkedlist.listIterator();
12:     while(listiterator.hasNext()){
13:        listiterator.set("元素"+listiterator.next());
14:     }
15:     while(listiterator.hasPrevious()){
16:        System.out.println(listiterator.previous());
17:     }
18:  }
19:}

运行结果：

元素F
元素E
元素D
元素C
元素B
元素A

由于链表中的每个元素通常必须知道下一个和前一个元素（双链表），使用列表遍历器的中next和previous方法，可以在链表中向前移动和向回移动来遍历链表中的每个元素。

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

⑵可变数组类(ArrayList)

java.util. ArrayList是对List接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null在内的所有元素。除了实现List接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。如图ArrayList类的继承关系和实现的接口所示，表示ArrayList类的继承关系和实现的接口。

清单 9-3 使用ArrayList

1: import java.util.ArrayList;
2: import java.util.List;
3: import java.util.Collections;
4: class BookList {
5:    /* 声明一个 ArrayList. */
6:    ArrayList bookArray;
7:    /* 声明一个 List. */
8:    List bookObjList;
9:    BookList() {
10:       bookArray = new ArrayList();
11:   }
12:    /* 向 ArrayList 添加元素. */     
13:    void add() {
14:       bookArray.add("Java程序设计");
15:       bookArray.add("计算机导论");
16:       bookArray.add("操作系统原理及应用");
17:       bookArray.add("数据结构");
18:       bookArray.add("Web开发技术");
19:       bookArray.add("UML设计及应用");
20:       System.out.println();
21:    }     
22:    /**从 ArrayList 显示.*/     
23:    void display() {
24:       System.out.println("**********************"
25:           + "****************");
26:       System.out.println("从 ArrayList 检索对象");
27:       System.out.println("*******************"
28:           + "*******************");
29:       System.out.println();
30:       for (int ctr = 0; ctr < bookArray.size(); ctr++) {
31:            System.out.print("\n" + bookArray.get(ctr));
32:       }
33:       System.out.println();
34:    }
35:    /** 反转 ArrayList.*/
36:    void reverse() {
37:       System.out.println();
38:       System.out.println("*********************************");
39:        System.out.println("反转 List 的内容");
40:        System.out.println("*********************************");
41:        System.out.println();
42:        System.out.println();
43:        System.out.println("书名列表   （反转前）： " + bookArray);
44:        System.out.println();
45:        Collections.reverse(bookArray);
46:        System.out.println("书名列表   （反转后）： " + bookArray);
47:    }
48:    /** 对 ArrayList 进行排序. */
49:    void sort() {
50:       System.out.println("********************");
51:       System.out.println("对 List 进行排序");
52:       System.out.println("********************");
53:       System.out.println();
54:       System.out.println("书名列表   （排序前）： " + bookArray);
55:       System.out.println();
56:       Collections.sort(bookArray);
57:       System.out.println("书名列表   （排序后）： " + bookArray);
58:    }
59:   /** 复制到另一个 List. */
60:   void copy() {
61:      System.out.println("***************************************");
62:      System.out.println("将内容复制到另一个 Array");
63:      System.out.println("***************************************");
64:      System.out.println();
65:      System.out.println("bookArray 是否为空？   " + bookArray.isEmpty());
66:      System.out.println("bookArray（之前）： " + bookArray);
67:      System.out.println();
68:      bookObjList = new ArrayList(bookArray);
69:      System.out.println("bookObjList（之后）： " + bookObjList);
70:   }
71: }
72: public class BookListTest {
73:    public static void main(String[] args) {
74:      BookList bookObj = new BookList();
75:      bookObj.add();
76:      bookObj.display();
77:      bookObj.reverse();
78:      bookObj.sort();
79:      bookObj.copy();
80:   }
81: }

9.1.4 子任务

１.子任务１—聊天系统中的LinkedList类的对象容器设计

在设计聊天系统服务器端类时，可以考虑LinkedList容器类用于会话管理。在该子任务中，服务器类ChatServer的设计类图如图ChatServer类图所示：

ChatServer类图

清单 9-4 ChatServer类：ChatServer.java

清单 9-5 ChatClient类：ChatClient.java

2.子任务2—聊天系统中的ArrayList类的对象容器设计

设计一个类ClientHandler，用于在一个ArrayList集合中放置连接客户端，类图如图服务器端客户管理类图所示：

服务器端客户管理类图

清单9-6 MyServer.java

9.1.5 扩展知识点

１. 堆栈

堆栈是一种受约束的链表形式，新的结点在链表的头部被加入到堆栈，而只能从链表的头部，即堆栈的顶部删除。基于这个原因，堆栈是作为一种后进先出（last-in,first-out:LIFO）的数据结构，如图堆栈的后进先出（FIFO）所示。堆栈底部结点的链接成员被设置为null，以表明这是堆栈的底部。

堆栈的后进先出（FIFO）:

向堆栈中增加数据的操作称为压栈（PUSH），从堆栈中删除数据的操作称为出栈（POP）。在Java中，java.util.Stack类用于实现和操作在程序执行期间的堆栈的增长与缩减。Stack 类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到栈顶距离的 search 方法。Stack类的继承结构如图Stack类的继承结构所示:

Stack类的继承结构:

清单9-7 入栈出栈操作 StackDemo.java

2. 向量

从图Stack类的继承结构可看出，Vector类是Stack类的父类，实现可增长的对象数组，可以存放一定数量的元素，容量可以递增，与数组一样，它包含可以使用整数索引进行访问元素。而Vector 的大小可以根据需要增大或缩小，以适应创建 Vector 后进行添加或移除项的操作。每个Vector对象会试图通过维护容量(capacity)和容量增量(capacityIncrement )来优化存储管理。容量始终至少应与向量对象的大小相等；这个值通常比后者大些，因为随着将元素添加到向量对象中，其存储将按容量增量的大小增加存储块。应用程序可以在插入大量元素前增加向量对象的容量；这样就减少了增加的重分配的量。

需要注意的是：原始数据类型不能直接添加到 Vector 中，这是由于Vector中的元素只能是对象，这时可将原始数据类型的包装类实例化为对象添加到Vector中。

清单9-8 使用Vector类, 安排课表 VectorDemo.java

3. 队列

队列是一种顺序表，其中的项在队列的尾部插入、从头部取出，它是一种先进先出（first-in,first-out: FIFO）的数据结构。如图先进先出(FIFO)所示：

先进先出(FIFO)

队列分为双队列和优先队列。双队列代表双端队列，元素可从队列的两端插入和删除，如图 双队列所示；优先队列表示加入到队列的项有一个与其相关的优先级，它确定处理和删除每个元素的次序，用于分时系统、操作系统的调度程序和打印池应用中。在优先队列中，高优先级的元素先处理，如果二个元素有同样的优先级，那么先来的元素先处理。

双队列:

队列可用数组或链表实现，在Java中，提供了Queue接口，为用户定义了队列的基本操作，它是后面将要讲到的Collection接口的子接口，除于具有基本的Collection操作外，Queue提供了队列的进队、出队和检查操作。Deque接口是Queue的子接口，支持在两端插入和移除元素，定义了数双端队列的操作方法。

清单9-9 队列操作 QueueDemoTest.java

4. 树集

链表、堆栈和队列是线性数据结构，而树是具有特殊特性的非线性、两维数据结构。数的结点包含两个或者多个链接。本点讨论的是二叉树，其结点全部包含两个链接（没有链接，其中一个或两个都可能为null），根结点是树的第一个结点，它的每个链接指向一个子结点。其左子结点是左子树的第一个结点；而且其右子结点是右子树的第一个结点。将这种特殊结点的子结点称作同胞（siblings）。一个没有子结点的结点称作页结点。如图二叉查找树所示，图中每个结点的数据大于左子结点的数据，并且小于右子结点的数据，将其称为二叉查找树。

二叉查找树：

Java通过TreeSet类使用树结构进行内部数据存储，可以按照任意顺序将元素插入该集合，它是一个有序集合。通过迭代器（Iterator）可以遍历树集中的元素，每个值将自动按排序后的顺序出现。TreeSet的继承结构如图TreeSet的继承结构所示。

TreeSet的继承结构：

清单9-10 树集操作 TreeSetDemo.java

５. 算法

集合框架包含三个组件，分别是接口、实现类和算法。接口是表示集合的抽象数据类型，实现是接口的具体实现类，而算法是对实现接口的对象执行计算的方法。

java.util包里面除了提供丰富的数据结构，还提供了大量的算法，这些算法集中在Collections类中，所提供的算法通过static方法来实现。

以下针对排序和查找算法进行了进一步的描述：

• 排序算法（sort）

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

• 查找算法(binarySearch)

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

除此之外，Collections类提供了很多通用的算法，如copy(复制)、fill(填充)、max(最大值)、min（最小值）和reverse(逆序)等算法，更多的算法请参考Java API文档。

清单9-11 使用比较器和Collections类中的算法 CollectionsTest.java

６. Date类、Calendar类和Random类

Date 类表示日期和时间，提供操纵日期和时间各组成部分的方法。Date 类的最佳应用之一是获取系统当前时间。

Calendar 类是一个抽象类，它为特定瞬间与一组诸如 YEAR、MONTH、DAY_OF_MONTH、HOUR 等日历字段之间的转换提供了一些方法，并为操作日历字段提供了一些方法。瞬间可用毫秒值来表示，它是距历元（即格林威治标准时间 1970 年 1 月 1 日的 00:00:00.000，格里高利历）的偏移量。

Random类的实例用于生成随机数。

9.2 任务2 基于Map接口及其实现类设计聊天系统的相关对象容器

9.2.1 任务目标

• 理解Map键值映射数据结构接口
• 掌握HashMap类的使用

9.2.2 任务陈述

当聊天系统涉及“键/值”容器对象设计时，使用Map接口类型声明该容器对象变量，而容器对象则通过Map接口的实现类HashMap的构造方法来完成。

9.2.3相关知识点

1. 哈希表

哈希表又称散列表，通过Hashtable类实现一个哈希表，该哈希表将键映射到相应的值。任何非null 对象都可以用作键或值。为了成功地在哈希表中存储和检索对象，用作键的对象必须实现 hashCode方法和equals 方法。HashMap类是基于哈希表的Map 接口的实现。此实现提供所有可选的映射操作，并允许使用null 值和 null 键。除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。

HashSet类为Set 接口的实现，由哈希表（实际上是一个 HashMap 实例）支持。此类允许使用 null 元素。此类为基本操作提供了稳定性能，这些基本操作包括add、remove、contains 和 size，假定哈希函数将这些元素正确地分布在桶中。对此集合进行迭代所需的时间与 HashSet 实例的大小（元素的数量）和底层 HashMap 实例（桶的数量）的“容量”的和成比例。

清单9-12 使用HashSet

1: import java.util.*;
2: public class SetDemo {
3:    private String colors[]={"red","white","blue","green",
4:      "gray","orange","tan","white","cyan","peach","gray","orange"};
5:    public SetDemo(){
6:      ArrayList list;
7:      list =new ArrayList(Arrays.asList(colors));
8:      System.out.println("数组列表："+list);
9:      printNonDuplicates(list);       
10:   }
11:   public void printNonDuplicates(Collection collection){
12:     HashSet set =new HashSet(collection);
13:     Iterator iterator=set.iterator();
14:     System.out.println("\n没有重复的是：");
15:     while(iterator.hasNext())
16:           System.out.print(iterator.next()+" ");
17:     System.out.println();
18:   }
19:   public static void main(String[] args) {
20:     new SetDemo();
21:   }
22:}

2. 键值映射接口(Map, SortedMap)

Map接口提供一个从键映射到值的数据结构，其中不能包含重复的键，每个键最多映射到一个值上。Map里面装着很多元素，不同的是元素是一个对而已。

Map虽然不从Collection中扩展而来，但它与Collection的关系还是很紧密地联系在一起。Map主要提供了增加、更改和删除对的操作。同时还返回对、键以及值的集合视图。Map接口的实现如图所示。

3. 键值映射接口实现类（HashMap, TreeMap）

针对Java集合框架的Map接口，依据不同的物理结构，可以有不同的实现，可以采用哈希散列表的形式实现，也可以采用二叉树的方式实现，以及采用散列表和链表结合的实现方式。

       接口                            实现类
                     散列表            二叉树                 散列表与链表
       Map          HashMap           TreeMap               LinkedHashMap

清单9-13 使用HashMap

1: import java.util.*;
2: public class MapDemo {
3:   private static String names[]={"one","two","three",
4:     "four","five","six","seven","two","ten","four"};
5:   public MapDemo(){
6:     HashMap map=new HashMap();
7:     Integer i;
8:     for (int count=0;count<names.length;count++){
9:         i=(Integer)map.get(new Character(names[count].charAt(0)));
10:        if (i==null)
11:          map.put(new Character(names[count].charAt(0)), new Integer(1));
12:        else
13:          map.put(new Character(names[count].charAt(0)),
14:                                       new Integer(i.intValue()+1));
15:    }
16:    System.out.println("\n以每个字符开始的单词数");
17:    printMap(map);
18:  }
19:  public void printMap(Map mapRef){
20:    System.out.println(mapRef.toString());
21:    System.out.println("大小:"+mapRef.size());
22:    System.out.println("是否为空："+mapRef.isEmpty());       
23:  }
24:  public static void main(String args[]){
25:    new MapDemo();      
26:  }   
27:}

9.2.4 子任务

１.子任务１—聊天系统中的HashMap类的键值映射容器设计

本子任务中使用HashMap进行服务器端的容器设计，同时使用RMI方式进行远程连接。类图设计如图使用RMI方式的聊天系统所示。RMI有关知识在后续情景的扩展知识点中介绍。

使用RMI方式的聊天系统:

清单9-14 HMChatServer.java

清单9-15 Chatting.java

清单9-16 ChatImpl.java

清单9-17 RMIClient.java

代码的执行条件：

① javac *.java
②  rmic ChatImpl
③  rmiregistry
④  打开一个新的命令提示符执行：
    java ChatServer 端口号
    应该响应：服务器运行的端口  [端口号] ....
⑤  打开一个新的命令提示符执行
    java RMIClient 127.0.0.1 端口号

2.子任务2—聊天系统中的TreeMap类的键值映射容器设计

在本子任务设计中，使用HashMap以及TreeMap用于聊天信息的管理。类图设计如图聊天信息管理类图所示：

聊天信息管理类图:

清单 9-18: Messages.java

清单 9-19: ChatUtil.java

9.2.5 扩展知识点

１. TreeMap类

TreeMap类是基于SortedMap 接口的红黑树的实现。此类保证了映射按照升序顺序排列关键字，根据使用的构造方法不同，可能会按照键的类的自然顺序进行排序。或者按照创建时所提供的比较器进行排序。

2. LinkedHashMap类

LinkedHashMap类是基于 Map 接口的哈希表和链表结合的实现，具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于，它维护一个双向链表。此链表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序。

3. Map.Entry接口

Map.Entry是Map内部定义的一个接口，专门用来存储单个键/值对的。它与Map接口的关系如图Map与Map.Entry的关系所示。

Map与Map.Entry的关系:

它是Map内使用static关键字声明的内部接口，其格式如下：

static interface Map.Entry<K,V>

此接口可以由外部通过“外部类.内部类”的形式直接调用。样例代码如下：

1：import java.util.*;
2：import java.util.Map.Entry;
3：public class EntryDemo {
4：  public static void main(String[] args) {
5：      Map<Integer, Integer> map = new HashMap<Integer, Integer>();
6：      for (int i = 0; i < 10; i++) {
7：         map.put(i, i);
8：      }
9：      for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
10：         System.out.println("键:" + entry.getKey()+
11：                                  " 值:"+ entry.getValue());           
12：     }
13：     Iterator<Map.Entry<Integer, Integer>> iter;
14:      iter = map.entrySet().iterator();
15:      while(iter.hasNext()){     
16:         Map.Entry<Integer, Integer> entry = iter.next();
17:         System.out.println("键:" + entry.getKey()+
18:                                   " 值:"+ entry.getValue()); 
19:      }
20:   }
21:}

从以上代码可以知道，在Map的操作中，所有的内容都是通过“key/value”的形式保存数据的，那么对于集合对象容器来说，实际上是将“key/value”的数据保存在Map.Entry的实例，然后，再在Map集合对象容器中插入的是一个Map.Entry的实例化对象，如图Map.Entry对象存储所示。在一般的Map增加或取出数据等操作，不用去管Map.Entry接口，但是在将Map中的数据全部输出时就必须使用Map.Entry接口。

Map.Entry对象存储:

9.3任务3 基于Java泛型设计聊天系统的相关对象容器

9.3.1 任务目标

• 理解Java泛型

9.3.2 任务陈述

考虑数据对象作为聊天系统的容器对象的元素对象时，容器对象变量声明以及容器对象的实例化都采用泛型格式，使编译器能够在编译时强制进行大量的类型检查，发现其中的错误，避免了运行时再进行数据类型转换所引发的异常。

9.3.3相关知识点

1. 泛型的构成

泛型是自Java SE 5.0之后引入的一项特征，从而引出了一个类型变量的概念，根据Java语言规范，类型变量是一种没有限制的标识符。有以下几种情况：

• 泛型类声明
• 泛型接口声明
• 泛型方法声明
• 泛型构造方法声明

⑴ 泛型类和接口:

如果一个类或接口上有一个或多个类型变量，那它就是泛型。类型变量由尖括号界定，放在类或接口名的后面：

public interface List<E> extends Collection<E> {
}

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, Serializable{
}

类型变量可以是E，也可以是T，没有限制，其扮演的角色就如同一个参数，它提供给编译器用来类型检查的信息。Java系统类库中的许多类，像整个集合框架中的类和接口都进行了泛型化的修改。

⑵ 泛型方法和泛型构造方法

以相似的方式，在定义方法和构造方法时，声明一个或者多个类型变量，则它们也可以泛型化。

public ArrayList(Collection<? extends E> c) {}
public <T> T[] toArray(T[] a) {}

以上第一个定义是ArrayList类的构造方法之一的声明，类型变量为E；第二个定义是ArrayList类中的一个方法的的声明，类型变量为T。

当您利用泛型进行设计时，既可以使用Java类库里提供的泛型类，也可以使用自己定义声明的泛型类。

清单 9-20: 使用泛型和访问者模式

1: abstract class Tree<E> {
2:     public interface Visitor<E, R> {
3:         public R leaf(E e);
4:         public R branch(R left, R right);
5:      }
6:      public abstract <R> R visit(Visitor<E, R> v);
7:      public static <T> Tree<T> leaf(final T e) {
8:          return new Tree<T>() {
9:              public <R> R visit(Visitor<T, R> v) {
10:                 return v.leaf(e);
11:             }
12:         };
13:     }
14:     public static <T> Tree<T> branch(final Tree<T> l, final Tree<T> r) {
15:         return new Tree<T>() {
16:             public <R> R visit(Visitor<T, R> v) {
17:                 return v.branch(l.visit(v), r.visit(v));
18:             }
19:         };
20:     }
21: }
22: public class TreeClient {
23:     public static <T> String toString(Tree<T> t) {
24:         return t.visit(new Tree.Visitor<T, String>() {
25:             public String leaf(T e) {
26:                 return e.toString();
27:             }
28:             public String branch(String l, String r) {
29:                 return "(" + l + "^" + r + ")";
30:             }
31:         });
32:     }
33:     public static <N extends Number> double sum(Tree<N> t) {
34:         return t.visit(new Tree.Visitor<N, Double>() {
35:             public Double leaf(N e) {
36:                 return e.doubleValue();
37:             }
38:             public Double branch(Double l, Double r) {
39:                 return l + r;
40:             }
41:         });
42:     }
43:     public static void main(String[] args) {
44:         Tree<Integer> t = Tree.branch(
45:                         Tree.branch(Tree.leaf(1),Tree.leaf(2)),
46:                         Tree.leaf(3)
47:                        );
48:         System.out.println(toString(t));
49:         System.out.println(sum(t));     
50:     }
51: }

在以上代码中，代码行1-21为抽象类Tree<E>的定义及实现，其类型变量为E，只有一个抽象方法visit，它接受一个Visitor<E, R>类型的参数，这个类型是通过其中的接口Visitor<E, R>定义的，它的泛型的类型变量为E和R。在该接口中指定了两个方法：一个方法是leaf，它接受一个类型变量为E的类型值，并且返回类型变量为R的类型值；另一个方法是branch，它接受类型变量为R的两个值，并且返回类型变量为R的类型值。

在抽象类当中，还有两个静态工厂方法leaf和branch：一个用于构造树的叶，一个用于构建树的枝。这些方法中包含一个扩展Tree的嵌套匿名子类，在其中实现了抽象类的抽象方法visit，而方法内的实现则不同。对应于leaf中的实现的visit，通过调用其参数类型Visitor<E, R>中的leaf方法来实施；而对应于branch中实现的visit，则通过调用其参数类型Visitor<E, R>中的branch方法来实施，这种调用是基于对参数类型对象的左、右子树递归调用的结果。

在代码行22-51的客户端类TreeClient内，基于Tree<T>实现了toString方法与sum方法，而非用于定义数据结构的类内，它们是将Tree<T>作为参数而采取静态方法。在两种方法中，有一个可喜的重用性。对于简单的树，每个工厂方法（leaf和branch）组为每个操作方法（toString和sum）一起定义。而对于树的访问者，每个操作方法（toString和sum）组为每个访问者的方法（leaf和branch）一起定义。

有了泛型，每个访问者有两个类型参数，一个为树的元素类型和一个为访问者的返回类型。如果没有泛型，每个访问者将不得不返回Object类型的结果，这将需要许多额外的强制类型转换。

正因为如此，Java泛型可以看成是一种便捷语法，能够节省某些Java类型转换上的操作。泛型的主要好处就是让编译器保留参数的类型信息，执行类型检查，执行类型转换操作，编译器保证了这些类型转换的绝对无误。

相对于依赖程序员来记住对象类型，并编写执行类型转换的程序，这有可能会导致程序运行时的失败，并且很难调试和解决；而泛型使编译器能够帮助程序员在编译时强制进行大量的类型检查，发现其中的错误。

9.3.4 子任务：

１.子任务１—聊天系统中的Collection对象容器设计

在该子任务中对本情景任务1的子任务1的ChatServer类应用泛型接口List<E>，将类名改为GChatServer，其类图设计如图使用Collection<E>泛型接口所示：

使用Collection泛型接口:

对接口List使用泛型如下：

List<GChat> chats = new LinkedList<GChat>();

清单 9-21: GChatServer.java

2.子任务2—聊天系统中的Map对象容器设计

将本情景任务2中的子任务1的HMChatServer类应用泛型接口Map<K,V>，将类名改为GHMChatServer，其类图设计如图使用Map<K,V>泛型接口所示：

使用Map泛型接口:

清单 9-21: GHMChatServer.java

清单 9-22: Chatting.java

清单 9-23: GChatImpl.java

清单 9-24: RMIClient.java

代码的执行条件：

① javac *.java
②  rmic GChatImpl
③  rmiregistry
④  打开一个新的命令提示符执行：  
     java GChatServer 端口号   
    应该响应：服务器运行的端口  [端口号] ....
⑤  打开一个新的命令提示符执行：
    java RMIClient 127.0.0.1 端口号

9.3.5 扩展知识点

１. 在泛型中使用? extends 通配符

在泛型的使用中，?extends用于向上造型一个泛型对象的引用。例如，已定义了以下几个类：Fruit、Apple、Strawberry和FujiApple，它们之间的关系如图水果类之间关系所示：

水果类之间关系

图中关系的含义为：FujiApple(富士苹果)是Apple(苹果)的子类型，Apple是Fruit(水果)的子类型，FujiApple是Fruit的子类型；Strawberry(草莓)是Fruit的子类型。样例代码如下：

List<Apple> apples = new ArrayList<Apple>();
List<? extends Fruit> fruits = apples;

“? extends”使泛型类型的子类型相关性成为现实，Apple是Fruit的子类型，List 是 List<? extends Fruit> 的子类型。

2. 在泛型中使用? super 通配符

在泛型的使用中，?super向下造型一个泛型对象的引用。样例代码如下：

List<Fruit> fruits = new ArrayList<Fruit>();
List<? super Apple> = fruits;

３. 在泛型中使用通配符的存取原则

对于在泛型中使用?extends和?super通配符，有以下存取原则：

• 如果想从一个数据类型里获取数据，可以使用?extends通配符；
• 如果要将对象写入一个数据结构里，可以使用?super通配符；
• 如果既想存，又想取，那就不要使用通配符。