泛型和集合框架

泛型和集合框架12.1泛型泛型（Generics）是在JDK1.5中推出的，其主要目的是可以建立具有类型安全的集合框架，如链表、散列映射等数据结构

泛型的目的Java泛型的主要目的是可以建立具有类型安全的数据结构，如链表、散列表等数据结构，最重要的一个优点就是：在使用这些泛型类建立的数据结构时，不必进行强制类型转换，即不要求进行运行时类型检查。JDK1.5是支持泛型的编译器，它将运行时的类型检查提前到编译时执行，使代码更安全。12.1.1泛型类可以使用“class名称<泛型列表>”声明一个类，为了和普通的类有所区别，这样声明的类称作泛型类，如：

classShowObject<E>E是其中的泛型，也就是并没有指定E是何种类型泛型类的类体和和普通类的类体完全类似，由成员变量和方法构成举例 publicclassShowObject<E>{ publicshowMess(Eb){ Stringmess=b.toString(); System.out.println(mess); } }12.1.2泛型类声明对象和普通的类相比，泛型类声明和创建对象时，类名后多了一对“<>”，而且必须要用具体的类型替换“<>”中的泛型。Dog.java

publicclassDog{publicStringtoString(){return}}Cat.java

publicclassCat{publicStringtoString(){return"一只小花猫";}}publicclassExample12_1{publicstaticvoidmain(Stringargs[]){ShowObject<Dog>showDog=newShowObject<Dog>();showDog.showMess(newDog());ShowObject<Cat>showCat=newShowObject<Cat>();showCat.showMess(newCat());}}说明泛型类中的泛型变量只能调用Object类中的方法，因此Cat和Dog类都重写了Object类的toString()方法。12.1.3泛型接口可以使用“interface名称<泛型列表>”声明一个接口，这样声名的接口称作泛型接口如

interfaceListen<E>{voidlisten(Ex);}注：普通类实现泛型接口时，必须指定泛型接口中泛型列表中的具体类型例12-2interfaceListen<E>{voidlisten(Ex);}classStudentimplementsListen<Piano>{publicvoidlisten(Pianop){p.play();}}classTeacherimplementsListen<Violin>{publicvoidlisten(Violinv){v.play();}}classPiano{publicvoidplay(){System.out.println("钢琴协奏曲:黄河");}}classViolin{publicvoidplay(){System.out.println("小提琴协奏曲:梁祝");}}publicclassExample12_2{publicstaticvoidmain(Stringargs[]){Studentzhang=newStudent();System.out.println("学生听:");zhang.listen(newPiano());Teacherteacher=newTeacher();System.out.println("老师听:");teacher.listen(newViolin());}}Java集合框架在Java语言中，设计者对常用的数据结构和算法做了一些规范（接口）和实现（具体实现接口的类）。所有抽象出来的数据结构和算法统称为Java集合框架Java程序员在具体应用时，不必考虑数据结构和算法实现细节，只需要用这些类创建出来的一些对象，然后直接应用就可以了，提高了编程效率Java容器类容器类可以大大提高编程效率和编程能力Java2容器类类库的用途是“保存对象”，它分为两类：Collection----一组独立的元素，通常这些元素都服从某种规则。List必须保持元素特定的顺序，而Set不能有重复元素。Map----一组成对的“键值对”对象，即其元素是成对的对象集合框架的层次结构说明Collection是集合接口，集合框架的根,代表一组ObjectSet子接口：里面的元素不允许重复List子接口：里面的元素可以重复说明Set和List对比：Set：检索元素效率低下，删除和插入效率高。插入和删除不会引起元素位置改变List：和数组类似，List可以动态增长，查找元素效率高。说明Set的子类：

HashSet以哈希表的形式存放元素，插入删除速度很快TreeSet保持次序的Set，底层为树结构。使用它可以从Set中提取有序的序列。List的子类：

ArrayList：动态数组（顺序结构）

LinkedList：链表（链式结构）12.2链表链表是由若干个称作节点的对象组成的一种数据结构，每个节点含有一个数据和下一个节点的引用，或含有一个数据并含有上一个节点的引用和下一个节点的引用数据引用引用数据null引用数据引用引用数据引用

null图12.3双链表示意图12.2.1LinkedList<E>泛型类java.util包中的LinkedList<E>泛型类创建的对象以链表结构存储数据，习惯上称LinkedList类创建的对象为链表对象。例如，LinkedList<String>list=newLinkedList<String>();创建一个空双链表。使用LinkedList<E>泛型类声明创建链表时，必须要指定E的具体类型，然后链表就可以使用add(Eobj)方法向链表依次增加节点举例list.add(“你好”);list.add(“十一快乐”);list.add(“注意休息”);此时，链表里有3个节点，节点自动链接在一起12.2.2常用方法以下是LinkedList<E>泛型类实现Lis<E>泛型接口中的一些常用方法。publicbooleanadd(Eelement)publicvoidadd(intindex,Eelement)publicvoidclear()publicEremove(intindex)publicbooleanremove(Eelement)publicEget(intindex)publicintindexOf(Eelement)publicintlastIndexOf(Eelement)publicEset(intindex,Eelement)publicintsize()publicbooleancontains(Objectelement)以下是LinkedList<E>泛型类本身新增加的一些常用方法publicvoidaddFirst(Eelement)publicvoidaddLast(Eelement)publicEgetFirst()publicEgetLast()publicEremoveFirst()publicEremoveLast()publicObjectclone()12.2.3遍历链表当用户需要遍历集合中的对象时，应当使用该集合提供的迭代器，而不是让集合本身来遍历其中的对象。由于迭代器遍历集合的方法在找到集合中的一个对象的同时，也得到待遍历的后继对象的引用，因此迭代器可以快速地遍历集合。什么是迭代器迭代器是一个实现了Iterator接口的类的对象所有实现了Collection接口的类都有一个名称为iterator（）的方法来获取迭代器链表对象可以使用iterator()方法获取一个Iterator对象，该对象就是针对当前链表的迭代器next方法：返回迭代器中的一个元素hasNext方法：如果容器里还有元素，则为true例12-3importjava.util.*;publicclassExample12_3{publicstaticvoidmain(Stringargs[]){List<String>list=newLinkedList<String>();list.add("大家好");list.add("国庆60周年");list.add("十一快乐");Iterator<String>iter=list.iterator();while(iter.hasNext()){Stringte=iter.next();System.out.print(te+"");}System.out.println("");longendTime=System.currentTimeMillis();for(inti=0;i<list.size();i++){Stringte=list.get(i);System.out.print(te+"");}}}JDK1.5之前没有泛型的LinkedList类，可以用普通的LinkedList创建一个链表对象，如LinkedListmylist=newLinkedList();然后mylist链表可以使用add(Objectobj)方法向这个链表依次添加节点。由于任何类都是Object类的子类，因此可以把任何一个对象作为链表节点中的对象使用集合框架注意事项（没有使用泛型）ObjectObjectObject加入集合从集合中取出(Rabbit)object(Car)object(Student)objectRabbitCarStudentRabbitCarStudent任何对象加入集合类后，自动转变为Object类型；取出时，需要进行强制类型转换，恢复为特定的类型例12-4使用了JDK1.5版本之前的LinkedList12.2.4排序与查找如果链表中的数据是实现了Comparable接口的类的实例，比如String对象，那么Java.util包中的Collections类调用sort(List<E>list)方法可以对参数指定的列表进行排序，即按节点中的存储的对象的大小升序排列节点。Collections类注意区分和Collection接口的的区别Collections是一个类，该类里的方法都是静态的方法，主要是用来对集合的操作的。是个非常有用的类String类实现了泛型接口Comparable<E>中的compareTo(Eb)方法，使得字符串可以按字典序比较大小，如果一个链表list如下添加节点：list.add("bird");list.add("apple");list.add("cat");那么用sort方法排序list：Collection.sort(list);之后，list中三个节点中的数据将依次是apple，bird和cat。如何比较两个对象一个类可以实现泛型接口Comparable<E>中的comareTo(Eb)方法来指定该类实例互相比较大小关系的准则，实现Comparable<E>接口类创建的对象可以调用compareTo(Eb)方法和参数指定的对象比较大小关系。假如a和b是实现Comparable<E>接口类创建的两个对象，当apareTo(b)<0称a小于b，apareTo(b)>0时，称a大于b，apareTo(b)==0，时，称a等于b。如何查找一个对象当链表节点中的对象是实现泛型接口Comparable<E>的类的实例时，就可以使用sort方法对链表进行排序操作。有时需要查找链表中是否含有和指定数据相等的数据，那么首先要对链表排序，然后使用Collections类里的publicstaticintbinarySearch(List<T>list,Tkey)查找链表中是否含有和数据key相等的数据12-512.2.5洗牌与旋转Collections类还提供了将链表中的数据重新随机排列的类方法以及旋转链表中数据的类方法，方法的详细解释如下publicstaticvoidshuffle(List<E>list)：随机排列list中的节点。staticvoidrotate(List<E>list,intdistance)：旋转链表中的节点，调用该方法后，list索引为i的节点中的数据将是调用该方法前索引为(i-distance)modlist.size()的节点中的数据。例如，假设list节点数据依次为：abcde，那么执行Collections.rotate(list,1)之后，list节点数据依次为eabcd。当方法的参数distance取正值时，向右转动list中的数据，取负值时向左转动list中的数据。图12.6洗牌与旋转publicstaticvoidreverse(List<E>list)：翻转list中的数据。假设list节点中的数据依次为：abcde，那么在Collections.reverse(list)之后，list节点中的数据依次为edcba。12-6，12-712-7：若干个人围成一圈，从某个人开始顺时针数到第3个人，该人丛圈中退出，然后继续顺时针数到第3个人，该人从圈中退出，依次类推，程序输出圈中最后剩下的人12.3堆栈堆栈是一种“后进先出”的数据结构使用java.util包中的Stack<E>泛型类创建一个堆栈对象，堆栈对象可以使用publicEpush(Eitem);实现压栈操作。使用publicEpop();实现出栈操作。使用publicbooleanempty();判断堆栈是否还有数据，有数据返回false，否则返回true。使用publicEpeek();获取堆栈顶端的数据，但不删除该数据。使用publicintsearch(Objectdata);获取数据在堆栈中的位置，最顶端的位置是１，向下依次增加，如果堆栈不含此数据，则返回-1。12-8Fibonacci数列，用栈实现12.4散列映射:HashMap关于Map:实现Map接口的对象会将键（Key)映射至值（Value）值指的是要存入容器的对象。在将对象存入Map对象时，需要同时给定一个键，要取回对象时可以指定，这样就可以取得与键对应的对象值。Map中每一个键都是唯一的，不能有重复的键。Map拥有自己的排序机制Map继承关系MapSortedMapHashtableLinkedHashMapHashMapTreeMap12.4.1HashMap<K,V>泛型类HashMap<K,V>泛型类实现了泛型接口Map<K,V>，HashMap<K,V>类中的绝大部分方法都是Map<K,V>接口方法的实现。编程时，可以使用接口回调技术，即把HashMap<K,V>对象的引用赋值给Map<K,V>接口变量，那么接口变量就可以调用类实现的接口方法HashMap<K,V>对象采用散列表这种数据结构存储数据，习惯上称HashMap<K,V>对象为散列映射或哈希映射。散列映射用于存储“键/值”对，允许把任何数量的“键/值”对存储在一起。键不可以发生逻辑冲突，即不要两个数据项使用相同的键，如果出现两个数据项对应相同的键，那么，先前散列映射中的“键/值”对将被替换HashMap中常用方法publicVput(Kkey,Vvalue)该方法将键值对对象存放到映射中publicVget(Objectkey)返回散列映射中使用key做键的“键/值”对中的值importjava.util.*;publicclassHashMapDemo{ publicstaticvoidmain(String[]args) { Map<String,String>map1=newHashMap<String,String>(); Stringkey1="book"; Stringkey2="apple"; map1.put(key1,"书"); map1.put(key2,"苹果"); System.out.println(map1.get(key1)); System.out.println(map1.get(key2)); }}HashMap中常用方法publicvoidclear()清空散列映射。publicObjectclone()返回当前散列映射的一个克隆。publicbooleancontainsKey(Objectkey)如果散列映射有“键/值”对使用了参数指定的键，方法返回true，否则返回false。publicbooleancontainsValue(Objectvalue)如果散列映射有“键/值”对的值是参数指定的值，方法返回true，否则返回false。publicbooleanisEmpty()如果散列映射不含任何“键/值”对，方法返回true，否则返回false。publicVremove(Objectkey)删除散列映射中键为参数指定的“键/值”对，并返回键对应的值。publicintsize()返回散列映射的大小，即散列映射中“键/值”对的数目。12.4.3遍历散列映射HashMap类里：publicCollection<V>values()方法返回一个实现Collection<V>接口类创建的对象，其中包括所有值对象。可以使用接口回调技术，即将该对象的引用赋给Collection<V>接口变量，该接口变量可以回调iterator()方法获取一个Iterator对象，这个Iterator对象存放着散列映射中所有“键/值”对中的“值”

importjava.util.*;publicclassHashMapDemo{ publicstaticvoidmain(String[]args) { Map<String,String>map1=newHashMap<String,String>(); map1.put("book","书"); map1.put("apple","苹果"); map1.put("Language","语言"); Collectionc1=map1.values(); Iteratorit1=c1.iterator(); while(it1.hasNext()) System.out.println(it1.next()); System.out.println(); for(Strings:map1.values()) System.out.println(s); }}思考（1）输出的次序并不是按当初加入的次序输出的（2）如果想要在迭代所有的对象时，依照插入的顺序来排列，则可以使用LinkedHashMap，它是HashMap的子类。（3）只要是实现Collection接口的对象，都可以使用增强的for循环功能来迭代所有的值12.4.3基于散列映射的查询对于经常需要进行查找的数据可以采用散列映射来存储这样的数据，即为数据指定一个查找它的关键字，然后按着“健-值”对，将关键字和数据一并存入散列映射中例12-9英语单词查询的应用程序12.5树集12.5.1TreeSet<E>泛型类TreeSet<E>类是实现Set接口和SortedSet接口的类SortedSet提供的方法让你有序得取出对应位置的对象。TreeSet<E>类创建的对象称作树集。树集树集采用树结构存储数据，树节点中的数据会按存放的数据的“大小”顺序一层一层地依次排列，在同一层中的节点从左到右按字从小大递增排列，下一层的都比上一层的小应用importjava.util.*;publicclassTreeSetDemo1{ publicstaticvoidmain(String[]args) { Set<String>set1=newTreeSet<String>(); set1.add("book"); set1.add("boy"); set1.add("apple"); set1.add("zoo"); for(Stringname:set1) System.out.println(name); }}说明由于加入的String对象，执行结果会自动按照字典顺序进行排列。依照字典顺序来排列String对象是TreeSet默认的12.5.2节点的大小关系当一个树集中的数据是实现Comparable<E>泛型接口类创建的对象时，节点就按对象的大小关系顺序排列12.5.3TreeSet类的常用方法publicbooleanadd(Eo)向树集添加加节点，节点中的数据由参数指定，添加成功返回true，否则返回false。publicvoidcl