《JAVA集合与泛型》PPT课件.ppt

1,2019年5月12日星期日,第9章,集合类与泛型程序设计,2,2019年5月12日星期日,9.1 Java中的集合类结构,Java提供了集合类(Collection)及其API，于是用户可以通过统一的操作接口，使得从一种数据结构到另一种数据结构的转换极为方便，简化了程序员编程时的负担。 任何集合框架包括三部分内容： 对外的接口 接口的实现 对集合运算的算法 集合API的根是一个集合接口，存放于java.util包中。Collection接口定义了所有属于集合的类都应该具有的通用方法。,3,2019年5月12日星期日,Java集合框架结构由两颗接口树构成： 第一棵树根节点为Collection接口，它定义了所有集合的基本操作，如添加、删除、遍历等。它的子接口Set、List等则提供了更加特殊的功能。 第二棵树根节点为Map接口。与哈希表类似，保持的是键值对的集合，可以通过键来实现对值元素的快速访问。,4,2019年5月12日星期日,Collection接口,5,2019年5月12日星期日,Map接口,6,2019年5月12日星期日,Collection： 每个元素都是单一对象。 List以特定顺序容纳元素。 Set中不能有重复的元素。 Map： 每个元素都是一对key-value（键值实值）对象，且每个元素中的键值都不能与其他元素中的键值相同。,7,2019年5月12日星期日,集合接口,8,2019年5月12日星期日,9.2 Collection接口,Collection接口是构造集合框架的基础。它声明所有集合类都将拥有的核心方法。 包含下面几种类型的方法 增加元素，清除元素，判断元素的存在 返回迭代接口，把集合转换成数组 集合的大小,9,2019年5月12日星期日,9.2 Collection接口,例9-1,10,2019年5月12日星期日,9.3 Set接口,Set接口是一种不包含重复元素的Collection的子接口。Set接口中并没有引入新方法，它提供的基本方法和Collection接口类似。 Set接口派生了一个SortedSet接口和一个抽象类AbstractSet。,11,2019年5月12日星期日,实现Set接口的类,SortedSet接口用来描述有序的元素集合 TreeSet实现了这个接口，它将放入其中的元素按序存放，要求其中的对象是可排序的。 抽象类AbstractSet实现了部分Collection接口，并有一个子类HashSet，它以散列方式表示集合内容。,12,2019年5月12日星期日,HashSet类,HashSet扩展AbstractSet并且实现Set接口。 它创建了一个使用哈希表存储的集合，能快速定位一个元素，从而可以优化查询的速度，特别是在查找大集合时HashSet类比较有用。 该类集使用散列表进行存储。 在散列(hashing)中，一个关键字的信息内容被用来确定唯一的一个值，称为散列码（hashcode）。而散列码被用来当作与关键字相连的数据的存储下标。 存储在HashSet中的元素必须正确覆盖java.lang.Object中定义的hashCode()方法。 HashSet的构造函数如下： HashSet()：创建一个空的哈希集。 HashSet(Collection c)：创建一个哈希集，并且将集合c中所有元素添加进去。 HashSet(int initialCapacity)：创建一个拥有特定容量的空哈希集。 HashSet(int initialCapacity，float loadFactor)：创建一个拥有特定容量和加载因子的空哈希集。,13,2019年5月12日星期日,loadFactor是0.01.0之间的一个数，通常默认为0.75。加载因子定义了哈希集合充满什么程度时就要增加容量。即当元素的数目大于哈希集容量和加载因子之积时，哈希集容量将扩展。 例：,HashSet hs = new HashSet(); hs.add(“A“); hs.add(“B“); hs.add(“C“); hs.add(“D“); hs.add(“E“); hs.add(“F“); hs.add(“A“); System.out.println(hs);,D, A, F, C, B, E 从输出结果可以看出，元素并没有按顺序进行存储，并且也没有重复元素。例9-2,14,2019年5月12日星期日,TreeSet类,TreeSet为使用树结构进行存储的Set接口提供了一个工具 对象按升序存储。访问和检索是很快的。 在存储了大量的需要进行快速检索的排序信息的情况下，TreeSet是一个很好的选择。,15,2019年5月12日星期日,TreeSet的使用,TreeSet hs = new TreeSet(); hs.add(“D“); hs.add(“E“); hs.add(“F“); hs.add(“A“); hs.add(“B“); hs.add(“C“); hs.add(“A“); System.out.println(hs);,该程序的输出如下： A, B, C, D, E, F TreeSet按树存储其元素，它们被按照自然顺序自动安排，也不能有重复元素 例9-3,16,2019年5月12日星期日,9.4 List接口,List接口是包含有序元素的一种Collection子接口，其中的元素必须按序存放。元素之间的顺序关系可以由插入的时间先后决定，也可以由元素值的大小决定。 List接口使用类似于数组下标的索引的概念表示元素在List 中的位置。用户能够使用索引来访问List 中的元素。索引从0开始。为了保持元素的有序的特性，List接口新增加了大量的方法，使之能够在序列中间根据具体位置添加和删除元素。,17,2019年5月12日星期日,List接口的主要方法,18,2019年5月12日星期日,9.4.1 LinkedList 类,类ArrayList、LinkedList、Vector、Stack等实现了List接口。 LinkedList类提供了使用双向链表实现数据存储的方法，可按序号检索数据，并能够进行向前或向后遍历。 由于插入数据时只需要记录元素的前后项即可，所以插入数度较快，因此适合于在链表中间需要频繁进行插入和删除的操作。 LinkedList的构造方法： LinkedList();创建一个空链表 LinkedList(Collection c);创建一个以集合c中元素为初始值的链表,19,2019年5月12日星期日,Linkedlist接口的主要方法,例9-4,20,2019年5月12日星期日,ArrayList类是List接口的一个可变长数组的实现，即一个ArrayList类对象可以动态改变大小。每个ArrayList类对象都有一个容量(Capacity)，用于存储元素的数组的大小。容量可随着不断添加新元素而自动增加。 序列以初始长度创建，当长度超过时，集合自动变大；当删除对象时，集合自动变小。集合中允许存储null值。ArrayList类的随机访问速度快，但是向表中插入和删除比较慢。 当需要插入大量元素时，在插入前可以调用ensureCapacity 方法来增加ArrayList 的容量以提高插入效率。,9.4.2 ArrayList 类,21,2019年5月12日星期日,ArrayList常用的构造函数如下： ArrayList ()：构建一个空的ArrayList对象。 ArrayList (Collection c)：构建一个ArrayList对象，并且将集合c中所有元素添加进去。 ArrayList (int initialCapacity)：构建一个拥有特定容量的空ArrayList对象。 ArrayList的很多成员方法与LinkedList相似，两者的本质区别是一个使用顺序结构，另一个使用链表结构，因此，它也可以使用LinkedList类提供的方法进行列表的操作。 例9-5,9.4.2 ArrayList 类,22,2019年5月12日星期日,9.5 Iterator接口,通常希望依次访问类集中的元素。到目前为止，除了使用集合对象的get()方法可以实现对集合中的元素的遍历外,处理这个问题的最简单方法是使用iterator， Iterator是一个或者实现Iterator或者实现ListIterator接口的对象。Iterator可以遍历类集中的元素，从而获得或删除元素。 ListIterator扩展Iterator，允许双向遍历列表，并可以修改。,23,2019年5月12日星期日,Iterator接口的主要方法,24,2019年5月12日星期日,Iterator迭代器只能前向循环，如果需要双向遍历，则可以使用更高级的ListIterator迭代器，ListIterator接口继承自Iterator接口。 ListIterator迭代器除了有next()方法外，还新增了hasprevious()方法和previous()方法，实现前向遍历。ListIterator还可以定位当前的索引位置，调用nextIndex()和previousIndex()就可以实现。,ListIterator迭代器,25,2019年5月12日星期日,ListIterator接口的主要方法,26,2019年5月12日星期日,Iterator使用,ArrayList al = new ArrayList(); Iterator itr = al.iterator(); while (itr.hasNext() Object element = itr.next(); System.out.print(element + “ “); 详细例9-6,使用Iterator的一般步骤： 调用集合对象的Iterator()方法得到一个指向集合序列第一个元素的迭代器； 设置一个调用hasNext()方法的循环，序列中是否还有元素。如果集合中还有元素，hasNext()返回true; 在循环中，使用next()方法获得集合序列中的下一个元素； 如果需要删除元素，可remove()方法将迭代器所返回的元素删除。Remove()方法删除next()方法最后一次从集合中访问的元素。,27,2019年5月12日星期日,9.6 Map及HashMap接口,1. Map 接口 Map中每项都是成对出现的，它提供了一组键值的映射即一个存储关键字和值的关联或者说是关键字/值对的对象。 存储的每个对象都有一个相应的关键字(key)，关键字决定了对象在Map中的存储位置。 给定一个关键字，可以得到它的值。关键字和值都是对象，每一对关键字/值，叫做一项。 关键字应该是唯一的，但值是可以被重复的,且每个key 只能映射一个value。 用put(Object key，Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。 有些映射可以接收null关键字和null值。而有的则不行,28,2019年5月12日星期日,Map接口的主要方法,29,2019年5月12日星期日,Map接口的一个抽象类是AbstractMap。 在这个抽象类中，部分地实现了Map接口中的成员方法，使得具体的映射类不必实现Map接口中的每个成员方法。 AstractMap抽象类有三个子类： TreeMap HashMap WeakHashMap：,AstractMap抽象类,30,2019年5月12日星期日,(1) TreeMap描述了一个按键值升序排列的映射,它有一些扩展的方法，如firstKey()，lastKey()等，还可以从TreeMap中指定一个范围以取得其子Map。 (2) HashMap描述的一个映射中允许存储空对象，由于键必须唯一，所以只能有一个空键值。 (3)WeakHashMap是一种改进的HashMap，它描述了一个映射，当集合中的某些内容不再使用时需清除掉无用的数据，并使用垃圾回收机制进行回收。,AstractMap抽象类,31,2019年5月12日星期日,HashMap类使用散列表实现Map接口 HashMap通过哈希运算可以快速查找一个键，因此在适合于在Map中插入、删除和定位元素。如果要按照自然顺序或者自定义顺序遍历关键字，TreeMap会更好些。,2HashMap,32,2019年5月12日星期日,由于HashMap实现了Map接口，因此它没有自己的新方法。HashMap的构造方法如下： HashMap()：创建一个空的HashMap集合。 HashMap(Map t)：创建一个哈希集，将t中所有元素添加进去。 HashMap(int initialCapacity)：创建一个拥有特定容量的空HashMap集合。 HashMap(int initialCapacity，float loadFactor)：创建一个拥有特定容量和加载因子的空HashMap。,33,2019年5月12日星期日,散列表中的容量是指能够存储对象的数量。当对象存储的数目到达容量乘以加载因子的值时，容量将会自动地增加到原容量的2倍加1，加1的目的是确保散列表的容量为质数或奇数。 例如: HashMap aMap=new HashMap(151,0.6f); 则 aMap对象最初的容量为151，当存储对象的数量达到91时，容量将会自动增加到303。,34,2019年5月12日星期日,HashMap类的主要成员方法,35,2019年5月12日星期日,例：HashMap hm = new HashMap / 把元素加入映射 hm.put(“John“, new Integer(96); hm.put(“Tom“, new Integer(97); hm.put(“Jane“, new Integer(98); 例9-7,36,2019年5月12日星期日,3. TreeMap 类,TreeMap类通过使用树实现Map接口。 允许快速检索。应该注意的是，不像散列映射，树映射保证它的元素按照关键字升序排序。 下面的TreeMap构造函数定义为： TreeMap( ) TreeMap(Comparator comp) TreeMap(Map m) TreeMap(SortedMap sm),37,2019年5月12日星期日,TreeMap的使用,TreeMap tm = new TreeMap(); / 放入元素 tm.put(“E“, new Double(3444.44); tm.put(“A“, new Double(3444.34); tm.put(“B“, new Double(124.22); tm.put(“C“, new Double(1338.00); Iterator i = set.iterator(); while (i.hasNext() String key = i.next(); System.out.println(key + “: “ + tm.get(key).doubleValue(); ,38,2019年5月12日星期日,Vector（向量）是Java.util包提供的工具类，是类似数组的一种顺序存储的数据结构。它允许将不同类型的元素存储在一个向量中，而且元素的个数可变，因此Vector 类提供了实现可增长数组的功能，以适应创建 Vector对象后进行添加或删除的操作，使得应用程序的操作方式变得更加方便、灵活。,9.7 Vector 类,39,2019年5月12日星期日,Vector类适合在如下情况中使用： 需要处理的对象数目不确定，序列中的元素都是对象或者可以表示为对象。 需要将不同类的对象组合成一个数据序列 需要在对象序列中频繁地插入和删除 需要经常定位元素或者进行其他查询操作 在不同类之间传递大量数据。,40,2019年5月12日星期日,1. 创建Vector类的对象,Vector类有如下4个构造函数： public Vector()：创建最多允许存放10个元素的向量，每次扩展向量元素的数目为原向量元素数目的一倍。 public Vector(int initialCapacity)：创建最多允许存放initialCapacity个元素的向量，每次扩展向量元素的数目为原向量元素数目的一倍。,41,2019年5月12日星期日,public Vector(int initialCapacity,int capacityIncrement)：创建最多允许存放initialCapacity个元素的向量，每次扩展向量元素的数目为capacityIncrement。 public Vector(Collection c)： 创建最多允许比参数带入的集合c的元素数目多10%的向量，每次扩展向量元素的数目为原向量元素数目的一倍。,42,2019年5月12日星期日,其中，initialCapacity表示刚创建时Vector序列包含的元素数目；capacityIncrement 表示向Vector序列中追加元素时每次增加的个数。 下面是几个创建向量对象的例子。 Vector vectorObject1=new Vector(); Vector vectorObject2=new Vector(200); Vector vectorObject3=new Vector(200，15); 在使用Vector时，需要特别注意的是先创建后使用，否则容易造成溢出或者空指针异常,43,2019年5月12日星期日,Vector类的主要成员方法(1),44,2019年5月12日星期日,Vector类的主要成员方法(2),例9-8,45,2019年5月12日星期日,9.8 Stack类,在Java语言中，Stack类是java.util包中专门用来实现栈的工具类。Stack类继承自Vector类，因此它是Vector的一个子类，实现了一个后进先出的堆栈。 Stack类继承了Vector类的所有方法，还新增了一些方法使得Vector类能够实现堆栈的操作。,46,2019年5月12日星期日,1、创建Stack类对象 public Stack()；它建立一个空的堆栈 2、压栈与出栈操作 public Object push(Object item)：将指定的对象压入栈 public Object pop()：将栈顶的对象从栈中取出 3、检查栈是否为空 public boolean empty()：测试堆栈是否为空，若堆栈中没有对象元素，则返回true，否则返回false 4、查看栈顶端的数据，但不删除该数据。 public object peek() 5、获取数据在堆栈中的位置。最顶端的位置是1，向下依次增加。如果堆栈不含有此数据，则返回-1。 public search(Object data),例9-9,47,2019年5月12日星期日,泛型是JDK 1.5以上版本的新特性，泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。这种参数类型可以用在类、接口和方法的创建中，分别称为泛型类、泛型接口和泛型方法。 它在使用集合时，提供了一种编译时类型安全检查功能，并能减少类型强制转化的麻烦。 当你从一个集合中取出一个元素时，例如使用Iterator接口中的next()方法，其返回值的类型是Object，在使用这个元素时，需要把返回值转换为元素本身的类型。这种类型转化是不安全的。 这种转换是要求开发者对实际参数类型可以预知的情况下进行的。对于强制类型转换错误的情况，编译器可能不提示错误，但在运行的时候可能会出现异常，这是一个安全隐患。泛型的引入很好地解决了这一问题,9.9 泛型程序设计,48,2019年5月12日星期日,泛型类的定义,泛型类的定义: class java_genericsT 里边的T的类型可以是任意的，由实际对象的类型决定。而在使用泛型类时，通过内的参数指定参数类型。,49,2019年5月12日星期日,未使用泛化的代码,ArrayList a=new ArrayList(); a.add(new Integer(1); a.add(new Integer(2); for(Iterator i=a.