JAVA-泛型与集合框架课件

2023/7/22《Java面向对象程序设计》第13章配合<Java面向对象程序设计>例子源代码一起使用Powerpoint制作：耿祥义张跃平泛型与集合框架12023/7/22主要内容泛型链表堆栈散列映射树集树映射难点树映射导读22023/7/22在jdk1.2之后，Java提供了实现常见数据结构的类，这些实现数据结构的类通称为Java集合框架。在JDK1.5后，Java集合框架开始支持泛型，本章首先介绍泛型，然后讲解常见数据结构类的用法。概述32023/7/22§13.1泛型泛型（Generics）是在JDK1.5中推出的，其主要目的是可以建立具有类型安全的集合框架，如链表、散列映射等数据结构。42023/7/22§13.1.1泛型类声明可以使用“class名称<泛型列表>”声明一个类,为了和普通的类有所区别，这样声明的类称作泛型类,如：

classPeople<E>

参考：Cone.java

52023/7/22§13.1.2使用泛型类声明对象泛型类声明和创建对象时，类名后多了一对“<>”，而且必须要用具体的类型替换“<>”中的泛型。例如：Cone<Circle>coneOne;coneOne=newCone<Circle>(newCircle());例题13-162023/7/22§13.1.3泛型接口可以使用“interface名称<泛型列表>”声明一个接口，这样声名的接口称作泛型接口如

interfaceComputer<E>

例题13-272023/7/228.1Java中的集合类结构

Java提供了集合类(Collection)及其API，于是用户可以通过统一的操作接口，使得从一种数据结构到另一种数据结构的转换极为方便，简化了程序员编程时的负担。任何集合框架包括三部分内容：对外的接口接口的实现对集合运算的算法集合API的根是一个集合接口，存放于java.util包中。Collection接口定义了所有属于集合的类都应该具有的通用方法。82023/7/228.1Java中的集合类结构Java集合框架结构由两颗接口树构成：第一棵树根节点为Collection接口，它定义了所有集合的基本操作，如添加、删除、遍历等。它的子接口Set、List等则提供了更加特殊的功能。

92023/7/22Collection接口102023/7/22第二棵树根节点为Map接口。与哈希表类似，保持的是键值对的集合，可以通过键来实现对值元素的快速访问。112023/7/22Map接口第二棵树根节点为Map接口。与哈希表类似，保持的是键值对的集合，可以通过键来实现对值元素的快速访问。122023/7/22132023/7/228.2Collection接口方法名功能说明booleanadd(Objecto)插入单个对象booleanaddAll(Collectionc)添加另外一个集合对象c中的所有对象Object[]toArray()以数组的形式返回内容Object[]toArray(Object[]a)以数组的形式返回内容Iteratoriterator()返回一个实现了Iterator接口的对象voidclear()清空所有对象booleanremove(Objecto)删除指定的对象booleanramoveAll(Collectionc)删除c中所拥有的对象booleanretainAll(Collectionc)保留指定的对象booleancontains(Objecto)检查是否包含有指定的对象booleancontainsAll(Collectionc)检查是否包含c中所包含的对象booleanisEmpty()判断集合是否为空intsize()获取集合中的对象个数142023/7/2213.2List接口List接口是包含有序元素的一种Collection子接口，其中的元素必须按序存放。元素之间的顺序关系可以由插入的时间先后决定，也可以由元素值的大小决定。List接口使用类似于数组下标的索引的概念表示元素在List中的位置。用户能够使用索引来访问List中的元素。索引从0开始。为了保持元素的有序的特性，List接口新增加了大量的方法，使之能够在序列中间根据具体位置添加和删除元素。

152023/7/22§13.2链表链表是由若干个称作节点的对象组成的一种数据结构，每个节点含有一个数据和下一个节点的引用。162023/7/22List接口的主要方法

方法名功能说明voidadd(intindex,Objectelement)在指定位置上添加一个对象booleanaddAll(intindex,Collectionc)将c中的所有对象添加到指定位置ListIteratorlistIterator()返回一个ListIteratorListIteratorlistIterator(intindex)返回指定的ListIteratorObjectget(intindex)返回指定位置的对象Objectremove(intindex)删除指定位置的对象Objectset(intindex,objectelement)用元素element取代位置index上的元素,返回被取代的元素intindexOf(objecto)返回第一个匹配对象的位置intlastIndexOf(objecto)返回最后一个匹配对象的索引172023/7/2213.2.1LinkedList类

LinkedList类提供了使用双向链表实现数据存储的方法，可按序号检索数据，并能够进行向前或向后遍历。由于插入数据时只需要记录元素的前后项即可，所以插入数度较快，因此适合于在链表中间需要频繁进行插入和删除的操作。182023/7/22§13.2.1LinkedList<E>泛型类◆

LinkedList<E>泛型类创建的对象以链表结构存储数据，习惯上称LinkedList类创建的对象为链表对象。例如，LinkedList<String>mylist=newLinkedList<String>();创建一个空双链表。

◆

add(Eobj)向链表依次增加节点192023/7/22Linkedlist接口的主要方法

方法名功能说明publicbooleanadd(Objectelement)向链表末尾添加一个新的结点publicbooleanadd(intindex，Objecto)将对象o添加到链表中由index指定位置publicbooleanaddFirst(Objecto)将对象o添加到链表的头部publicbooleanaddLast(Objecto)将对象向o添加到链表的末尾publicbooleanclear()删除链表的所有节点，成为空链表publicObjectremove(intindex)删除指定位置上的结点publicObjectremove(Objecto)删除首次出现含有o的结点publicObjectget(intindex)返回链表中index位置处的结点对象202023/7/22

ArrayList类是List接口的一个可变长数组的实现，即一个ArrayList类对象可以动态改变大小。每个ArrayList类对象都有一个容量(Capacity)，用于存储元素的数组的大小。容量可随着不断添加新元素而自动增加。序列以初始长度创建，当长度超过时，集合自动变大；当删除对象时，集合自动变小。集合中允许存储null值。ArrayList类的随机访问速度快，但是向表中插入和删除比较慢。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。8.4.2ArrayList类212023/7/22ArrayList常用的构造函数如下：ArrayList()：构建一个空的ArrayList对象。ArrayList(Collectionc)：构建一个ArrayList对象，并且将集合c中所有元素添加进去。ArrayList(intinitialCapacity)：构建一个拥有特定容量的空ArrayList对象。ArrayList的很多成员方法与LinkedList相似，两者的本质区别是一个使用顺序结构，另一个使用链表结构，因此，它也可以使用LinkedList类提供的方法进行列表的操作。8.4.2ArrayList类222023/7/22232023/7/228.5Iterator接口除了使用集合对象的get()方法可以实现对集合中的元素的遍历外。利用迭代器(Iterator)也可以实现元素遍历。

迭代器是一个实现了Iterator接口或者ListIterator接口的对象。ListIterator继承了Iterator，可以进行双向遍历以及元素的修改。242023/7/22252023/7/22

Iterator迭代器只能前向循环，如果需要双向遍历，则可以使用更高级的ListIterator迭代器，ListIterator接口继承自Iterator接口。

ListIterator迭代器除了有next()方法外，还新增了hasprevious()方法和previous()方法，实现前向遍历。ListIterator还可以定位当前的索引位置，调用nextIndex()和previousIndex()就可以实现。

262023/7/22272023/7/22282023/7/2213.3Stack类在Java语言中，Stack类是java.util包中专门用来实现栈的工具类。Stack类继承自Vector类，因此它是Vector的一个子类，实现了一个后进先出的堆栈。Stack类继承了Vector类的所有方法，还新增了一些方法使得Vector类能够实现堆栈的操作。292023/7/221、创建Stack类对象

publicStack()；它建立一个空的堆栈2、压栈与出栈操作publicObjectpush(Objectitem)：将指定的对象压入栈

publicObjectpop()：将栈顶的对象从栈中取出3、检查栈是否为空

publicbooleanempty()：测试堆栈是否为空，若堆栈中没有对象元素，则返回true，否则返回false4、查看栈顶端的数据，但不删除该数据。

publicobjectpeek()5、获取数据在堆栈中的位置。最顶端的位置是1，向下依次增加。如果堆栈不含有此数据，则返回-1。publicsearch(Objectdata)例:13.6302023/7/2213.4Map及HashMap接口312023/7/22Map接口的主要方法

方法名功能说明Objectput(Objectkey,Objectvalue)插入新的对象，并用key作为其键字voidputAll(Mapt)将另一个Map中的所有对象复制进来SetentrySet()返回映射中的关键字－值对的集合SetkeySet()返回映射中所有关键字的集合Collectionvalues()返回映射中所有值的集合Objectremove(Objectkey)删除指定的对象Objectget(Objectkey)获取与key相联系的对象booleancontainsKey(Objectkey)判断是否包含指定的键值booleancontainsValue(Objectvalue)判断是否包含指定的对象322023/7/22

Map接口的一个抽象类是AbstractMap。在这个抽象类中，部分地实现了Map接口中的成员方法，使得具体的映射类不必实现Map接口中的每个成员方法。AstractMap抽象类有三个子类：TreeMapHashMapWeakHashMap：

AstractMap抽象类332023/7/22

(1)TreeMap描述了一个按键值升序排列的映射,它有一些扩展的方法，如firstKey()，lastKey()等，还可以从TreeMap中指定一个范围以取得其子Map。

(2)HashMap描述的一个映射中允许存储空对象，由于键必须唯一，所以只能有一个空键值。(3)WeakHashMap是一种改进的HashMap，它描述了一个映射，当集合中的某些内容不再使用时需清除掉无用的数据，并使用垃圾回收机制进行回收。AstractMap抽象类342023/7/22HashMap通过哈希运算可以快速查找一个键，因此在适合于在Map中插入、删除和定位元素。如果要按照自然顺序或者自定义顺序遍历关键字，TreeMap会更好些。

2．HashMap352023/7/22由于HashMap实现了Map接口，因此它没有自己的新方法。HashMap的构造方法如下：HashMap()：创建一个空的HashMap集合。HashMap(Mapt)：创建一个哈希集，将t中所有元素添加进去。HashMap(intinitialCapacity)：创建一个拥有特定容量的空HashMap集合。HashMap(intinitialCapacity，floatloadFactor)：创建一个拥有特定容量和加载因子的空HashMap。362023/7/22

散列表中的容量

是指能够存储对象的数量。当对象存储的数目到达容量乘以加载因子的值时，容量将会自动地增加到原容量的2倍加1，加1的目的是确保散列表的容量为质数或奇数。例如:aMap对象最初的容量为151，当存储对象的数量达到91时，容量将会自动增加到303。372023/7/22§13.4散列映射

§13.4.1HashMap<K,V>泛型类

HashMap<K,V>对象采用散列表这种数据结构存储数据，习惯上称HashMap<K,V>对象为散列映射。例如HashMap<String,Student>hashtable=HashSet<String,Student>();hashtable可以存储“键/值”对数据。

相关方法：publicVput(Kkey,Vvalue)将键/值对数据存放到散列映射中，该方法同时返回键所对应的值。382023/7/22

loadFactor是0.01.0之间的一个数，通常默认为0.75。加载因子定义了哈希集合充满什么程度时就要增加容量。即当元素的数目大于哈希集容量和加载因子之积时，哈希集容量将扩展。392023/7/22HashMap类的主要成员方法方法描述Objectput(Objectkey,Objectvalue)用键值key存储对象valuevoidputAll(Mapmap)将map中的所有键值/对象传递给当前的散列表Objectget(Objectkey)返回键值key所对应的对象remove(Objectkey)删除key键值所对应的对象SetKeySet()返回一个Set对象，其内容为所有的键值SetentrySet()返回一个Set对象，其内容为所有的键值/对象对Collectionvalues()返回一个Collection对象，其内容为散列表中存储的所有对象ObjectgetKey()返回对象的键值ObjectgetValue()返回所对应的对象voidsetValue(Objectnew)将对象设置为new402023/7/22§13.4.2常用方法publicvoidclear()

清空散列映射。publicObjectclone()

返回当前散列映射的一个克隆。publicbooleancontainsKey(Objectkey)

如果散列映射有“键/值”对使用了参数指定的键，方法返回true，否则返回false。publicbooleancontainsValue(Objectvalue)

如果散列映射有“键/值”对的值是参数指定的值。publicVget(Objectkey)

返回散列映射中使用key做键的“键/值”对中的值。publicbooleanisEmpty()

如果散列映射不含任何“键/值”对，方法返回true，否则返回false。publicVremove(Objectkey)

删除散列映射中键为参数指定的“键/值”对，并返回键对应的值。publicintsize()

返回散列映射的大小，即散列映射中“键/值”对的数目。412023/7/22§13.6树映射

TreeMap<K,V>类实现了Map<K,V>接口，称TreeMap<K,V>对象为树映射。树映射使用publicVput(Kkey,Vvalue);方法添加节点。例题13-9422023/7/22§13.4.3遍历散列映射publicCollection<V>values()方法返回一个实现Collection<V>接口类创建的对象。使用接口回调技术，即将该对象的引用赋给Collection<V>接口变量，该接口变量可以回调iterator()方法获取一个Iterator对象，这个Iterator对象存放着散列映射中所有“键/值”对中的“值”。432023/7/2213.5Set接口Set接口是一种不包含重复元素的Collection的子接口。Set接口中并没有引入新方法，它提供的基本方法和Collection接口类似。442023/7/22452023/7/22Set接口派生了一个SortedSet接口和一个抽象类AbstractSet。SortedSet接口用来描述有序的元素集合，TreeSet实现了这个接口，它将放入其中的元素按序存放，要求其中的对象是可排序的。抽象类AbstractSet实现了部分Collection接口，并有一个子类HashSet，它以散列方式表示集合内容。

462023/7/22§13.5树集

§13.5.1TreeSet<E>泛型类

TreeSet<E>类创建的对象称作树集。例如TreeSet<String>mytree=newTreeSe<String>();然后使用add方法为树集添加节点，例如mytree.add("boy");472023/7/22§13.5.2节点的大小关系

树集用add方法添加节点，节点会按其存放的数据的“大小”顺序一层一层地依次排列，在同一层中的节点从左到右按“大小”顺序递增排列，下一层的都比上一层的小。482023/7/22§13.5.3TreeSet类的常用方法publicbooleanadd(Eo)

向树集添加加节点。publicvoidclear()

删除树集中的所有节点。publicvoidcontains(Objecto)

如果树集中有包含参数指定的对象，该方法返回true，否则返回false。publicEfirst()

返回树集中的第一个节点中的数据（最小的节点）。publicElast()

返回最后一个节点中的数据（最大的节点）。publicisEmpty()

判断是否是空树集，如果树集不含任何节点，该方法返回true。publicbooleanremove(Objecto)

删除树集中的存储参数指定的对象的最小节点。publicintsize()

返回树集中节点的数目。例题13-8492023/7/22HashSet类

HashSet类是实现了Set接口的标准类，它创建了一个使用哈希表存储的集合，能快速定位一个元素，从而可以优化查询的速度，特别是在查找大集合时HashSet类比较有用。HashSet的构造函数如下：HashSet()：创建一个空的哈希集。HashSet(Collectionc)：创建一个哈希集，并且将集合c中所有元素添加进去。HashSet(intinitialCapacity)：创建一个拥有特定容量的空哈希集。HashSet(intinitialCapacity，floatloadFactor)：创