第9章Java的集合类课件.ppt

1、第第9章章 Java的集合类的集合类学习重点：学习重点：l集合类与普通数组的区别集合类与普通数组的区别l各种集合类的特点及适用条件各种集合类的特点及适用条件第第9章章 Java的集合类的集合类 9.19.1 集合类概述集合类概述 9.29.2 原集合类原集合类 9.2.19.2.1 数组数组 9.2.29.2.2 Vector Vector类类 9.2.39.2.3 BitSet BitSet类类 9.2.49.2.4 Stack Stack类类 9.2.59.2.5 Hashtable Hashtable类类 9.39.3 新集合类新集合类 9.3.19.3.1 Collection Col

2、lection 9.3.29.3.2 List List 9.3.39.3.3 Set Set 9.3.49.3.4 Map Map 9.3.59.3.5 Utilities Utilities 9.49.4 练习题练习题 9.1 9.1 集合类概述集合类概述l集合类是用来存放某类对象的。我们知道，数组是有固定长度的，在定集合类是用来存放某类对象的。我们知道，数组是有固定长度的，在定义数组的时候，就需要确定这个数组的内存空间，但很多时候我们不能义数组的时候，就需要确定这个数组的内存空间，但很多时候我们不能确定需要存放多少元素，这时数组就显得很不方便，这时就需要使用集确定需要存放多少元素，这时数

3、组就显得很不方便，这时就需要使用集合类。合类。l集合类有一个共同特点，就是它们只容纳对象集合类有一个共同特点，就是它们只容纳对象(实际上是对象名，既指实际上是对象名，既指向地址的指针向地址的指针)，这一点和数组不同，数组可以容纳对象和简单数据。，这一点和数组不同，数组可以容纳对象和简单数据。l集合类容纳的对象都是集合类容纳的对象都是ObjectObject类的实例，一旦把一个对象置入集合类中，类的实例，一旦把一个对象置入集合类中，它的类信息将丢失，也就是说，集合类中容纳的都是指向它的类信息将丢失，也就是说，集合类中容纳的都是指向ObjectObject类对象类对象的指针。的指针。9.2 9.2

4、 原集合类原集合类 9.2.1 数组数组例例9.1 数组中容纳对象和简单数据数组中容纳对象和简单数据这个程序中把对象和简单数据分别作为数组的元素，然后对它们分别操作这个程序中把对象和简单数据分别作为数组的元素，然后对它们分别操作 l程序代码程序代码上面的程序中我们用同样的格式设计了两种数组：对象数组和简单数据类型数组，以进行比较。l数组a只是初始化成一个null的对象名(指针)，此时，编译器会禁止我们对 这个指针进行任何实际操作。l数组b被初始化成指向由Weeble类对象构成的一个数组，但那个数组里实际 并未放置任何Weeble对象，所以数组b的元素都是空指针，不能直接 使用，然而，我们仍然可

5、以查询那个数组的大小，因为b指向的是一 个合法对象。这个程序中还用到对象间的赋值，对象间赋值传递的是 指针。例例9.2 对象数组的传递对象数组的传递 这个程序中我们用一个数组来存放香味名(字符串对象)，然后从这个数组中随机抽出香味名，形成20个随机排列，并输出。计算中每次都形成一个新的对象数组，并在不同的方法中传递。l程序代码程序代码lflavorSet()方法创建了一个名为results的String数组。该数组的大小为n，具体数值取决于传递给方法的自变量。随后，它从数组flav里随机挑选一些香料(Flavor)，并将它们置入results里，并最终返回results。返回数组与返回其他任何

6、对象没什么区别，返回的都是一个指针。l另一方面，当flavorSet()随机挑选香料的时候，它需要保证以前挑选过的香料不会再次出现。lmain()能显示出20个完整的香味名集合，所以我们看到flavorSet()每次都用一个随机顺序选择香料。9.2.2 Vector类 该类实现了可变数组。和数组一样，它的元素可通过下标进行访该类实现了可变数组。和数组一样，它的元素可通过下标进行访问。问。VectorVector类的对象通过类的对象通过capacity和和capacityIncrement两个值来改两个值来改变集合的容量，变集合的容量，capacitycapacity指示集合最多能容纳的元素个数

7、，指示集合最多能容纳的元素个数，capacityIncrement指示每次增加多少容量，而不是一个一个增加指示每次增加多少容量，而不是一个一个增加的。的。这个类有这个类有3个属性、多个构造函数和许多其他方法。下面列举几个方个属性、多个构造函数和许多其他方法。下面列举几个方法：法：lvoid addElement(Object obj)在集合的最后增加一个元素在集合的最后增加一个元素lvoid add(int index,Object element)在指定位置增加一个元素在指定位置增加一个元素lObject elementAt(int index)返回指定位置的元素返回指定位置的元素lvoid

8、 insertElementAt(Object obj,int index)在指定位置插入元素在指定位置插入元素lvoid removeElementAt(int index)删除指定位置的元素删除指定位置的元素lint catacity()返回当前容量返回当前容量lint size()返回集合的元素个数返回集合的元素个数例例9.3 9.3 集合中元素必须是同类的对象集合中元素必须是同类的对象l程序代码程序代码l这个程序中只有在执行这个程序中只有在执行(Cat)cats.elementAt(7).print();的时候抛的时候抛出例外。在这个程序中也看到了重新造型的格式：出例外。在这个程序中也

9、看到了重新造型的格式：(Cat)cats.elementAt(i)，因为一个集合的元素是一个因为一个集合的元素是一个ObjectObject类的类的对象，所以必须把它强制转换成对象，所以必须把它强制转换成CatCat类的对象进行操作。类的对象进行操作。能不能把元素转换成能不能把元素转换成DogDog类？类？答案是肯定的，把程序中的最后两句换成如下形式，就能把最后一个元答案是肯定的，把程序中的最后两句换成如下形式，就能把最后一个元素输出。素输出。for(int i=cats.size()-1;i=0;i-)(Dog)cats.elementAt(i).print();这时的输出结果为：这时的输出

10、结果为：Dog#7Exception in thread main java.lang.ClassCastException:Cat at CatsAndDogs.main(CatsAndDogs.java:31)l程序中我们用到了程序中我们用到了size()size()这个方法来确定元素的个数，其实有另一个方这个方法来确定元素的个数，其实有另一个方法可以让程序自动检查元素的类型以及集合的最后一个该类型元素，这就法可以让程序自动检查元素的类型以及集合的最后一个该类型元素，这就是是Enumeration(Enumeration(枚举接口枚举接口)，它是一个简单的反复器，它是一个简单的反复器(it

11、erator)(iterator)，它能实现，它能实现对集合的遍历。实现枚举的对象必须通过对集合的遍历。实现枚举的对象必须通过VectorVector类的方法类的方法elements()elements()来创来创建，这个方法返回反映当前集合内容的实现枚举的对象。然后通过枚举的建，这个方法返回反映当前集合内容的实现枚举的对象。然后通过枚举的方法实现对集合的遍历：方法实现对集合的遍历：Object nextElement()/获得下一个元素，定一次调用返回定一个元素bealoon hasMoreElements()/检查集合中是否有更多的元素我们就用这两个方法来代替上面的一部分程序，其中改动我们

12、就用这两个方法来代替上面的一部分程序，其中改动import语句和主语句和主类如下：类如下：import java.util.*;/这一部分不变public class CatsAndDogs public static void main(String args)Vector cats=new Vector();for(int i=0;i 7;i+)cats.addElement(new Cat(i);cats.addElement(new Dog(7);/以下部分是更新的代码 Enumeration e=cats.elements();/创建Enumeration对象e while(e.ha

13、sMoreElements()/使用e来完成集合的遍历 (Cat)e.nextElement().print();这个程序的输出结果同原先的程序，其中的黑体部分就是更改部分。使用Enumeration，我们不必关心集合中的元素数量。所有工作均由hasMoreElements()和nextElement()自动照管了。9.2.3 BitSet类类 这个类实际是由这个类实际是由“二进制位二进制位”构成的一个构成的一个VectorVector，即这个，即这个VectorVector集合中的元素都是集合中的元素都是falsefalse或或truetrue，默认值都为，默认值都为falsefalse。此

14、外，此外，BitSetBitSet的最小长度是一个长整数的最小长度是一个长整数(Long)(Long)的长度：的长度：6464位，位，这意味着假如我们准备保存比它更小的数据，如这意味着假如我们准备保存比它更小的数据，如8 8位数据，那么位数据，那么BitSetBitSet就显得浪费了。就显得浪费了。它有以下几个特殊的方法：它有以下几个特殊的方法：lpublic void and(BitSet set)进行逻辑运算，还有or()和xor()lpublic int length()有效逻辑位的位数lpublic int size()返回集合中的元素个数，最小为64lpublic void set(

15、int bitIndex)把指定位置的值置为truelpublic void clear(int bitIndex)把指定位置的值置为falselpublic boolean get(int bitIndex)得到制定位置的值例例9.4 使用使用BitSet类类 这段程序的目的是随机产生一个数字串，然后逐一判断它每一个这段程序的目的是随机产生一个数字串，然后逐一判断它每一个二进制位是否为二进制位是否为1 1，是则在，是则在BitSetBitSet的相应位置上置的相应位置上置truetrue，否则置，否则置falsefalse 888l程序代码程序代码9.2.4 Stack类类 Stack类是类

16、是Vector类的子类，它是一个类的子类，它是一个“后入先出后入先出”(LIFO，last-in-first-out)的集合。的集合。Stack的意思就是堆栈，堆栈就像一个桶，只有一个口，放入和取的意思就是堆栈，堆栈就像一个桶，只有一个口，放入和取出都用这个口，最后放入的东西能最先拿出，最先放入的东西只能最后拿出都用这个口，最后放入的东西能最先拿出，最先放入的东西只能最后拿出。通常在堆栈中存入数据称为出。通常在堆栈中存入数据称为“压入压入”(push)，取出数据成为，取出数据成为“弹弹出出”(pop)。由于压入和弹出都在堆栈口进行，所以位置很确定，这和其他。由于压入和弹出都在堆栈口进行，所以位

17、置很确定，这和其他集合不同。和其他所有集合不同。和其他所有JavaJava集合一样，我们压入和弹出的都是对象，所以集合一样，我们压入和弹出的都是对象，所以必须对自己弹出的东西进行造型。必须对自己弹出的东西进行造型。这个类增加了这个类增加了5个方法：个方法：lpublic Object push(Object item)把形参对象压入堆栈lpublic Object pop()弹出第一个对象lpublic Object peek()并不取出的情况下，看定一个对象lpublic boolean empty()是否为空lpublic int search(Object o)检查第一个出现形参对象的位

18、置例例9.5 堆栈类的使用堆栈类的使用 这个程序的目的是将英文的这个程序的目的是将英文的1212个月存放到一个个月存放到一个StackStack中，然后按顺序打中，然后按顺序打印出来。印出来。l程序代码程序代码l从这个程序的结果可以清楚地看到，先压入的后弹出，这个类的对象也从这个程序的结果可以清楚地看到，先压入的后弹出，这个类的对象也可以使用可以使用Vector类的方法，如类的方法，如addElement()和和elementAt()等。等。9.2.5 Hashtable类类 这个类是字典类这个类是字典类(Dictionary)(Dictionary)的子类，字典类是抽象类，它达的子类，字典类

19、是抽象类，它达到的目的是通过一个键到的目的是通过一个键(key)(key)来查找元素，这和实际的查字典及其来查找元素，这和实际的查字典及其相似。相似。l该抽象类有许多方法，该抽象类有许多方法，size()size()告诉我们其中包含了多少元素，告诉我们其中包含了多少元素，isEmpty()isEmpty()判断是否包含了元素判断是否包含了元素(是则为是则为true)true)，put(Object key,Object value)put(Object key,Object value)添加一个值，并将其同一个键关联起来，添加一个值，并将其同一个键关联起来，get(Object key)get

20、(Object key)获得与某个获得与某个键对应的值，而键对应的值，而remove(Object Key)remove(Object Key)用于从列表中删除用于从列表中删除“键值键值”对。对。还可以使用枚举技术，还可以使用枚举技术，keys()keys()产生对键的一个枚举产生对键的一个枚举(Enumeration)(Enumeration)，而，而elements()elements()产生对所有值的一个枚举。产生对所有值的一个枚举。lHashtableHashtable类不仅实现父类的方法，还有自己的方法，下面这个方法就类不仅实现父类的方法，还有自己的方法，下面这个方法就是用来检查形参

21、对象是否是一个散列表的键：是用来检查形参对象是否是一个散列表的键：public boolean containsKey(public boolean containsKey(ObjectObject key)key)例例9.6 用用Hashtable来检查随机数的随机性来检查随机数的随机性 下面的程序将随机整数对应在下面的程序将随机整数对应在020020之间，然后生成之间，然后生成10 00010 000个随机数，看个随机数，看它们在它们在020间的分布如何。间的分布如何。l程序代码程序代码 这个程序中我们建立一个这个程序中我们建立一个HashtableHashtable表表htht，其中的，

22、其中的“键值键值”对是随机数对是随机数(r)(r)与统计数与统计数(Counter.i)(Counter.i)，其中的随机数是键，统计数是值。，其中的随机数是键，统计数是值。9.3 新集合类新集合类l集合类继承关系图集合类继承关系图 l事实上这个集合族中分两个部分。一个是事实上这个集合族中分两个部分。一个是CollectionCollection系，它是以下标访系，它是以下标访问元素的集合，它实际含有问元素的集合，它实际含有ListList和和SetSet两个组件。另一个是两个组件。另一个是MapMap系，它是系，它是一种映射，通过键来访问元素的集合一种映射，通过键来访问元素的集合(可见可见H

23、ashtableHashtable是应该属于这个系是应该属于这个系的的)，9.3.1 CollectionCollectionCollection的所有方法：的所有方法：public int size()public boolean isEmpty()public boolean contains(Object o)是否含有形参对象public Iterator iterator()产生一个反复器，其中包含了该collection对象中所有的元素，类似于一个枚举类型的对象public Object toArray()返回一个包含所有元素的对象数组public Object toArray(Ob

24、ject a)把所有元素放入a中public boolean add(Object o)集合中加入对象，成功时返回truepublic boolean remove(Object o)public boolean containsAll(Collection c)判断c是否为子集public boolean addAll(Collection c)public boolean removeAll(Collection c)清空指定集合public boolean retainAll(Collection c)删除所有c中没有的元素public void clear()清空集合public bo

25、olean equals(Object o)比较两个对象是否相同public int hashCode()获取集合的hashcode例例9.7 Collection9.7 Collection的使用的使用 这个程序非常简单，只是用来演示大部分的这个程序非常简单，只是用来演示大部分的CollectionCollection含有的含有的方法，因为这些方法在它的方法，因为这些方法在它的“子类子类”中都能使用，所以先熟悉这些中都能使用，所以先熟悉这些方方法。由于法。由于CollectionCollection是一个接口，所以它的实例只能是它是一个接口，所以它的实例只能是它“子类子类”的的对象。对象。l

26、程序代码程序代码9.3.2 List9.3.2 List List的明显特征是它的元素有一个确定的顺序，它比的明显特征是它的元素有一个确定的顺序，它比Collection多了一些多了一些指定位置增删改的方法。它能产生指定位置增删改的方法。它能产生ListIterator的对象。实现它的类有的对象。实现它的类有ArrayList和和ArrayList。ArrayList内存中是顺序存储的内存中是顺序存储的(元素的内存位置紧元素的内存位置紧邻邻)，而，而LinkedList内存中是以链表内存中是以链表(数据结构中的内容，这里不再讲数据结构中的内容，这里不再讲)的形的形式存储，所以式存储，所以Arr

27、ayListArrayList比较适用于经常遍历访问，比较适用于经常遍历访问，ArrayList比较适用于比较适用于经常在中间进行增删改操作。经常在中间进行增删改操作。A ArrayList是被用来代替是被用来代替Vector的一个通用的的一个通用的可变数组类，因而，可变数组类，因而，Java1.2Java1.2以后的编程应多使用以后的编程应多使用ArrayList。9.3.3 SetlSet与Collection有完全相同的对外接口，实际上就是一个Collection，但添加到Set的每个元素都必须是独一无二的，Set不会添加重复的元素。添加到Set里的对象必须定义equals()方法，以提

28、供算法来判断欲添加进来的对象是否与已经存在的某对象相等，从而建立对象的惟一性。一个Set不能保证自己可按任何特定的顺序维持自己的元素。l实现Set的类有HashSet和TreeSet，HashSet是以hash桶来存放元素，能实现快速查找，TreeSet是一种有顺序的集合，一般以字典式升序排列，或以创建Set时指定的Comparator来排序，内存中以二叉树型结构存储。由于TreeSet实现了SortedSet，所以有几个特殊的方法，例如：public Object first()获取第一个即排在最低位的一个public Object last()获取排在toElement之前的元素组成的So

29、rtedSet例例9.8 set中元素的惟一性中元素的惟一性l下面的程序演示下面的程序演示SetSet中的元素是惟一的，即使多次添加同一个值，集合中的元素是惟一的，即使多次添加同一个值，集合中依然是原来几个。这个程序使用了中依然是原来几个。这个程序使用了CollectionCollection类中的方法类中的方法l程序代码程序代码 9.3.4 MaplMap这种接口用来维持很多“键值”对，以便通过一个键查找相应的值。lHashMap基于一个散列表实现(用它代替Hashtable)。针对“键值”对的插入和检索，这种形式具有较好的执行性能。lTreeMap 在一个二叉树的基础上实现。查看键或者“键

30、值”对时，它们会按固定的顺序排列(取决于Comparator)。TreeMap最大的好处就是我们得到的是已排好序的结果。TreeMap是含有subMap()方法的惟一一种Map，利用它可以返回树的一部分。lWeakHashMap是一种特殊的HashMap，对于那些弱键，垃圾收集器会自动删除，因而，对应的“键值”对可能会丢失。例例9.9 Map的用法的用法这个程序先定义两个字符串数组，用这些字符串构造这个程序先定义两个字符串数组，用这些字符串构造Map，并把它，并把它的键和值分别输出，然后遍历这个的键和值分别输出，然后遍历这个Map，再使用，再使用Map的一些方法。的一些方法。l程序代码程序代码

31、 可见，虽然testData1被放入了两次，但Map对象中并没有重复的数据，当程序调用：Map m2=fill(new TreeMap(),testData2);m.putAll(m2);我们又可以看到这样的结果：Size=10,Keys:Dopey|Bashful|Belligerent|Sleepy|Lazy|Happy|Comatose|Grumpy|Sneezy|Doc|可见testData2中的数据也放进来了。9.3.5 Utilities1.Arrays Arrays类为所有基本数据类型的数组提供了一个重载的类为所有基本数据类型的数组提供了一个重载的sort()和和binarySe

32、arch()，它们也可用于它们也可用于StringString和和ObjectObject。例例9.10 数组工具的使用数组工具的使用 这个程序定义了两个重载的方法来产生随机字符串，两个重载的打印方这个程序定义了两个重载的方法来产生随机字符串，两个重载的打印方法，法，main()main()方法中用随机类产生随机数进行排序和查找，而后用已定义的方法中用随机类产生随机数进行排序和查找，而后用已定义的随机字符串类产生字符串，排序并查找。随机字符串类产生字符串，排序并查找。l程序代码程序代码l对于字符，如果用默认的比较器，会区分大小写。对于字符，如果用默认的比较器，会区分大小写。例例9.11 自己定

33、义比较方法的自己定义比较方法的sort()这个程序中把接收的对象转化为字符串，并全部改成小写后进行这个程序中把接收的对象转化为字符串，并全部改成小写后进行比较，就不区分大小写了。比较，就不区分大小写了。l程序代码程序代码l这个例子的一个结果为这个例子的一个结果为 例例9.12 比较对象来排序比较对象来排序 这个程序定义了一个比较对象的比较器，可能读者会怀疑如何能这个程序定义了一个比较对象的比较器，可能读者会怀疑如何能比较对象，事实上，只是把对象的某一内容比较对象，事实上，只是把对象的某一内容(如名称、属性值等如名称、属性值等)进进行比较，读者也可以自己定义。行比较，读者也可以自己定义。l程序代

34、码程序代码l程序的结果程序的结果 2.Collections Collections Collections类可用与数组相同的形式排序和搜索一个列表类可用与数组相同的形式排序和搜索一个列表(List)(List)。用于排序和搜索列表的静态方法包含在类。用于排序和搜索列表的静态方法包含在类CollectionsCollections中，但它们拥有与中，但它们拥有与ArraysArrays中差不多的方法名。中差不多的方法名。lsort(List)用于对一个实现了Comparable的对象列表进行排序。lbinarySearch(List,Object)用于查找列表中的某个对象。lsort(List

35、,Comparator)利用一个“比较器”对一个列表进行排序。lbinarySearch(List,Object,Comparator)则用于查找那个列表中的一个对象。例例9.13 9.13 排序工具示范排序工具示范 这个例子利用了上面的CompClass，AlphaComp和Collectionx以及Arrayx来示范Collections中的排序工具。程序用了两个不同的ArrayList对象来演示Collections中的排序和查找方法。l程序代码程序代码l执行结果执行结果 9.4 9.4 练练 习习 题题1.1.选择题选择题(1)(1)Vector类的对象中的元素可以是：类的对象中的元素

36、可以是：A.A.int型整数型整数 B.B.浮点数浮点数 C.C.对象对象 D.D.属性属性(2)(2)BitSotBitSot的最小长度是：的最小长度是：A.A.8 8位位 B.B.1616位位 C.C.3232位位 D.D.6464位位2.2.程序阅读题程序阅读题(1)阅读下列程序，加入输入参数阅读下列程序，加入输入参数a b r a c o p o p s t q，会得到什么样的结会得到什么样的结果？果？import java.util.*;public class Freq private static final Integer ONE=new Integer(1);public s

37、tatic void main(String args)Map m=new TreeMap();for(int i=0;iargs.length;i+)Integer freq=(Integer)m.get(argsi);m.put(argsi,(freq=null?ONE:new Integer(freq.intValue()+1);System.out.println(m.size()+distinct words detected:);System.out.println(m);3.3.编程题编程题(1)(1)编制一个程序，用编制一个程序，用Class类来获取所有关于类来获取所有关于HashSet类的信息。类的信息。(2)(2)用用ArrarList来实现一个列表，然后用来实现一个列表，然后用Collections类进行排序、搜索。类进行排序、搜索。用不同类型的元素进行试验。用不同类型的元素进行试验。(3)(3)用用HashMap来检查随机数的分布情况。来检查随机数的分布情况。