第七讲容器和泛型

第7讲

容器与泛型容器容器是用于存储并操作多个元素的对象一个容器框架通常包括一组接口抽象的数据类型允许对容器以独立于具体实现的统一方式进行操作具体实现采用不同的数据结构对接口的具体实现算法一组有用的算法，如查找、排序算法针对通用接口Java容器类位于java.util包中用于保存对象封装了众多的数据结构和算法JAVA中的部分容器类图Collection:独立元素的序列List：按照插入的顺序保存元素

ArrayList:以动态数组的方式实现，适用于随机访问，但插入删除代价较高

LinkedList：以链表方式实现，插入删除代价低，但不适合随机访问Set：不能有重复元素

HashSet:基于散列技术的实现，元素的顺序与插入顺序不一致

TreeSet:基于红黑树的实现，元素的顺序与大小相关

LinkedHashSet:采用了散列，但同时维护了元素的插入顺序Queue：按排队规则确定顺序

LinkedList:先进先出队列

PriorityQueue:优先队列Map:一组成对的“键-值”对象

HashMap:键值按散列技术排序

TreeMap：键值按元素的大小排序

LinkedHashMap：维护了键值的插入顺序Collection接口publicinterfaceCollection<E>extendsIterable<E>{intsize();booleanisEmpty();booleancontains(Objectelement);booleanadd(Eelement);booleanremove(Objectelement);Iterator<E>iterator();booleancontainsAll(Collection<?>c);booleanaddAll(Collection<?extendsE>c);booleanremoveAll(Collection<?>c);booleanretainAll(Collection<?>c);voidclear();Object[]toArray();<T>T[]toArray(T[]a);}List接口元素访问Eget(intindex);Eset(intindex,Eelement);boolean

add(Eelement);boolean

add(intindex,Eelement);Eremove(intindex);boolean

addAll(intindex,Collection<?ExtendsE>c);查找

int

indexOf(Objecto);

int

lastIndexOf(Objecto);遍历

ListIterator<E>listIterator();

ListIterator<E>listIterator(intindex);Range-ViewList<E>subList(intfromintto);List实现类ArrayListLinkedListVector(deprecated)importjava.util.*;publicclassListPerformance{publicstaticvoidmain(String[]args){Collection<Integer>c=newHashSet<Integer>();c.add(1);c.add(2);List<Integer>list1=newArrayList<Integer>(c);List<Integer>list2=newLinkedList<Integer>(c);

/**比较在表头插入元素的时间*/longt1=System.nanoTime();for(inti=0;i<100000;i++)list1.add(2,i);System.out.println(System.nanoTime()-t1);t1=System.nanoTime();for(inti=0;i<100000;i++)list2.add(2,i);System.out.println(System.nanoTime()-t1);

/*比较访问一个元素的时间*/Randomrand=newRandom();inttmp;t1=System.nanoTime();for(inti=0;i<100000;i++) tmp=list1.get(rand.nextInt(list1.size()));System.out.println(System.nanoTime()-t1);t1=System.nanoTime();for(inti=0;i<100000;i++) tmp=list2.get(rand.nextInt(list2.size()));System.out.println(System.nanoTime()-t1);}}374213141631015625960258213795528821ArrayList和LinkedList性能比较Set接口

intsize();booleanisEmpty();booleancontains(Objectelement);booleanadd(Eelement);booleanremove(Objectelement);Iterator<E>iterator();booleancontainsAll(Collection<?>c);booleanaddAll(Collection<?ExtendsE>c);booleanremoveAll(Collection<?>c);booleanretainAll(Collection<?>c);voidclear();Object[]toArray();T[]toArray(T[]a);Set实现类HashSet

基于hash方法的实现插入的元素不保持顺序TreeSet

要求被加入对象可比较基本类型实现Comparable接口向TreeSet的构造函数显式传入一个Comparator对象，用于比较被加入对象LinkedHashSet

基于hash方法的实现但保持元素插入的顺序importjava.util.*;publicclassSetOperations{ publicstaticvoidmain(String[]args){ Collection<Integer>c=newArrayList<Integer>(); c.add(43); c.add(34); c.add(34); c.add(28); c.add(56); c.add(56); c.add(17); Set<Integer>s1=newHashSet<Integer>(); Set<Integer>s2=newTreeSet<Integer>(); Set<Integer>s3=newLinkedHashSet<Integer>(); s1.addAll(c); s2.addAll(c); s3.addAll(c); System.out.println(c); System.out.println(s1); System.out.println(s2); System.out.println(s3); }}输出：[43,34,34,28,56,56,17][17,34,43,56,28][17,28,34,43,56][43,34,28,56,17]importjava.util.*;classPerson{ Stringname; intsalary; publicPerson(Stringname,intsalary){=name;this.salary=salary;} publicStringtoString(){ return"Name="+name+",Salary="+salary; }}publicclassTreeSetTest1{ publicstaticvoidmain(String[]args){ Personp1=newPerson("Tom",1000); Personp2=newPerson("Bob",2000); Personp3=newPerson("Alice",3000); Set<Person>persons=newTreeSet<Person>(); persons.add(p1);

persons.add(p2);

//

运行时会报错，因为无法比较对象大小 persons.add(p3); System.out.println(persons); }}Exceptioninthread"main"java.lang.ClassCastException:.njnu.cs.abyssoop.ch11.Personcannotbecasttojava.lang.Comparableatjava.util.TreeMap.put(UnknownSource)atjava.util.TreeSet.add(UnknownSource)at.njnu.cs.abyssoop.ch11.TreeSetTest2.main(TreeSetTest1.java:19)importjava.util.*;classPersonimplementsComparable{//方法一：为需要排序的类实现Comparable接口 Stringname; intsalary; publicPerson(Stringname,intsalary){=name;this.salary=salary;} publicintcompareTo(Objectobj){ Personp=(Person)obj; returnpareTo(); } publicStringtoString(){ return"Name="+name+",Salary="+salary; }}publicclassTreeSetTest2{ publicstaticvoidmain(String[]args){ Set<Person>persons=newTreeSet<Person>(); Personp1=newPerson("Tom",1000); Personp2=newPerson("Bob",2000); Personp3=newPerson("Alice",1500); persons.add(p1); persons.add(p2); persons.add(p3); System.out.println(persons); }}[Name=Alice,Salary=1500,Name=Bob,Salary=2000,Name=Tom,Salary=1000]importjava.util.*;publicclassTreeSetTest3{publicstaticvoidmain(String[]args){ Personp1=newPerson("Tom",1000); Personp2=newPerson("Bob",2000); Personp3=newPerson("Alice",3000); Set<Person>persons1=newTreeSet<Person>(

newComparator<Person>(){//方法二：向TreeSet构造函数传入//Comparator对象，用于比较两个待排序的对象； publicintcompare(Personp1,Personp2){ returnpareTo(); } }); persons1.add(p1); persons1.add(p2); persons1.add(p3); Set<Person>persons2=newTreeSet<Person>( newComparator<Person>(){//另一种对Person排序的方法 publicintcompare(Personp1,Personp2){ return(p1.salary==p2.salary)?0:(p1.salary>p2.salary?1:-1); } }); persons2.add(p1); persons2.add(p2); persons2.add(p3); System.out.println(persons1); System.out.println(persons2);}}[Name=Alice,Salary=3000,Name=Bob,Salary=2000,Name=Tom,Salary=1000][Name=Tom,Salary=1000,Name=Bob,Salary=2000,Name=Alice,Salary=3000]Queue接口方法

boolean

offer(Eo):将给定元素插入队列Eremove()：获得并删除队列头元素,如果队列为空，则抛出异常Epoll():获取并删除队列头元素，如果队列为空，则返回null.Eelement():获取但不删除队列头元素，如果队列头为空，则抛出异常Epeek():获取但不删除队列头元素，如果队列为空，则返回null实现类

LinkedList

PriorityQueue要求加入的对象可比较importjava.util.*;publicclassQueueTest1{ publicstaticvoidprintQ(Queue<Integer>queue){ while(queue.peek()!=null) System.out.print(queue.remove()+""); System.out.println(); } publicstaticvoidmain(String[]args){

Queue<Integer>queue=newLinkedList<Integer>();//LinkedList是一种

//先进先出对列； Randomrand=newRandom(); for(inti=0;i<10;i++) queue.offer(rand.nextInt(i+10)); printQ(queue);queue=newPriorityQueue<Integer>();//PriorityQueue是优先队列； for(inti=0;i<10;i++) queue.offer(rand.nextInt(i+10)); printQ(queue); }}8585691421632566788111212Stack类方法

booleanempty():测试堆栈是否为空

Epeek():查看栈顶元素而不移除它，若堆栈为空，则抛出EmptyStackException异常Epop():移除栈顶元素并作为此函数的值返回该对象，若堆栈为空，则抛出EmptyStackException异常

Epush(Eitem):把项压入栈顶

int

search(Objecto):返回对象在栈中的位置，以1为基数Map接口public

interfaceMap<K,V>{Vput(Kkey,Vvalue);Vget(Objectkey);Vremove(Objectkey);

booleancontainsKey(Objectkey);

booleancontainsValue(Objectvalue);

intsize();

booleanisEmpty();

voidputAll(Map<?extendsK,?extendsV>m);

voidclear();

publicSet<K>keySet();

publicCollection<V>values();

publicSet<Map.Entry<K,V>>entrySet();public

interfaceEntry{KgetKey();VgetValue();VsetValue(Vvalue);}}Map实现类HashMapTreeMapLinkedHashMapitem2=Jordon；item4=Alice；item1=Tom；item3=Bob；item5=Green；item1=Tom；item2=Jordon；item3=Bob；item4=Alice；item5=Green；item4=Alice；item3=Bob；item1=Tom；item2=Jordon；item5=Green；/*不同的Map的行为*/importjava.util.*;publicclassMapTest1{publicstaticvoidmain(String[]args){ Map[]maps={newHashMap(),newTreeMap(),newLinkedHashMap()}; for(inti=0;i<maps.length;i++){ maps[i].put("item4","Alice"); maps[i].put("item3","Bob"); maps[i].put("item1","Tom"); maps[i].put("item2","Jordon"); maps[i].put("item5","Green"); } for(inti=0;i<maps.length;i++){ Iteratoriter=maps[i].keySet().iterator(); while(iter.hasNext()){ Stringkey=(String)iter.next(); Stringvalue=(String)maps[i].get(key); System.out.print(key+"="+value+";"); } System.out.println(); }}}Collection的公共方法add(E)addAll(collection<?ExtendsE>)remove(Object)removeAll(Collection<?>)contains(Object)iterator()containsAll(Collection<?>)retainAll(Collection<?>)Size()toArray()contains方法的实现语义List基于equals()方法HashSet同时基于hashCode()和equals()方法TreeSet基于compareTo()结果importjava.util.*;classPersonimplementsComparable{Stringname;intage;publicPerson(Stringname,intage){=name;this.age=age;}

/*equals()方法影响List和HashSet的contains()方法；包括HashMap的键的比较*/publicbooleanequals(Objecto){if(!(oinstanceofPerson))returnfalse;Personp=(Person)o;returnname.equals()&&age==p.age;}/*hashCode()方法是基于HASH的HashMap和HashSet用于产生HASH值的基本方法*/publicinthashCode(){return(name+age).hashCode();}/*compareTo()方法是TreeSet的contains()方法比较对象是否相等的依据*/publicintcompareTo(Objectobj){Personp=(Person)obj;if(pareTo()>0)returnpareTo();else return(age>p.age)?1:(age==p.age?0:-1);}}publicclassContainsTest{publicstaticvoidmain(String[]args){Personp1=newPerson("Alice",21);Personp2=newPerson("Bob",22);Personp3=newPerson("Bob",22);Collection<Person>c1=newArrayList<Person>();c1.add(p1);c1.add(p2);System.out.println(c1.contains(p2));System.out.println(c1.contains(p3));Collection<Person>c2=newHashSet<Person>();c2.add(p1);c2.add(p2);

System.out.println(c2.contains(p3));

Collection<Person>c3=newTreeSet<Person>();c3.add(p1);c3.add(p2);

System.out.println(c3.contains(p3));

Map<Person,String>map=newHashMap<Person,String>();map.put(p1,"Alice");map.put(p2,"Bob");map.put(p3,"Bob");

System.out.println(map);}}truetruetruetrue{Person@2cb6949f=Alice,Person@3d5fa95=Bob}迭代器Iterator用于遍历任何Collection容器的对象publiciterator()返回Iterator对象Iterator的方法

hasNext()方法检测序列中是否还有元素next()方法返回下一个元素remove()方法将迭代器新近返回的元素删除/*采用迭代器遍历容器的元素*/importjava.util.*;publicclassCollectionTest{ publicstaticvoidmain(String[]args) { Collection<String>coll=newArrayList<String>(); coll.add("Hi,Tom!"); coll.addAll(Arrays.asList("WelcometoJava!".split(""))); Iterator<String>iter=coll.iterator(); while(iter.hasNext()){ System.out.println(iter.next()); } }}输出：Hi,Tom!WelcomeToJava!foreach语法用于遍历数组、集合等元素，是for语句的特殊版本语法：for(Tval:objs){…}应用场合数组publicstaticvoidmain(String[]args){

for(String

arg:args){

System.out.println(arg);}}容器(实现了Iterable接口)Collection<String>col=newArrayList<String>();for(String

str:col)

System.out.println(str);任何实现了Iterable接口的对象Iterable接口包含一个方法Iterator

iterator();importjava.util.*;publicclassIterableClassimplementsIterable<String>{//实现Iterable接口protectedString[]words=("Andthatishow"+"weknowtheEarthtobebanana-shapped.").split("");

publicIterator<String>iterator(){//Iterable接口需要实现的方法returnnewIterator<String>(){//采用匿名内部类生成一个Iterator对象 privateintindex=0;

publicbooleanhasNext(){ returnindex<words.length; } publicStringnext(){ returnwords[index++]; } publicvoidremove(){ thrownewUnsupportedOperationException(); }};}publicstaticvoidmain(String[]args){ for(Strings:newIterableClass())//可以使用foreach语法 System.out.print(s+""); System.out.println();}}Collections实用类包含一组作用于集合的实用静态方法/算法

addAll()fill()reverse()binarySearch()max()min()frequency()shuffle()sort()泛型泛型的概念泛型类/接口泛型方法泛型边界和类型擦除通配符泛型概念提高代码复用能力同一个类型定义、数据结构或算法等适用于许多种类型解耦类或方法所使用的类型之间的约束增强编译器类型检查功能泛型出现之前，容器类可以存放任何Object对象，由程序员负责将对象向下转型为具体的类，这种缺乏编译期检查的行为容易产生运行时错误importjava.util.*;classFruit{}classAppleextendsFruit{}classOrangeextendsFruit{}publicclassBeforeGenerics{publicstaticvoidmain(String[]args){ Listlist=newArrayList(); list.add(newApple()); list.add(newOrange()); Iteratoriter=list.iterator(); while(iter.hasNext()){ Appleapple=(Apple)iter.next();//运行时异常，编译期不出错

}}}问题：如果我们想执行严格的编译器检查，以使得容器只能存放特定的类型，该怎么办？泛型类/接口泛型语法

classname<T1,T2,…,Tn>{/*…*/}interfacename<T1,T2,…,Tn>{/*…*/}

类/接口定义后面加参数列表，用<>表示，参数列表可以有一个或多个public

classBox{

privateObjectobject;

public

voidset(Objectobject){

this.object=object;}

publicObjectget(){returnobject;}}/***GenericversionoftheBoxclass.*@param<T>thetypeofthevaluebeingboxed*/public

classBox<T>{//Tstandsfor"Type"

privateTt;

public

voidset(Tt){this.t=t;}

publicTget(){returnt;}}泛型类/接口实例化定义类型时用具体的类型实例化类型参数

Box<Integer>integerBox=newBox<Integer>();List<Apple>list1=newArrayList<Apple>();List<Orange>list2=newArrayList<Orange>();list1.add(newApple());

//list1.add(newOrange());//编译期错误，无法添加Orange对象至该容器public

interfacePair<K,V>{

publicKgetKey();

publicVgetValue();}public

classOrderedPair<K,V>implementsPair<K,V>{

privateKkey;

privateVvalue;

publicOrderedPair(Kkey,Vvalue){this.key=key;this.value=value;}

publicKgetKey(){returnkey;}

publicVgetValue(){returnvalue;}}Pair<String,Integer>p1=newOrderedPair<String,Integer>("Even",8);Pair<String,String>p2=newOrderedPair<String,String>("hello","world");同一份代码，可以用于处理不同类型的对象，并保持了编译器的类型检查的优点泛型的继承/实现与普通类的类继承和接口实现一样继承：extends实现：implementsclassTwoTuple<A,B>{publicfinalAfirst;publicfinalBsecond;publicTwoTuple(Aa,Bb){first=a;second=b;}publicStringtoString(){return"("+first+","+second+")";}}classThreeTuple<A,B,C>extendsTwoTuple<A,B>{//ThreeTuple继承自TwoTuplepublicfinalCthird;publicThreeTuple(Aa,Bb,Cc){super(a,b);third=c;}publicStringtoString(){return"("+first+","+second+","+third+")";}}publicclassTupleTest{publicstaticvoidmain(String[]args){TwoTuple<Integer,String>tuple1=newTwoTuple<Integer,String>(1,"TwoTuple");ThreeTuple<Boolean,Double,String>tuple2=newThreeTuple<Boolean,Double,String>(true,1.34,"ThreeTuple");System.out.println(tuple1);System.out.println(tuple2);}}(1,TwoTuple)(true,1.34,ThreeTuple)泛型类继承示例Java.util中的泛型类继承和实现例子publicinterfaceIterable<E>{…}publicinterfaceCollection<E>extendsIterable<E>{…}publicinterfaceList<E>extendsCollection<E>{…}publicabstractclassAbstractCollection<E>implementsCollection<E>{…}publicabstractclassAbstractList<E>extendsAbstractCollection<E>implementsList<E>{…}publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{…}interfaceGenerator<T>{Tnext();}//泛型接口；publicclassFibonacciimplementsGenerator<Integer>{//用实际类型实例化后的具体接口privateintcount=0;

publicIntegernext(){returnfib(count++);}//Generator<Integer>接口需要实现的方法privateintfib(intn){if(n<2)return1;returnfib(n-1)+fib(n-2);}publicstaticvoidmain(String[]args){Fibonaccigen=newFibonacci();for(inti=0;i<18;i++)System.out.println(gen.next()+"");}}泛型方法语法：将泛型参数列表置于返回值之前

public<T>voidf(Tx){}类型参数推测使用泛型方法时，不必要指明参数类型，编译器会自动依据传递的参数进行类型推测，就好象f()被重载过无数次泛型方法参数推测publicclassGenericMethods{public<T>voidf(Tx){ System.out.println(x.getClass().getName());}publicstaticvoidmain(String[]args){GenericMethodsgm=newGenericMethods();gm.f("");gm.f(1);gm.f(1.0);gm.f(1.0F);gm.f('c');gm.f(gm);}}java.lang.Stringjava.lang.Integerjava.lang.Doublejava.lang.Floatjava.lang.Character.njnu.cs.abyssoop.ch15.GenericMethods[A][A,B,C][,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z]importjava.util.*;publicclassGenericVarargs{publicstatic<T>List<T>makeList(T...args){//可变参数，…表示参数可以是一个T类

//型数组或是T类型的对象序列，只能用于最后一个参数List<T>result=newArrayList<T>();for(Titem:args)//foreach语法遍历可变参数result.add(item);returnresult;}publicstaticvoidmain(String[]args){List<String>ls=makeList("A");System.out.println(ls);ls=makeList("A","B","C");System.out.println(ls);ls=makeList("ABCDEFGHIJKLMNOPQRSTUVWXYZ".split(""));System.out.println(ls);}}泛型方法与可变参数边界和类型擦除泛型类定义内部，所有的参数类型都只是作为Object类，丢失了具体的类型信息类型擦除用具体类型实例化类型参数不会使得泛型类感知具体的类型classHasF{publicvoidf(){System.out.println("HasF.f()");}}classManipulator<T>{privateTobj;publicManipulator(Tx){obj=x;}publicvoidmanipulate(){obj.f();//编译时错误，f()没有定义} }publicclassManipulation{publicstaticvoidmain(String[]args){HasFhf=newHasF();Manipulator<HasF>manipulator=newManipulator<HasF>(hf);manipulator.manipulate();}}擦除导致类型信息丢失类型边界通过重载的extends关键词声明泛型类参数的类型边界语法classname<Textendsbaseclass&baseinterface1&baseinterface2&…>可以包含一个基类和多个接口，基类在前ClassA{/*...*/}interfaceB{/*...*/}interfaceC{/*...*/}classD<TextendsA&B&C>{/*...*/}classHasF{publicvoidf(){System.out.println("HasF.f()");}}classManipulator<TextendsHasF>{//通过extends关键词限定参数T的界限privateTobj;publicManipulator(Tx){obj=x;}publicvoidmanipulate(){obj.f();//此时可以调用f()方法} }publicclassManipulation{publicstaticvoidmain(String[]args){HasFhf=newHasF();Manipulator<HasF>manipulator=newManipulator<HasF>(hf);manipulator.manipulate();}}泛型方法和边界类型边界类型对于实现某些通用的算法非常有用例如，编写一个泛型算法，找出一个数组中比给定元素大的元素个数public

static<T>intcountGreaterThan(T[]anArray,Telem){

intcount=0;

for(Te:anArray)

if(e>elem)//compilererror，why?++count;

returncount;}public

static<TextendsComparable<T>>intcountGreaterThan(T[]anArray,Telem){

intcount=0;

for(Te:anArray)

if(pareTo(elem)>0)++count;

returncount;}泛型与子类型面向对象中，可以将一个子类对象赋值给一个父类引用对泛型也适用，可以向一个存放父类对象的容器添加子类对象public

voidsomeMethod(Numbern){/*...*/}someMethod(newInteger(10));//OKsomeMethod(newDouble(10.1));//OKBox<Number>box=newBox<Number>();box.add(newInteger(10));//OKbox.add(newDouble(10.1));//OK泛型与子类型但是不能将一个存放子类对象的容器赋值给一个存放父类对象的容器即类型参数的继承关系不能拓展到容器的继承关系publicvoidboxTest(Box<Number>n){/*...*/}//接受什么类型的参数？泛型与子类型如果希望编写一个方法，能应用于下述类型

List<Integer>List<Double>List<Float>List<Byte>List<Number>List<Short>List<Long>How?publicvoid<T>method(List<T>list);//不仅仅能用于上述类型publicvoidmethod(List<Number>list);//只能用于List<Number>类型，无法用于其它类型通配符上界通配符无界通配符下界通配符上界通配符如果希望编写一个方法，能应用于容纳Number容器或其子类型的容器，即

List<Number>List<Integer>…解决办法publicvoidmethod(List<?extendsNumber>list);//泛型参数的类型可以是Number及其子类型；public

static

doublesumOfList(List<?extendsNumber>list){

doubles=0.0;

for(Numbern:list)s+=n.doubleValue();

returns;}List<Integer>li=Arrays.asList(1,2,3);System.out.println("sum="+sumOfList(li));List<Double>ld=Arrays.asList(1.2,2.3,3.5);System.out.println("sum="+sumOfList(ld));无界通配符当方法实现只需要用到Object类的方法而无需用到具体类型的方法，且希望能应用于不同类型的容器时，可以用无界通配符<?>假设，希望写一个通用方法，打印容器List中的所有元素public

static

voidprintList(List<Object>list){

for(Objectelem:list)System.out.println(elem+"");System.out.println();}List<Object>list1=newArrayList<Object>();printList(list1);//OKList<Integer>list2=newArrayList<Integer>();printList(list2);//compiletimeerror!public

static

voidprintList(List<?>list){

for(Objectelem:list)System.out.print(elem+"");System.out.println();}List<Object>list1=newArrayList<Object>();printList(list1);//OKList<Integer>list2=newArrayList<Integer>();printList(list2);//OK下界通配符语法：

<?superA>//表示参数类型为A类型或其父类型例如，要写一个方法，能应用于所有的Integer类列表容器及其父类的列表容器

List<Integer>List<Number>List<Object>public

static

voidaddNumbers(List<?superInteger>list){

for(inti=1;i<=10;i++){list.add(i);}}List<Integer>list1=newArrayList<Integer>();addNumbers(list1);//OKList<Number>list2=newArrayList<Number>();addNumbers(list2);//OK通配符和继承当没有通配符时，用具体类型参数化泛型类型后得到的类型相互之间没有继承关系使用了通配符后，可以在泛型类型之间建立起某种继承关系通配符数组可以将存放子类对