Java面向对象程序设计第09章_泛型与集合框架

第9章泛型与集合框架,主讲：赵建邦办公室：信息学院202E-mail:zhaojianbang,2,本章主要内容,9.1java.util.Collection接口9.2ArrayList类（数组表）9.3LinkedList类（链表）9.4Stack类（堆栈）9.5HashMap类（散列映射）9.6TreeSet类（树集）9.7TreeMap类（树映射）难点：树映射,9.1java.util.Collection接口,Collection(容器)接口是Collection层次结构中的根接口Collection表示一组对象，这些对象也称为collection的元素（Elements）JDK不提供此接口的任何直接实现由Collection接口派生的两个接口是List和Set，JDK提供的容器类都是这些子接口的类实现不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，可逐一访问Collection中每一个元素,9.1java.util.Collection接口,9.2ArrayList类,java.util.ArrayList类实现了List接口，用于表述长度可变的数组列表访问速度很快，插入与移除元素很慢，动态增长会不断复制原有List通过两个例子来理解以下几个内容：同质容器、异质容器TestArrayList_02.java同质容器：用泛型符号来限定的容器数组表的增长方式toString()的原理ArrayList_01.java,9.3LinkedList类,链表由若干个节点对象组成，分为单链表和双向链表插入与移除开销不大，访问较慢LinkedList类实现了链表泛型类常用方法:添加节点、删除节点、置空链表、替换节点、判断元素是否是已有链表元素等遍历链表使用迭代器BoxingTest.java,9.4Stack类,堆栈“后进先出”例：使用堆栈操作实现Fibonacci序列要比递归效率更高Fibonacci.java,A,B,C,D,top,插入E,A,B,C,D,删除D,E,9.5HashMap类,HashMap用于存储具有“键/值”对应关系的数据结构该泛型类创建的对象成为散列映射键不能出现冲突HashMap表会自动实现扩容常用方法：查询指定键、查询指定值、添加、删除其中插入和查询的开销是固定的,Map的出现和ArrayList同理，不同的是，ArrayList用下标进行查找，Map用对象进行查找，它就像“字典”,9.5HashMap类,HashMap构造方法：HashMap()：构建一个初始容量为16，负载因子为0.75的HashMapHashMap(intinitialCapacity)：构建一个初始容量为initialCapacity，负载因子为0.75的HashMapHashMap(intinitialCapacity,floatloadFactor)：以指定初始容量、指定的负载因子创建一个HashMapHashMap采用一种所谓的“Hash算法”来决定每个元素的存储位置，依据Key计算HashMapTest.java,9.6TreeSet类,按照排序二叉树进行存储,TreeSet对象进行数据插入和查询的时候效率比HashSet低，因为TreeSet需要维持数据的有序性而必须进行排序。它适合于录入具有高度有序的数据集,9.7TreeMap类,树结构可以保持元素的有序排列，因此实现了Map接口的TreeMap类不仅可以实现“键/值”映射，还能保持元素按照关键字有序排列元素保存机制：“红黑树”参考书“算法分析与设计”MichaelT.G&RobertoT著，霍红卫译，人民邮电出版社例13.9,总结,容器用来存储对象的集合，根据容器的类型可以实现有序或者无序存储Set接口：元素不能重复，使用add添加元素，自动排序常用实现类：HashSet(快速查找)、TreeSet(有序)List接口：可以重复，不做排序常用实现类：ArrayList、LinkedList、StackMap接口：保存“键/值”，使用put添加元素常用实现类：HashMap、TreeMap(有序),讨论：迭代器,迭代器是一个对象，它的工作是遍历并选择序列中的对象1、使用iterator()方法返回一个迭代器对象，第一次调用next()方法时，返回序列的第一个元素，以后返