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

1、Java 高级高级 第十一章 集合框架 主要内容：主要内容：l 集合类框架的概念 l 集合类接口与类 l两个特殊的集合类l Java1.0/1.1的集合类集合类框架的概念集合类和集合接口关系图集合类和集合接口关系图所谓框架就是一个类库的集合。集合框架就是一个用来表示和操作集合的统一的架构，包含了实现集合的接口与类。集合类和集合接口关系图解读集合类和集合接口关系图解读l实线框图表示集合类；虚线框图表示集合接口；l虚线连接的空心箭头表示接口之间的继承或类对接口的实现关系；实线表示类之间的继承关系。l实心箭头表示一个接口方法可以返回另一个接口可引用的实例。l图中还展示了集合类相关的一些功能类如：Co

2、llections和Arrays,它们封装有特定的集合操作功能。集合类接口 六大集合类接口之一六大集合类接口之一Collection接口接口 lcollection是集合类的基本接口，它用来说明作为一个集合类应有的特征属性并为一组对象的操作提供了一些简单的方法。l子接口有：List 和Setl它的实现类有： AbstractCollection,AbstractList,AbstractSet,ArrayList,BeanContextServicesSupport,BeanContextSupport,HashSet,LinkedHashSet,LinkedList,TreeSet,Vect

3、or。Collection接口提供的主要方法接口提供的主要方法boolean add(Object c)：用于向集合中添加一个新元素。boolean addAll(Collection c)：用于添加一组元素。boolean remove(Object o)：用于删除一个元素。boolean removeAll(Collection c)：用于删除一组元素。Object toArray()：把集合转换成对象数组引用返回。Object toArray(Object a)：把集合转换成对象数组引用返回。但是类型和参数a的类型是相同的。boolean isEmpty() ：用于判断集合是否为空。It

4、erator iterator()：用于返回实现Iterator接口的对象。Collection接口的子接口接口的子接口lList 是Collection的子接口，它具有可以控制的顺序，但并没有定义或限制按什么排序。实现List接口的类是AbstractList, ArrayList, LinkedList, Vector。lSet 不能包含重复的元素。它的实现类有AbstractSet, HashSet, LinkedHashSet, TreeSet。lSortedSet是Set的子接口，在Set基础上，要求其元素按照某种自然顺序进行存储。它的实现类有TreeSet。ArrayListl我们

5、可以将ArrayList看作是能够自动增长容量的数组。l利用ArrayList的toArray()返回一个数组。lArrays.asList()用于返回一个列表。l迭代器(Iterator) 给我们提供了一种通用的方式来遍历集合中的元素。方法名方法名说明说明boolean hasNext()判断迭代器是否还存在下一个元素Object next()返回下一个元素的引用void remove()从集合中删除迭代器指向的最后一个元素返回的元素删除的元素next()remove()next()Collectionsl排序：Collections.sort() 自然排寻(natural ordering

6、 )； 实现比较器(Comparator)接口。l取最大/最小元素：Collections.max()、Collections.min()。l在已排序的List中搜索指定的元素：Collectons.binarySearch()。LinkedListl线性表：必存在唯一的称为“第一个”和“最后一个”的数据元素；除第一个和最后一个元素外，每个元素都有且只有一个前驱元素，都有且只有一个后继元素。线性表按其存储结构可分为顺序表和链表。lLinkedList是采用双向循环链表实现的。l利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-ended queue )。

7、单向链表的结构单向链表的结构datanextdatanextdatanext=nullhead节点l单向链表的插入与删除datanextdatanextdatanextnullhead节点datanextdatanextdatanextdatanextnull循环链表的结构循环链表的结构datanextdatanextdatanexthead节点datanextdatanextdatanexthead节点previouspreviousprevious栈（栈（Stack）l栈(Stack)也是一种特殊的线性表，是一种后进先出(LIFO)的结构。l栈是限定仅在表尾进行插入和删除运算的线性表，表尾

8、称为栈顶(top)，表头称为栈底(bottom)。l栈的物理存储可以用顺序存储结构，也可以用链式存储结构。栈底栈顶出栈进栈队列（队列（ Queue ）l队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。l表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)。l队列的操作是按先进先出(FIFO)的原则进行的。l队列的物理存储可以用顺序存储结构，也可以用链式存储结构。队头队尾出队 入队ArrayList和和LinkedList的比较的比较lArrayList底层采用数组完成，而LinkedList则是以双向链表(double-li

9、nked list)完成，其内每个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素。l如果我们经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。就ArrayList与Vector主要从三方面来说:l同步性:Vector是线程安全的，也就是说是同步的，而ArrayList是线程序不安全的，不是同步的。l数据增长:当需要增长时，Vector默认增长为原来一倍，而ArrayList却是原来的一半。ArrayList和和Vector的比较的比较HashSetl实现Set接口，依靠HashMa

10、p来实现的。l我们通常应该为要存放到散列表的各个对象重新定义hashCode()和equals()。l散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散列表中的地址。TreeSetlTreeSet是依靠TreeMap来实现的。lTreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着TreeSet中元素要实现Comparable接口。l我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。HashSet和和TreeSet的比较的

11、比较lHashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。六大集合类接口之二六大集合类接口之二Map接口接口lMap接口能够将一个键(Key)影射到一个值(Value),不允许有重复的键，每个键之多有一个与之对应的值。lMap 的实现类有： Hashtable、HashMaplSortedMap是Map的子接口，能使Key按照自然顺序进行存储。它的实现类有TreeMapl接口为我们提供了完成下面三种主要的功能的方法Map 改变：包括关键字/值对的删除、更新和插入。Map 查询：允许用户从Ma

12、p中获取关键字/值对。提供查询Map元素内容的方法，也有用来查询整个Map对象的方法。Map接口的三种视图接口的三种视图lkeySet()方法获取的是Map中的关键字的一个Set(唯一性)。因为map映射中的关键字是唯一，keySet()方法得到的正好是一个set。lvalues()方法返回映射中值的Collection(Collection是允许存储重复元素的对象的集合)。因为Map中的值是可以重复的，values()方法得到的只能是一个collection而不是一个Set。lentrySet()方法返回Map.Entry的一个Set。即Map对象中所存储的键值对的集合，也就是一个键值对构成

13、的Set。HashMap和和TreeMap的比较的比较l和Set类似，HashMap的速度通常都比TreeMap快，只有在需要排序的功能的时候，才使用TreeMap。就HashMap与HashTable主要从三方面来说:l历史原因:Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现l同步性:Hashtable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的l值:只有HashMap可以让你将空值作为一个表的条目的key或value HashMap和和Hashtable的比较的比较六大集合类接口之三六大集合

14、类接口之三Enumeration接口接口lEnumeration接口是一个对集合类进行遍历的接口。lEnumeration接口提供的方法：boolean hasMoreElements() ：检索是否有下一个对象，如果有则返回ture；否则返回false。Object nextElement() ：在上一个方法为true的条件下，返回下一个Object类型的对象；如果上一个方法返回的结果为false，那么还调用此方法时会产生一个NoSuchElementException。六大集合类接口之四六大集合类接口之四Iteraor接口接口lIteraor接口提供了以下的方法：hasNext()：下一个

15、对象存在返回ture；否则返回false。next()：hasNext()为true时调用，返回Object类型的对象。remove()：在提供迭代器实现对象的集合中删除由next()方法指向的一个对象。lIteraor接口的优点：Iterator是用于遍历集合类的标准访问方法。每种集合类返回的Iterator对象类型可能不同，Array可能返回ArrayIterator，Set可能返回SetIterator，但是它们都实现了Iterator接口，因此用户不需直接和集合类打交道。六大接口之五六大接口之五ListIterator接口接口lListIterator是Iterator的子接口。它对集

16、合遍历时进行的更改，将直接影响原来的集合。对List来说，也可以通过listIterator()取得其迭代器。lIterator和ListIterator主要区别在以下方面：lListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。lListIterator有add()方法，可向List中添加对象。lListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现，Iterator没有此

17、功能。l都可实现删除对象，但是ListIterator可以实现对象的修改，此功能通过set()方法来实现。集合接口在使用时的注意事项集合接口在使用时的注意事项lEnumeration接口的nextElement方法和Iteraor接口的next()方法返回的对象用Object进行引用，在实际使用中，应根据对象的具体类型进行显式的转化（注意，要转化成X类，条件是集合中所引用的对象原来就是X类型，或是X类型的子类，否则会产生类型转化异常）。l一些集合对象，例如Hashtable、HashMap，它的键和其值的加入顺序，与Iteraor遍历顺序，并不一定一致。六大接口之六六大接口之六Comparat

18、or接口接口lComparator是一个集合对象排序接口，某个类实现了这个接口，那么这个类的对象就可以进行排序，接口方法如下： public interface Comparator int compare(Object o1, Object o2); boolean equals(Object obj); l一般都只需要实现compare方法就行了,因为类都是默认从Object继承，可使用Object的equals()方法。两个特殊的集合类 StringTokenizer类类lStringTokenizer是以token为单元的字符串集合，它实现Enumeration接口，对其集合进行遍历采

19、用Enumeration提供的方法，当然也可采用它自己的方法，例如：StringTokenizer st = new StringTokenizer(this is a test); while (st.hasMoreTokens() System.out.println(st.nextToken();l默认情况下，StringTokenizer用空格、制表符“t”、回车符、换行符、分页符为标志进行token区分。l其他的构造方法：public StringTokenizer(String str,String delim)public StringTokenizer(String str, String delim,boo