深入集合框架.pptx

课程整体目标课程整体目标n掌握理解集合掌握理解集合n理解了解集合的体系结构理解了解集合的体系结构n使用使用ArrayList、编写自己的、编写自己的ArrayListnLinkedList的特性及其使用的特性及其使用nHashMap的特性及基使用的特性及基使用n使用迭代器遍历集合使用迭代器遍历集合本章相关词汇（蓝色为关键字）本章相关词汇（蓝色为关键字）单 词说 明class类print打印String字符串3Collection接口接口接口是表示集合的抽象数据类型算法算法是对实现接口的对象执行计算的方法实现实现是接口的实际实现集合框架包含三个组件Java集合框架包含的内容集合框架包含的内容1接口接口CollectionListMap2具体类具体类ListArrayListLinkedListMapHashMap3算法算法Java集合框架，为我们提供了一套性能优良、使用方便的接口和集合框架，为我们提供了一套性能优良、使用方便的接口和类，我们不必再重新发明轮子，只需学会如何使用它们，就可以处类，我们不必再重新发明轮子，只需学会如何使用它们，就可以处理实际应用中出现的问题了理实际应用中出现的问题了Java集合框架位于集合框架位于java.util包中包中Collections提供了对集合进提供了对集合进行排序、遍历等行排序、遍历等多种算法实现多种算法实现采用键采用键-值对的存储方式，值对的存储方式，长度可动态改变长度可动态改变采用线性列表的存储方式，采用线性列表的存储方式，长度可动态改变长度可动态改变5集合框架的优点提供有用的数据结构和算法，从而减少编程工作提高了程序速度和质量,因为它提供了高性能的数据结构和算法允许不同API之间的互操作，API之间可以来回传递集合可以方便地扩展或改写集合怎样保存你的对象怎样保存你的对象?n数组数组-简单的线性序列简单的线性序列简单和高效简单和高效容量固定容量固定类型识别类型识别 类型相同类型相同能保存基本类型能保存基本类型Arrays类类nJava.util.Arrays类类包含了一组可用语数组的包含了一组可用语数组的staic方法方法,这些方法都是一些实这些方法都是一些实用的工具用的工具.equals()-比较两个数组是否相等比较两个数组是否相等fill()-用来填充数组用来填充数组sort()-用来对数组进行排序用来对数组进行排序binarySearch()-用于在一个已经排序的数组中查找元素用于在一个已经排序的数组中查找元素思考思考:对象数组中保存的是对象的值还是对象的引用对象数组中保存的是对象的值还是对象的引用?数组数组n一般来说，程序都是根据具体情况在不断地创建新的对象，而这些情一般来说，程序都是根据具体情况在不断地创建新的对象，而这些情况又只有在程序运行的时候才能确定。不到运行时你是不会知道你到况又只有在程序运行的时候才能确定。不到运行时你是不会知道你到底需要多少对象，甚至是什么类型的对象。所以你不能指望用命名的底需要多少对象，甚至是什么类型的对象。所以你不能指望用命名的reference来持有每个对象：来持有每个对象：MyObjectmyReference;n原因就在于，你不可能知道究竟需要多少这样的对象。原因就在于，你不可能知道究竟需要多少这样的对象。n数组的不足数组的不足不能自动调整大小不能自动调整大小不能实现快速的添加和删除对象不能实现快速的添加和删除对象不能存放不同类型的对象不能存放不同类型的对象不能实现不能实现key_valuen如何解决这个问题如何解决这个问题?集合框架中的接口集合框架中的接口q集合是包含一组相关数据元素的对象，它提供了对其所包含的各种元素的操作。q所谓框架就是一个类库的集合。集合框架就是一个用来表示和操作集合的统一的架构，包含了实现集合的接口与类。集合框架中的接口集合框架中的接口nCollection：集合层次中的根接口：集合层次中的根接口nSet：不能包含重复的元素。：不能包含重复的元素。SortedSet是一个按是一个按照升序排列元素的照升序排列元素的SetnList：是一个有序的集合，可以包含重复的元素。：是一个有序的集合，可以包含重复的元素。提供了按索引访问的方式提供了按索引访问的方式nMap：包含了：包含了key-value对。对。Map不能包含重复的不能包含重复的key。SortedMap是一个按照升序排列是一个按照升序排列key的的Map集合框架结构图集合框架结构图SortedSetSetHashSetLinkedHashSetTreeSetListArrayListLinkedListMapSortedMapHashMapTreeMapCollectionSetListArrayListnArrayList：我们可以将其看作是能够自动增长容：我们可以将其看作是能够自动增长容量的数组。量的数组。n利用利用ArrayList的的toArray()返回一个数组。返回一个数组。nArrays.asList()返回一个列表。返回一个列表。n迭代器迭代器(Iterator)给我们提供了一种通用的方式来给我们提供了一种通用的方式来访问集合中的元素。访问集合中的元素。迭代器的工作原理迭代器的工作原理nTheIteratorinterfaceisshownbelow:publicinterfaceIteratorbooleanhasNext();Objectnext();voidremove();/Optionaln可以认为迭代器是指向两个元素之间的位置可以认为迭代器是指向两个元素之间的位置.n在调用在调用remove()remove()方法的时候方法的时候,必须调用一次必须调用一次next()next()方法方法.nremove()remove()方法实际上是删除上一个返回的元素方法实际上是删除上一个返回的元素.返回的元素删除的元素next()remove()next()算法算法Collections类类n排序：排序：Collections.sort()（1）自然排序）自然排序(natural ordering)；（2）实现比较器）实现比较器(Comparator)接口。接口。(3)混排功能混排功能n取最大和最小的元素：取最大和最小的元素：Collections.max()、Collections.min()。n在已排序的在已排序的List中搜索指定的元素：中搜索指定的元素：Collectons.binarySearch()。排序排序-Comparable接口接口qComparable接口强行对实现它的每个类的对象进行整体排序。此排序被称为该类的自然排序，类的compareTo方法被称为它的自然比较方法。q如果你要为一个其元素没有实现Comparable的列表排序，Collections.sort(list)将扔出一个ClassCastException。qcompareTo方法将接收对象与特定对象进行比较，并在接收对象小于、等于或大于特定对象时分别返回-1、0或1排序排序-Comparator接口接口q如果要对某些对象不按自然顺序进行排序，又会怎么样呢？或者，如果你要为某些不实现Comparable的对象进行排序呢？为做这些事情，需要提供一个Comparator。Comparator实际就是一个封装了排序的对象。与Comparable接口类似，Comparator接口由一个的方法构成:publicinterfaceComparatorintcompare(Objecto1,Objecto2);qcompare方法比较它的两个参数，当第一个参数小于、等于或大于第二个参数时，分别返回一个负整数、空或正整数。如果其中一个参数具有对Comparator不适合的类型，compare方法则扔出一个ClassCastException搜索搜索q除了排序之外，Collections和Arrays类提供在Collection中查找最大值和最小值的机制，还提供对List或数组进行搜索的机制。q当某个列表是无序时,可以使用List的contains()方法查明某个元素是不是该列表的一部分。q如果预先使用Collections.sort()对List进行了排序，就可以使用binarySearch()方法进行更快的二分搜索。否则，必须提供Comparator。此外，如果用某个Comparator进行排序，必须在二分搜索时使用同一个Comparator。publicstaticintbinarySearch(Listlist,Objectkey)publicstaticintbinarySearch(Listlist,Objectkey,Comparatorcomparator)LinkedListnLinkedList是采用双向循环链表实现的。是采用双向循环链表实现的。n利用利用LinkedList实现栈实现栈(stack)、队列、队列(queue)、双向队列双向队列(double-endedqueue)。用用LinkedList实现队列实现队列n队列队列(Queue)(Queue)是限定所有的插入只能在表的一端进行，而所有的删除是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。都在表的另一端进行的线性表。n表中允许插入的一端称为队尾表中允许插入的一端称为队尾(Rear)(Rear)，允许删除的一端称为队头，允许删除的一端称为队头(Front)(Front)。n队列的操作是按先进先出队列的操作是按先进先出(FIFO)(FIFO)的原则进行的。的原则进行的。n队列的物理存储可以用顺序存储结构，也可以用链式存储结构。队列的物理存储可以用顺序存储结构，也可以用链式存储结构。a1a2a3an队头队尾出队入队用用LinkedListLinkedList实现栈实现栈n栈栈(Stack)(Stack)也是一种特殊的线性表，是也是一种特殊的线性表，是一种后进先出一种后进先出(LIFO)(LIFO)的结构。的结构。n栈是限定仅在表尾进行插入和删除运算栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶的线性表，表尾称为栈顶(top)(top)，表头，表头称为栈底称为栈底(bottom)(bottom)。n栈的物理存储可以用顺序存储结构，也栈的物理存储可以用顺序存储结构，也可以用链式存储结构。可以用链式存储结构。a1a2an栈底栈顶出栈进栈ArrayList和和LinkedList的比较的比较nArrayList底层采用数组完成，而底层采用数组完成，而LinkedList则是则是以一般的双向链表以一般的双向链表(double-linkedlist)完成，其完成，其内每个对象除了数据本身外，还有两个内每个对象除了数据本身外，还有两个引用，分引用，分别指向前一个元素和后一个元素。别指向前一个元素和后一个元素。n如果我们经常在如果我们经常在List的开始处增加元素，或者在的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用，否则的话，使用ArrayList将更加快将更加快速。速。Setn扩展扩展CollectionCollection接口接口n不允许重复元素不允许重复元素n对对 equals()equals()和和 hashcode()hashcode()方法添加了限制方法添加了限制nHashSetHashSet和和TreeSetTreeSet是是SetSet的实现的实现HashSetn实现实现Set接口的接口的hashtable(哈希表哈希表)，依靠，依靠HashMap来实现的。来实现的。n我们应该为要存放到我们应该为要存放到哈希表哈希表的各个对象定义的各个对象定义hashCode()和和equals()。HashSetn散列表又称为哈希表。散列表算法的基本思想是：散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量，通过一定的函数关系（散列函以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散数）计算出对应的函数值，以这个值作为该结点存储在散列表中的地址。列表中的地址。n当散列表中的元素存放太满，就必须进行再散列，将产生当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除。在散列表将被删除。在JavaJava语言中，通过负载因子语言中，通过负载因子(load(load factor)factor)来决定何时对散列表进行再散列。例如：如果负来决定何时对散列表进行再散列。例如：如果负载因子是载因子是0.750.75，当散列表中已经有，当散列表中已经有75%75%的位置已经放满，的位置已经放满，那么将进行再散列。那么将进行再散列。n负载因子越高负载因子越高(越接近越接近1.0)1.0)，内存的使用效率越高，元素，内存的使用效率越高，元素的寻找时间越长。负载因子越低的寻找时间越长。负载因子越低(越接近越接近0.0)0.0)，元素的寻，元素的寻找时间越短，内存浪费越多。找时间越短，内存浪费越多。TreeSetnTreeSetTreeSet是依靠是依靠TreeMapTreeMap来实现的。来实现的。nTreeSetTreeSet是一个有序集合，是一个有序集合，TreeSetTreeSet中元素将按照升序排列，中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着缺省是按照自然顺序进行排列，意味着TreeSetTreeSet中元素要中元素要实现实现ComparableComparable接口。接口。n我们可以在构造我们可以在构造TreeSetTreeSet对象时，传递实现了对象时，传递实现了ComparatorComparator接口的比较器对象。接口的比较器对象。SetSet(interface)加至Set内的每个元素都必须独一无二，不与其它元素重复；Set不允许持有重复元素，每个元素都必须定义equals()以判断所谓的独一性，Set具有和Collection一样的interface。Set interface并不保证以任何和特定次序来维护其元素HashSet一种把查找时间看得很重要的Sets。所有与元素都必须定义HashCode()TreeSet底层结构为tree的一种有序(ordered)Set。这么一来你便可以自Set中萃取出一个带次序性的序列（ordered squence）HashSet和和TreeSet的比较的比较nHashSetHashSet是基于是基于HashHash算法实现的，其性能通常都优于算法实现的，其性能通常都优于TreeSetTreeSet。我们通常都应该使用。我们通常都应该使用HashSetHashSet，在我们需要排序，在我们需要排序的功能时，我们才使用的功能时，我们才使用TreeSetTreeSet。HashMap实现了Map接口用于存储键/值映射关系不能保证其元素的存储顺序Mapn将键映射至值的对象将键映射至值的对象每个键最多都只能映射至一个值每个键最多都只能映射至一个值n重要方法重要方法基本操作基本操作 put()、get()、remove()、containsKey()、containsValue()、size()和和 isEmpty()批操作批操作 putAll()和和 clear()集合视图集合视图 keySet()、values()和和 entrySet()HashMapnHashMapHashMap对对keykey进行散列。进行散列。nkeySet()keySet()、values()values()、entrySet()entrySet()。Map视图操作视图操作nentrySet()返回返回Map中所包含映射的中所包含映射的Set视图。视图。Set中的每个中的每个元素都是一个元素都是一个Map.Entry对象，可以使用对象，可以使用getKey()和和getValue()方法（还有一个方法（还有一个setValue()方法）访问后者方法）访问后者的键元素和值元素的键元素和值元素nkeySet()返回返回Map中所包含键的中所包含键的Set视图。视图。删除删除Set中的元中的元素还将删除素还将删除Map中相应的映射（键和值）中相应的映射（键和值）nvalues()返回返回map中所包含值的中所包含值的Collection视图。视图。删除删除Collection中的元素还将删除中的元素还将删除Map中相应的映射（键和中相应的映射（键和值）值）TreeMapnTreeMapTreeMap按照按照keykey进行排序。进行排序。MapMap(interface)维护key-value的关联性，使你可以使用key来查找valueHashMap基于hashtable(哈希表)完成的一个实现品。可用它来取代Hashtable(Java2以前的一种container)。可在常量时间内插入元素，或找出一组key-valuepair。通过其构造函数，使用者可调整效能表现。因为它允许你设定capacity（容量）和loadfactor(负载因子)TreeMap当你检查其中的key或key-valuepairs时，会以排序形式出现（前后次序由Comparable或Comparator决定）。TreeMap的特色便是让你得以排序形式得到结果。TreeMap是唯一具有subMap()的一种Map，这个函数让你得以返回tree中的部分组成。HashMap和和TreeMap的比较的比较n和和SetSet类似，类似，HashMapHashMap的速度通常都比的速度通常都比TreeMapTreeMap快，只有在快，只有在需要排序的功能的时候，才使用需要排序的功能的时候，才使用TreeMapTreeMap。Java1.0/1.1的集合类的集合类nVectorVector：用：用ArrayListArrayList代替代替VectorVector。nHashtableHashtable：用：用HashMapHashMap代替代替HashtableHashtable。nSatckSatck：用：用LinkedListLinkedList代替代替StackStack。nPropertiesPropertiesVector类它具有类似数组的数据结构，而且是动态的可以存放一定数量的元素容量可以递增VectorVector类类类类Vector类类n实现可变长度的对象数组实现可变长度的对象数组n组件可以使用整型下标访问组件可以使用整型下标访问n构造函数构造函数Vector()Vector(Collectionc)Vector(intcap)Vector(intcap,intinc)PropertiesPropertiesn用于存取用于存取*.Properties文件文件forEachn“增强的增强的for”n使编译器能够创建遍历集合的迭代器，这样就不使编译器能够创建遍历集合的迭代器，这样就不用声明迭代器对象和使用方法用声明迭代器对象和使用方法hasNext()和和next()来访问集合中的连续元素。来访问集合中的连续元素。nforEach语句在元素列表上隐式分配了一个迭代语句在元素列表上隐式分配了一个迭代器，该语句通过连续调用器，该语句通过连续调用next()方法来扫描元素方法来扫描元素列表，其中列表，其中next()方法抽取元素并将其指派给局方法抽取元素并将其指派给局部变量部变量str。eg:for(Stringstr:list)总结总结nLinkedList是一个序列，该序列的元素都有一个是一个序列，该序列的元素都有一个值以及标识序列中相邻元素的链接值以及标识序列中相邻元素的链接nHashMap把各个把各个Object映射起来，实现了映射起来，实现了“键键值值”对应的快速存取对应的快速存取n迭代器是一个为扫描集合中整个元素范围的迭代器是一个为扫描集合中整个元素范围的“定定位器位器”nforEach能使编译器能够创建遍历集合的迭代器能使编译器能够创建遍历集合的迭代器使用集合框架注意事项ObjectObjectObject加入集加入集合合从集合中取从集合中取出出(Rabbit)object(Car)object(Student)objectRabbitCarStudentRabbitCarStudent任何对象加入集合类后，自动转变为任何对象加入集合类后，自动转变为Object类型；取出类型；取出时，需要进行强制类型转换，恢复为特定的类型时，需要进行强制类型转换，恢复为特定的类型集合框架关系图集合框架关系图集合框架关系图集合框架关系图(简简)