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

信息工程学院本科课程第9章泛型与集合框架主讲：赵建邦办公室：信息学院202E-mail:[e-mail]信息工程学院本科课程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同质容器：用泛型符号E来限定的容器数组表的增长方式toString()的原理ArrayList_01.java信息工程学院本科课程9.3LinkedList类链表由若干个节点对象组成，分为单链表和双向链表插入与移除开销不大，访问较慢LinkedListE类实现了链表泛型类常用方法:添加节点、删除节点、置空链表、替换节点、判断元素是否是已有链表元素等遍历链表使用迭代器BoxingTest.java信息工程学院本科课程9.4Stack类堆栈“后进先出”例：使用堆栈操作实现Fibonacci序列要比递归效率更高Fibonacci.javaABCDbase123450top插入Ebase123450ABCDtop删除DE信息工程学院本科课程9.5HashMap类HashMapKeyClass,ValueClass用于存储具有“键/值”对应关系的数据结构该泛型类创建的对象成为散列映射键不能出现冲突HashMap表会自动实现扩容常用方法：查询指定键、查询指定值、添加、删除其中插入和查询的开销是固定的Map的出现和ArrayList同理，不同的是，ArrayList用下标进行查找，Map用对象进行查找，它就像“字典”信息工程学院本科课程9.5HashMap类HashMap构造方法：HashMap()：构建一个初始容量为16，负载因子为0.75的HashMapHashMap(intinitialCapacity)：构建一个初始容量为initialCapacity，负载因子为0.75的HashMapHashMap(intinitialCapacity,floatloadFactor)：以指定初始容量、指定的负载因子创建一个HashMapHashMapKey,Value采用一种所谓的“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、StackMap接口：保存“键/值”，使用put添加元素常用实现类：HashMap、TreeMap(有序)信息工程学院本科课程讨论：迭代器迭代器是一个对象，它的工作是遍历并选择序列中的对象1、使用iterator()方法返回一个迭代器对象，第一次调用next()方法时，返回序列的第一个元素，以后返回下一个元素2、hasNext()检查是否还有元素3、可以使用remove()将最近返回的元素删除4、实现Map的容器需要调用keySet()或values()得到key或值的Set信息工程学院本科课程谢谢！