总结Java集合类操作优化经验
在实际的项目开发中会有很多的对象,如何高效、方便地管理对象,成为影响程序性能与可维护性的重要环节。Java提供了集合框架来解决此类问题,线性表、链表、哈希表等是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构,所有类都在java.util这个包里,清单1描述了集合类的关系。
清单1.集合类之间关系
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│└Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap
集合接口
Collection接口
Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些Collection允许相同的元素、支持对元素进行排序,另一些则不行。JDK不提供直接继承自Collection的类,JDK提供的类都是继承自Collection的子接口,如List和Set。所有实现Collection接口的类都必须提供两个标准的构造函数,无参数的构造函数用于创建一个空的Collection,有一个Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素,后一个构造函数允许用户复制一个Collection。
如何遍历Collection中的每一个元素?
不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代子,使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下:
Iteratorit=collection.iterator();//获得一个迭代子 while(it.hasNext()){ Objectobj=it.next();//得到下一个元素 }
Collection接口派生的两个接口是List和Set。
Collection接口提供的主要方法:
1、booleanadd(Objecto)添加对象到集合;
2、booleanremove(Objecto)删除指定的对象;
3、intsize()返回当前集合中元素的数量;
4、booleancontains(Objecto)查找集合中是否有指定的对象;
5、booleanisEmpty()判断集合是否为空;
6、Iteratoriterator()返回一个迭代器;
7、booleancontainsAll(Collectionc)查找集合中是否有集合C中的元素;
8、booleanaddAll(Collectionc)将集合C中所有的元素添加给该集合;
9、voidclear()删除集合中所有元素;
10、voidremoveAll(Collectionc)从集合中删除C集合中也有的元素;
11、voidretainAll(Collectionc)从集合中删除集合C中不包含的元素。
List接口
List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组。和下文要提到的Set不同,List允许有相同的元素。
除了具有Collection接口必备的iterator()方法外,List还提供一个listIterator()方法,返回一个ListIterator接口。和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加、删除、设定元素、向前或向后遍历等功能。实现List接口的常用类有LinkedList,ArrayList,Vector和Stack等。
List接口提供的主要方法:
1、voidadd(intindex,Objectelement)在指定位置上添加一个对象;
2、booleanaddAll(intindex,Collectionc)将集合C的元素添加到指定的位置;
3、Objectget(intindex)返回List中指定位置的元素;
4、intindexOf(Objecto)返回第一个出现元素O的位置;
5、Objectremoveint(intindex)删除指定位置的元素;
6、Objectset(intindex,Objectelement)用元素element取代位置index上的元素,返回被取代的元素。
Map接口
Map没有继承Collection接口。Map提供Key到Value的映射,一个Map中不能包含相同的Key,每个Key只能映射一个Value。Map接口提供3种集合的视图,Map的内容可以被当作一组Key集合,一组Value集合,或者一组Key-Value映射。
Map提供的主要方法:
1、booleanequals(Objecto)比较对象;
2、booleanremove(Objecto)删除一个对象;
3、put(Objectkey,Objectvalue)添加key和value。
RandomAccess接口
RandomAccess接口是一个标志接口,本身并没有提供任何方法,任务凡是通过调用RandomAccess接口的对象都可以认为是支持快速随机访问的对象。此接口的主要目的是标识那些可支持快速随机访问的List实现。任何一个基于数组的List实现都实现了RaodomAccess接口,而基于链表的实现则都没有。因为只有数组能够进行快速的随机访问,而对链表的随机访问需要进行链表的遍历。因此,此接口的好处是,可以在应用程序中知道正在处理的List对象是否可以进行快速随机访问,从而针对不同的List进行不同的操作,以提高程序的性能。
集合类介绍
LinkedList类
LinkedList实现了List接口,允许Null元素。此外LinkedList提供额外的Get、Remove、Insert等方法在LinkedList的首部或尾部操作数据。这些操作使得LinkedList可被用作堆栈(Stack)、队列(Queue)或双向队列(Deque)。请注意LinkedList没有同步方法,它不是线程同步的,即如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List,方法如
Listlist=Collections.synchronizedList(newLinkedList(…));
ArrayList类
ArrayList实现了可变大小的数组。它允许所有元素,包括Null。Size、IsEmpty、Get、Set等方法的运行时间为常数,但是Add方法开销为分摊的常数,添加N个元素需要O(N)的时间,其他的方法运行时间为线性。
每个ArrayList实例都有一个容量(Capacity),用于存储元素的数组的大小,这个容量可随着不断添加新元素而自动增加。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。和LinkedList一样,ArrayList也是线程非同步的(unsynchronized)。
ArrayList提供的主要方法:
1、Booleanadd(Objecto)将指定元素添加到列表的末尾;
2、Booleanadd(intindex,Objectelement)在列表中指定位置加入指定元素;
3、BooleanaddAll(Collectionc)将指定集合添加到列表末尾;
4、BooleanaddAll(intindex,Collectionc)在列表中指定位置加入指定集合;
5、Booleanclear()删除列表中所有元素;
6、Booleanclone()返回该列表实例的一个拷贝;
7、Booleancontains(Objecto)判断列表中是否包含元素;
8、BooleanensureCapacity(intm)增加列表的容量,如果必须,该列表能够容纳m个元素;
9、Objectget(intindex)返回列表中指定位置的元素;
10、IntindexOf(Objectelem)在列表中查找指定元素的下标;
11、Intsize()返回当前列表的元素个数。
Vector类
Vector非常类似于ArrayList,区别是Vector是线程同步的。由Vector创建的Iterator,虽然和ArrayList创建的Iterator是同一接口,但是,因为Vector是同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常。
Stack类
Stack继承自Vector,实现了一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。除了基本的Push和Pop方法,还有Peek方法得到栈顶的元素,Empty方法测试堆栈是否为空,Search方法检测一个元素在堆栈中的位置。注意,Stack刚创建后是空栈。
Set类
Set是一种不包含重复的元素的Collection,即任意的两个元素e1和e2都有e1.equals(e2)=false。Set最多有一个null元素。很明显,Set的构造函数有一个约束条件,传入的Collection参数不能包含重复的元素。请注意,必须小心操作可变对象(MutableObject),如果一个Set中的可变元素改变了自身状态,这可能会导致一些问题。
Hashtable类
Hashtable继承Map接口,实现了一个基于Key-Value映射的哈希表。任何非空(non-null)的对象都可作为Key或者Value。添加数据使用Put(Key,Value),取出数据使用Get(Key),这两个基本操作的时间开销为常数。
Hashtable通过InitialCapacity和LoadFactor两个参数调整性能。通常缺省的LoadFactor0.75较好地实现了时间和空间的均衡。增大LoadFactor可以节省空间但相应的查找时间将增大,会影响像Get和Put这样的操作。使用Hashtable的简单示例,将1、2、3这三个数字放到Hashtable里面,他们的Key分别是”one”、”two”、”three”,代码如清单2所示。
清单2.Hashtable示例
Hashtablenumbers=newHashtable(); numbers.put(“one”,newInteger(1)); numbers.put(“two”,newInteger(2)); numbers.put(“three”,newInteger(3));
如果我们需要取出一个数,比如2,可以用相应的key来取出,代码如清单3所示。
清单3.从Hastable读取数据
Integern=(Integer)numbers.get(“two”); System.out.println(“two=”+n);
由于作为Key的对象将通过计算其散列函数来确定与之对应的Value的位置,因此任何作为key的对象都必须实现HashCode和Equals方法。HashCode和Equals方法继承自根类Object,如果你用自定义的类当作Key的话,要相当小心,按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的HashCode必须相同,但如果两个对象不同,则它们的HashCode不一定不同,如果两个不同对象的HashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的HashCode()方法,能加快哈希表的操作。
如果相同的对象有不同的HashCode,对哈希表的操作会出现意想不到的结果(期待的Get方法返回Null),要避免这种问题,最好同时复写Equals方法和HashCode方法,而不要只写其中一个。
HashMap类
HashMap和Hashtable类似,不同之处在于HashMap是线程非同步的,并且允许Null,即NullValue和NullKey。但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者LoadFactor参数设置过低。
WeakHashMap类
WeakHashMap是一种改进的HashMap,它对Key实行“弱引用”,如果一个Key不再被外部所引用,那么该Key可以被GC回收。
集合类实践
ArrayList、Vector、LinkedList均来自AbstractList的实现,而AbstractList直接实现了List接口,并扩展自AbstarctCollection。ArrayList和Vector使用了数组实现,ArrayList没有对任何一个方法提供线程同步,因此不是线程安全的,Vector中绝大部分方法都做了线程同步,是一种线程安全的实现。LinkedList使用了循环双向链表数据结构,由一系列表项连接而成,一个表项总是包含3个部分,元素内容、前驱表项和后驱表项。
当ArrayList对容量的需求超过当前数组的大小时,需要进行扩容。扩容过程中,会进行大量的数组复制操作,而数组复制时,最终将调用System.arraycopy()方法。LinkedList由于使用了链表的结构,因此不需要维护容量的大小,然而每次的元素增加都需要新建一个Entry对象,并进行更多的赋值操作,在频繁的系统调用下,对性能会产生一定的影响,在不间断地生成新的对象还是占用了一定的资源。而因为数组的连续性,因此总是在尾端增加元素时,只有在空间不足时才产生数组扩容和数组复制。
ArrayList是基于数组实现的,而数组是一块连续的内存空间,如果在数组的任意位置插入元素,必然导致在该位置后的所有元素需要重新排列,因此其效率较差,尽可能将数据插入到尾部。LinkedList不会因为插入数据导致性能下降。
ArrayList的每一次有效的元素删除操作后都要进行数组的重组,并且删除的元素位置越靠前,数组重组时的开销越大,要删除的元素位置越靠后,开销越小。LinkedList要移除中间的数据需要便利完半个List。
清单4.ArrayList和LinkedList使用代码
importjava.util.ArrayList; importjava.util.LinkedList; publicclassArrayListandLinkedList{ publicstaticvoidmain(String[]args){ longstart=System.currentTimeMillis(); ArrayListlist=newArrayList(); Objectobj=newObject(); for(inti=0;i<5000000;i++){ list.add(obj); } longend=System.currentTimeMillis(); System.out.println(end-start); start=System.currentTimeMillis(); LinkedListlist1=newLinkedList(); Objectobj1=newObject(); for(inti=0;i<5000000;i++){ list1.add(obj1); } end=System.currentTimeMillis(); System.out.println(end-start); start=System.currentTimeMillis(); Objectobj2=newObject(); for(inti=0;i<1000;i++){ list.add(0,obj2); } end=System.currentTimeMillis(); System.out.println(end-start); start=System.currentTimeMillis(); Objectobj3=newObject(); for(inti=0;i<1000;i++){ list1.add(obj1); } end=System.currentTimeMillis(); System.out.println(end-start); start=System.currentTimeMillis(); list.remove(0); end=System.currentTimeMillis(); System.out.println(end-start); start=System.currentTimeMillis(); list1.remove(250000); end=System.currentTimeMillis(); System.out.println(end-start); } }
清单5.运行输出
639 1296 6969 0 0 15
HashMap是将Key做Hash算法,然后将Hash值映射到内存地址,直接取得Key所对应的数据。在HashMap中,底层数据结构使用的是数组,所谓的内存地址即数组的下标索引。HashMap的高性能需要保证以下几点:
1、Hash算法必须是高效的;
2、Hash值到内存地址(数组索引)的算法是快速的;
3、根据内存地址(数组索引)可以直接取得对应的值。
HashMap实际上是一个链表的数组。前面已经介绍过,基于HashMap的链表方式实现机制,只要HashCode()和Hash()方法实现得足够好,能够尽可能地减少冲突的产生,那么对HashMap的操作几乎等价于对数组的随机访问操作,具有很好的性能。但是,如果HashCode()或者Hash()方法实现较差,在大量冲突产生的情况下,HashMap事实上就退化为几个链表,对HashMap的操作等价于遍历链表,此时性能很差。
HashMap的一个功能缺点是它的无序性,被存入到HashMap中的元素,在遍历HashMap时,其输出是无序的。如果希望元素保持输入的顺序,可以使用LinkedHashMap替代。
LinkedHashMap继承自HashMap,具有高效性,同时在HashMap的基础上,又在内部增加了一个链表,用以存放元素的顺序。
HashMap通过hash算法可以最快速地进行Put()和Get()操作。TreeMap则提供了一种完全不同的Map实现。从功能上讲,TreeMap有着比HashMap更为强大的功能,它实现了SortedMap接口,这意味着它可以对元素进行排序。TreeMap的性能略微低于HashMap。如果在开发中需要对元素进行排序,那么使用HashMap便无法实现这种功能,使用TreeMap的迭代输出将会以元素顺序进行。LinkedHashMap是基于元素进入集合的顺序或者被访问的先后顺序排序,TreeMap则是基于元素的固有顺序(由Comparator或者Comparable确定)。
LinkedHashMap是根据元素增加或者访问的先后顺序进行排序,而TreeMap则根据元素的Key进行排序。
清单6所示代码演示了使用TreeMap实现业务逻辑的排序。
清单6.TreeMap实现排序
importjava.util.Iterator; importjava.util.Map; importjava.util.TreeMap; publicclassStudentimplementsComparable<Student>{ publicStringname; publicintscore; publicStudent(Stringname,intscore){ this.name=name; this.score=score; } @Override //告诉TreeMap如何排序 publicintcompareTo(Studento){ //TODOAuto-generatedmethodstub if(o.score<this.score){ return1; }elseif(o.score>this.score){ return-1; } return0; } @Override publicStringtoString(){ StringBuffersb=newStringBuffer(); sb.append("name:"); sb.append(name); sb.append(""); sb.append("score:"); sb.append(score); returnsb.toString(); } publicstaticvoidmain(String[]args){ TreeMapmap=newTreeMap(); Students1=newStudent("1",100); Students2=newStudent("2",99); Students3=newStudent("3",97); Students4=newStudent("4",91); map.put(s1,newStudentDetailInfo(s1)); map.put(s2,newStudentDetailInfo(s2)); map.put(s3,newStudentDetailInfo(s3)); map.put(s4,newStudentDetailInfo(s4)); //打印分数位于S4和S2之间的人 Mapmap1=((TreeMap)map).subMap(s4,s2); for(Iteratoriterator=map1.keySet().iterator();iterator.hasNext();){ Studentkey=(Student)iterator.next(); System.out.println(key+"->"+map.get(key)); } System.out.println("subMapend"); //打印分数比s1低的人 map1=((TreeMap)map).headMap(s1); for(Iteratoriterator=map1.keySet().iterator();iterator.hasNext();){ Studentkey=(Student)iterator.next(); System.out.println(key+"->"+map.get(key)); } System.out.println("subMapend"); //打印分数比s1高的人 map1=((TreeMap)map).tailMap(s1); for(Iteratoriterator=map1.keySet().iterator();iterator.hasNext();){ Studentkey=(Student)iterator.next(); System.out.println(key+"->"+map.get(key)); } System.out.println("subMapend"); } } classStudentDetailInfo{ Students; publicStudentDetailInfo(Students){ this.s=s; } @Override publicStringtoString(){ returns.name+"'sdetailinformation"; } }
清单7.运行输出
name:4score:91->4'sdetailinformation name:3score:97->3'sdetailinformation subMapend name:4score:91->4'sdetailinformation name:3score:97->3'sdetailinformation name:2score:99->2'sdetailinformation subMapend name:1score:100->1'sdetailinformation subMapend
WeakHashMap特点是当除了自身有对Key的引用外,如果此Key没有其他引用,那么此Map会自动丢弃该值。如清单8所示代码声明了两个Map对象,一个是HashMap,一个是WeakHashMap,同时向两个map中放入A、B两个对象,当HashMap删除A,并且A、B都指向Null时,WeakHashMap中的A将自动被回收掉。出现这个状况的原因是,对于A对象而言,当HashMap删除并且将A指向Null后,除了WeakHashMap中还保存A外已经没有指向A的指针了,所以WeakHashMap会自动舍弃掉a,而对于B对象虽然指向了null,但HashMap中还有指向B的指针,所以WeakHashMap将会保留B对象。
清单8.WeakHashMap示例代码
importjava.util.HashMap; importjava.util.Iterator; importjava.util.Map; importjava.util.WeakHashMap; publicclassWeakHashMapTest{ publicstaticvoidmain(String[]args)throwsException{ Stringa=newString("a"); Stringb=newString("b"); Mapweakmap=newWeakHashMap(); Mapmap=newHashMap(); map.put(a,"aaa"); map.put(b,"bbb"); weakmap.put(a,"aaa"); weakmap.put(b,"bbb"); map.remove(a); a=null; b=null; System.gc(); Iteratori=map.entrySet().iterator(); while(i.hasNext()){ Map.Entryen=(Map.Entry)i.next(); System.out.println("map:"+en.getKey()+":"+en.getValue()); } Iteratorj=weakmap.entrySet().iterator(); while(j.hasNext()){ Map.Entryen=(Map.Entry)j.next(); System.out.println("weakmap:"+en.getKey()+":"+en.getValue()); } } }
清单9.运行输出
map:b:bbb weakmap:b:bbb
WeakHashMap主要通过expungeStaleEntries这个函数来实现移除其内部不用的条目,从而达到自动释放内存的目的。基本上只要对WeakHashMap的内容进行访问就会调用这个函数,从而达到清除其内部不再为外部引用的条目。但是如果预先生成了WeakHashMap,而在GC以前又不曾访问该WeakHashMap,那不是就不能释放内存了吗?
清单10.WeakHashMapTest1
importjava.util.ArrayList; importjava.util.List; importjava.util.WeakHashMap; publicclassWeakHashMapTest1{ publicstaticvoidmain(String[]args)throwsException{ List<WeakHashMap<byte[][],byte[][]>>maps=newArrayList<WeakHashMap<byte[][],byte[][]>>(); for(inti=0;i<1000;i++){ WeakHashMap<byte[][],byte[][]>d=newWeakHashMap<byte[][],byte[][]>(); d.put(newbyte[1000][1000],newbyte[1000][1000]); maps.add(d); System.gc(); System.err.println(i); } } }
不改变任何JVM参数的情况运行清单10所示代码,由于Java默认内存是64M,抛出内存溢出了错误。
清单11.运行输出
241 242 243 Exceptioninthread"main"java.lang.OutOfMemoryError:Javaheapspace atWeakHashMapTest1.main(WeakHashMapTest1.java:10)
果不其然,WeakHashMap这个时候并没有自动帮我们释放不用的内存。清单12所示代码不会出现内存溢出问题。
清单12.WeakHashMapTest2
importjava.util.ArrayList; importjava.util.List; importjava.util.WeakHashMap; publicclassWeakHashMapTest2{ publicstaticvoidmain(String[]args)throwsException{ List<WeakHashMap<byte[][],byte[][]>>maps=newArrayList<WeakHashMap<byte[][],byte[][]>>(); for(inti=0;i<1000;i++){ WeakHashMap<byte[][],byte[][]>d=newWeakHashMap<byte[][],byte[][]>(); d.put(newbyte[1000][1000],newbyte[1000][1000]); maps.add(d); System.gc(); System.err.println(i); for(intj=0;j<i;j++){ System.err.println(j+"size"+maps.get(j).size()); } } } }
运行结果发现这次测试输出正常,不再出现内存溢出问题。
总的来说,WeakHashMap并不是你什么也干它就能自动释放内部不用的对象的,而是在你访问它的内容的时候释放内部不用的对象。
WeakHashMap实现弱引用,是因为它的Entry<K,V>是继承自WeakReference<K>的,
在WeakHashMap$Entry<K,V>的类定义及构造函数里面如清单13所示。
清单13.WeakHashMap类定义
privatestaticclassEntry<K,V>extendsWeakReference<K> implementsMap.Entry<K,V>Entry(Kkey,Vvalue,ReferenceQueue<K>queue,inthash,Entry<K,V>next){ super(key,queue); this.value=value; this.hash=hash; this.next=next; }
请注意它构造父类的语句:“super(key,queue);”,传入的是Key,因此Key才是进行弱引用的,Value是直接强引用关联在this.value之中。在System.gc()时,Key中的Byte数组进行了回收,而Value依然保持(Value被强关联到Entry上,Entry又关联在Map中,Map关联在ArrayList中)。
For循环中每次都New一个新的WeakHashMap,在Put操作后,虽然GC将WeakReference的Key中的Byte数组回收了,并将事件通知到了ReferenceQueue,但后续却没有相应的动作去触发WeakHashMap去处理ReferenceQueue,所以WeakReference包装Key依然存在于WeakHashMap中,其对应的value也当然存在。
那value是何时被清除的呢?对清单10和清单11两个示例程序进行分析可知,清单11的maps.get(j).size()触发了Value的回收,那又如何触发的呢?查看WeakHashMap源码可知,Size方法调用了expungeStaleEntries方法,该方法对JVM要回收的的Entry(Quene中)进行遍历,并将Entry的Value置空,回收了内存。所以效果是Key在GC的时候被清除,Value在Key清除后访问WeakHashMap被清除。
WeakHashMap类是线程不同步的,可以使用Collections.synchronizedMap方法来构造同步的WeakHashMap,每个键对象间接地存储为一个弱引用的指示对象。因此,不管是在映射内还是在映射之外,只有在垃圾回收器清除某个键的弱引用之后,该键才会自动移除。需要注意的是,WeakHashMap中的值对象由普通的强引用保持。因此应该小心谨慎,确保值对象不会直接或间接地强引用其自身的键,因为这会阻止键的丢弃。注意,值对象可以通过WeakHashMap本身间接引用其对应的键,这就是说,某个值对象可能强引用某个其他的键对象,而与该键对象相关联的值对象转而强引用第一个值对象的键。
处理此问题的一种方法是,在插入前将值自身包装在WeakReferences中,如:m.put(key,newWeakReference(value)),然后,分别用get进行解包,该类所有“collection视图方法”返回的迭代器均是快速失败的,在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器自身的Remove或Add方法,其他任何时间任何方式的修改,迭代器都将抛出ConcurrentModificationException。因此,面对并发的修改,迭代器很快就完全失败,而不是冒着在将来不确定的时间任意发生不确定行为的风险。
注意,我们不能确保迭代器不失败,一般来说,存在不同步的并发修改时,不可能做出任何完全确定的保证。
总结
综合前面的介绍和实例代码,我们可以知道,如果涉及到堆栈、队列等操作,应该考虑用List。对于需要快速插入、删除元素等操作,应该使用LinkedList。如果需要快速随机访问元素,应该使用ArrayList。如果程序在单线程环境中,或者访问仅仅在一个线程中进行,考虑非同步的类,其效率较高。如果多个线程可能同时操作一个类,应该使用同步的类。要特别注意对哈希表的操作,作为Key的对象要正确复写Equals和HashCode方法。尽量返回接口而非实际的类型,如返回List而非ArrayList,这样如果以后需要将ArrayList换成LinkedList时,客户端代码不用改变,这就是针对抽象进行编程思想。
本文只是针对应用层面的分享,希望对大家优化Java集合类操作有所帮助。