java面向对象程序设计第十一章

Java高级

第十一章集合框架

主要内容：

集合类框架的概念集合类接口与类两个特殊的集合类

Java1.0/1.1的集合类集合类框架的概念集合类和集合接口关系图所谓框架就是一个类库的集合。集合框架就是一个用来表示和操作集合的统一的架构，包含了实现集合的接口与类。集合类和集合接口关系图解读实线框图表示集合类；虚线框图表示集合接口；虚线连接的空心箭头表示接口之间的继承或类对接口的实现关系；实线表示类之间的继承关系。实心箭头表示一个接口方法可以返回另一个接口可引用的实例。图中还展示了集合类相关的一些功能类如：Collections和Arrays,它们封装有特定的集合操作功能。集合类接口六大集合类接口之一——Collection接口collection是集合类的基本接口，它用来说明作为一个集合类应有的特征属性并为一组对象的操作提供了一些简单的方法。子接口有：List和Set它的实现类有：AbstractCollection,AbstractList,AbstractSet,ArrayList,BeanContextServicesSupport,BeanContextSupport,HashSet,LinkedHashSet,LinkedList,TreeSet,Vector。Collection接口提供的主要方法boolean

add(Objectc)：用于向集合中添加一个新元素。boolean

addAll(Collection

c)：用于添加一组元素。boolean

remove(Object

o)：用于删除一个元素。booleanremoveAll(Collectionc)：用于删除一组元素。Object[]toArray()：把集合转换成对象数组引用返回。Object[]toArray(Object[]a)：把集合转换成对象数组引用返回。但是类型和参数a的类型是相同的。booleanisEmpty()：用于判断集合是否为空。Iteratoriterator()：用于返回实现Iterator接口的对象。Collection接口的子接口List

是Collection的子接口，它具有可以控制的顺序，但并没有定义或限制按什么排序。实现List接口的类是AbstractList,ArrayList,LinkedList,Vector。Set

不能包含重复的元素。它的实现类有AbstractSet,HashSet,LinkedHashSet,TreeSet。SortedSet是Set的子接口，在Set基础上，要求其元素按照某种自然顺序进行存储。它的实现类有TreeSet。ArrayList我们可以将ArrayList看作是能够自动增长容量的数组。利用ArrayList的toArray()返回一个数组。Arrays.asList()用于返回一个列表。迭代器(Iterator)给我们提供了一种通用的方式来遍历集合中的元素。方法名说明booleanhasNext()判断迭代器是否还存在下一个元素Objectnext()返回下一个元素的引用voidremove()从集合中删除迭代器指向的最后一个元素返回的元素删除的元素next()remove()next()Collections排序：Collections.sort()①自然排寻(naturalordering)；②实现比较器(Comparator)接口。取最大/最小元素：Collections.max()、Collections.min()。在已排序的List中搜索指定的元素：Collectons.binarySearch()。LinkedList线性表：必存在唯一的称为“第一个”和“最后一个”的数据元素；除第一个和最后一个元素外，每个元素都有且只有一个前驱元素，都有且只有一个后继元素。线性表按其存储结构可分为顺序表和链表。LinkedList是采用双向循环链表实现的。利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-endedqueue)。单向链表的结构datanextdatanextdatanext=nullhead节点单向链表的插入与删除datanextdatanextdatanext＝nullhead节点datanextdatanextdatanextdatanext＝null循环链表的结构datanextdatanextdatanexthead节点双向循环链表结构datanextdatanextdatanexthead节点previouspreviousprevious栈（Stack）栈(Stack)也是一种特殊的线性表，是一种后进先出(LIFO)的结构。栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)。栈的物理存储可以用顺序存储结构，也可以用链式存储结构。a1a2an…栈底栈顶出栈进栈队列（Queue）队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)。队列的操作是按先进先出(FIFO)的原则进行的。队列的物理存储可以用顺序存储结构，也可以用链式存储结构。a1a2a3…an队头队尾出队入队ArrayList和LinkedList的比较ArrayList底层采用数组完成，而LinkedList则是以双向链表(double-linkedlist)完成，其内每个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素。如果我们经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。就ArrayList与Vector主要从三方面来说:同步性:Vector是线程安全的，也就是说是同步的，而ArrayList是线程序不安全的，不是同步的。数据增长:当需要增长时，Vector默认增长为原来一倍，而ArrayList却是原来的一半。ArrayList和Vector的比较HashSet实现Set接口，依靠HashMap来实现的。我们通常应该为要存放到散列表的各个对象重新定义hashCode()和equals()。散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散列表中的地址。TreeSetTreeSet是依靠TreeMap来实现的。TreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着TreeSet中元素要实现Comparable接口。我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。HashSet和TreeSet的比较HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。六大集合类接口之二——Map接口Map接口能够将一个键(Key)影射到一个值(Value),不允许有重复的键，每个键之多有一个与之对应的值。Map的实现类有：Hashtable、HashMapSortedMap是Map的子接口，能使Key按照自然顺序进行存储。它的实现类有TreeMap接口为我们提供了完成下面三种主要的功能的方法Map改变：包括关键字/值对的删除、更新和插入。Map查询：允许用户从Map中获取关键字/值对。提供查询Map元素内容的方法，也有用来查询整个Map对象的方法。Map接口的三种视图keySet()方法获取的是Map中的关键字的一个Set(唯一性)。因为map映射中的关键字是唯一，keySet()方法得到的正好是一个set。values()方法返回映射中值的Collection(Collection是允许存储重复元素的对象的集合)。因为Map中的值是可以重复的，values()方法得到的只能是一个collection而不是一个Set。entrySet()方法返回Map.Entry的一个Set。即Map对象中所存储的键值对的集合，也就是一个键值对构成的Set。HashMap和TreeMap的比较和Set类似，HashMap的速度通常都比TreeMap快，只有在需要排序的功能的时候，才使用TreeMap。就HashMap与HashTable主要从三方面来说:历史原因:Hashtable是基于陈旧的Dictionary类的,HashMap是Java1.2引进的Map接口的一个实现同步性:Hashtable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的值:只有HashMap可以让你将空值作为一个表的条目的key或value

HashMap和Hashtable的比较六大集合类接口之三——Enumeration接口Enumeration接口是一个对集合类进行遍历的接口。Enumeration接口提供的方法：booleanhasMoreElements()：检索是否有下一个对象，如果有则返回ture；否则返回false。ObjectnextElement()：在上一个方法为true的条件下，返回下一个Object类型的对象；如果上一个方法返回的结果为false，那么还调用此方法时会产生一个NoSuchElementException。六大集合类接口之四——Iteraor接口Iteraor接口提供了以下的方法：hasNext()：下一个对象存在返回ture；否则返回false。next()：hasNext()为true时调用，返回Object类型的对象。remove()：在提供迭代器实现对象的集合中删除由next()方法指向的一个对象。Iteraor接口的优点：Iterator是用于遍历集合类的标准访问方法。每种集合类返回的Iterator对象类型可能不同，Array可能返回ArrayIterator，Set可能返回SetIterator，但是它们都实现了Iterator接口，因此用户不需直接和集合类打交道。六大接口之五——ListIterator接口ListIterator是Iterator的子接口。它对集合遍历时进行的更改，将直接影响原来的集合。对List来说，也可以通过listIterator()取得其迭代器。Iterator和ListIterator主要区别在以下方面：ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。ListIterator有add()方法，可向List中添加对象。ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现，Iterator没有此功能。都可实现删除对象，但是ListIterator可以实现对象的修改，此功能通过set()方法来实现。集合接口在使用时的注意事项Enumeration接口的nextElement方法和Iteraor接口的next()方法返回的对象用Object进行引用，在实际使用中，应根据对象的具体类型进行显式的转化（注意，要转化成X类，条件是集合中所引用的对象原来就是X类型，或是X类型的子类，否则会产生类型转化异常）。一些集合对象，例如Hashtable、HashMap，它的键和其值的加入顺序，与Iteraor遍历顺序，并不一定一致。六大接口之六——Comparator接口Comparator是一个集合对象排序接口，某个类实现了这个接口，那么这个类的对象就可以进行排序，接口方法如下：

publicinterfaceComparator{

int

compare(Objecto1,Objecto2);

boolean

equals(Object

obj);}一般都只需要实现compare方法就行了,因为类都是默认从Object继承，可使用Object的equals()方法。两个特殊的集合类

StringTokenizer类StringTokenizer是以token为单元的字符串集合，它实现Enumeration接口，对其集合进行遍历采用Enumeration提供的方法，当然也可采用它自己的方法，例如：

StringTokenizer

st=newStringTokenizer("thisisatest"); while(st.hasMoreTokens()){System.out.println(st.nextToken());}默认情况下，StringTokenizer用空格、制表符“\t”、回车符、换行符、分页符为标志进行token区分。其他的构造方法：publicStringTokenizer(String

str,String

delim)publicStringTokenizer(String

str,String

delim,boole