Java容器学习笔记Set接口及其实现类的相关知识总结.docxVIP

Java容器学习笔记（二） Set接口及其实现类的相关知识总结分类：Java学习实习笔记2011-10-21 00:54652人阅读评论(4)收藏举报在Java容器学习笔记（一）中概述了Collection的基本概念及接口实现，并且总结了它的一个重要子接口List及其子类的实现和用法。本篇主要总结Set接口及其实现类的用法，包括HashSet（无序不重复），LinkedHashSet（按放入顺序有序不重复），TreeSet（按红黑树方式有序不重复），EnumSet，ConcurrentSkipListSet（来自于java.util.concurrent包），CopyOnWriteArraySet（来自于java.util.concurrent包）等。2. Set接口及其实现类Set接口中方法清单：Set集合和List集合都存放的是单个元素的序列，但是Set集合不允许集合中有重复元素（主要依赖于equals方法）。Set接口的父接口为Collection和Iterable，直接实现该接口的子接口有SortedSet和NavigableSet。实现Set接口的重要类有HashSet（无序不重复），LinkedHashSet（按放入顺序有序不重复），TreeSet（按红黑树方式有序不重复），EnumSet，ConcurrentSkipListSet（来自于java.util.concurrent包），CopyOnWriteArraySet（来自于java.util.concurrent包）。在Set接口中没有新增任何方法，所有方法均来自其父接口。它无法提供像List中按位存取的方法。在数学上一个集合有三个性质：确定性，互异性，无序性。HashSet的特点、实现机制及使用方法a) HashSet的特点：HashSet中存放的元素是无序的，底层是用HashMap实现的，其中key是要放入的元素，value是一个Object类型的名为PRESENT的常量，由于用到了散列函数，因此其存取速度是非常快的，在地址空间很大的情况下它的存取速度可以达到O(1)级。如果首先了解了HashMap的实现方法，那么HashSet的实现是非常简单的。b）HashSet的实现机制：首先需要了解一下散列或者哈希的用法。我们知道，当数据量很大时hash函数计算的结果将会重复，按照下图所示的形式进行存贮。在HashSet中有个loadFactor（负载因子），对于上图所示总共有11个位置，目前有4个位置已经存放，即40%的空间已被使用。在HashSet的默认实现中，初始容量为16，负载因子为0.75，也就是说当有75%的空间已被使用，将会进行一次再散列（再哈希），之前的散列表（数组）将被删除，新增加的散列表是之前散列表长度的2倍，最大值为Integer.MAX_VALUE。负载因子越高，内存使用率越大，元素的寻找时间越长。负载因子越低，内存使用率越小，元素的寻找时间越短。从上图可以看出，当哈希值相同时，将存放在同一个位置，使用链表方式依次链接下去。（面试官问到这个问题，当时我的回答是再哈希，其实我并不知道HashSet真正是怎么实现的，我只知道在学习数据结构时学习过再哈希，就是这个哈希表很满时需要重新建立哈希表，以便于存取，因为大量的值放在一个位置上就变成了链表的查询了，几乎是O(n/2)级别的，但是我没有说出来再哈希的过程，以及哈希值相同时到底如何存放，所以o(_)o ）。为了说明HashSet在Java中确实如上实现，下面附上JDK中两个重要方法的源码：（下面源码来自于HashMap，原因是HashSet是基于HashMap实现的）view plainprint?1. /*2. *Rehashesthecontentsofthismapintoanewarraywitha3. *largercapacity.Thismethodiscalledautomaticallywhenthe4. *numberofkeysinthismapreachesitsthreshold.5. *6. *IfcurrentcapacityisMAXIMUM_CAPACITY,thismethoddoesnot7. *resizethemap,butsetsthresholdtoInteger.MAX_VALUE.8. *Thishastheeffectofpreventingfuturecalls.9. *10. *paramnewCapacitythenewcapacity,MUSTbeapoweroftwo;11. *mustbegreaterthancurrentcapacityunlesscurrent12. *capacityisMAXIMUM_CAPACITY(inwhichcasevalue13. *isirrelevant).14. */15. voidresize(intnewCapacity)16. EntryoldTable=table;17. intoldCapacity=oldTable.length;18. if(oldCapacity=MAXIMUM_CAPACITY)19. threshold=Integer.MAX_VALUE;20. return;21. 22. 23. EntrynewTable=newEntrynewCapacity;24. transfer(newTable);25. table=newTable;26. threshold=(int)(newCapacity*loadFactor);27. 28. 29. /*30. *TransfersallentriesfromcurrenttabletonewTable.31. */32. voidtransfer(EntrynewTable)33. Entrysrc=table;34. intnewCapacity=newTable.length;35. for(intj=0;jsrc.length;j+)36. Entrye=srcj;37. if(e!=null)38. srcj=null;39. do40. Entrynext=e.next;41. inti=indexFor(e.hash,newCapacity);42. e.next=newTablei;43. newTablei=e;44. e=next;45. while(e!=null);46. 47. 48. HashSet共实现了5个构造方法，对外提供了4个构造方法。这些方法在api中均可看到详细使用说明。由于HashSet基于HashMap实现，我们只关心我们放入的key，value是个Object类型的常量，所以在iterator方法中使用的是HashMap的keySet方法进行迭代的。c）HashSet的使用方法：从HashSet的特点及实现上看，我们知道在不需要放入重复数据并且不关心放入顺序以及元素是否要求有序的情况下，我们没有任何理由不选择使用HashSet。另外HashSet是允许放空值的。那么HashSet是如何保证不重复的？下面一个例子说明：view plainprint?1. importjava.util.HashSet;2. importjava.util.Iterator;3. publicclassExampleForHashSet4. publicstaticvoidmain(Stringargs)5. HashSeths=newHashSet();6. hs.add(newName(Wang,wu);7. hs.add(newName(Zhang,san);8. hs.add(newName(Wang,san);9. hs.add(newName(Zhang,wu);10. /本句输出为211. System.out.println(hs.size();12. Iteratorit=hs.iterator();13. /下面输出两行，分别为Zhang:san和Wang:wu14. while(it.hasNext()15. System.out.println(it.next();16. 17. 18. 19. className20. Stringfirst;21. Stringlast;22. publicName(Stringfirst,Stringlast)23. this.first=first;24. this.last=last;25. 26. Override27. publicbooleanequals(Objecto)28. if(null=o)29. returnfalse;30. 31. if(this=o)32. returntrue;33. 34. if(oinstanceofName)35. Namename=(Name)o;36. /本例认为只要first相同即相等37. if(this.first.equals(name.first)38. returntrue;39. 40. 41. returnfalse;42. 43. Override44. publicinthashCode()45. intprime=31;46. intresult=1;47. /hashcode的实现一定要和equals方法的实现对应48. returnprime*result+first.hashCode();49. 50. Override51. publicStringtoString()52. returnfirst+:+last;53. 54. 简单说明一下上面的例子：上面已经提到HashSet里面放的元素是不允许重复的，那么什么样的元素是重复呢，重复的定义是什么？上面例子中实现了一个简单的类Name类，并且重写了equals方法与hashCode方法，那么重复指的是equals方法吗？equals相同就算是重复吗？当然不是这样的。如果我们改写一下hashCode方法，将返回值改为 return prime*result + first.hashCode() + last.hashCode()那么HashSet中的size会变为4，但是Name(“Wang”, “wu”)和Name(“Wang”, “san”)其实用equals方法来比较的话其实是相同的。 Name n1 =newName(W, x); Name n2 =newName(W, y); System.out.println(n1.equals(n2);也就是说上面代码会输出true。这样我们是不是可以这样认为：如果hashCode相同的话再判断equals的返回值是否为true，如果为true则相同，即上面说的重复。如果hashCode不同那么一定是不重复的？由此看来equals相同，hashCode不一定相同，equals和hashCode的返回值不是绝对关联的？当然我们实现equals方法时是要根据hashCode方法实现的，必须建立关联关系，也就是说正常情况下equals相同，则hashCode的返回值应该是相同的。LinkedHashSet的特点、实现机制及使用方法a) LinkedHashSet的特点：LinkedHashSet保证了按照插入顺序有序，继承自HashSet，没有实现新的可以使用的方法。b) LinkedHashSet实现机制：LinkedHashSet继承自HashSet，构造时使用了在HashSet中被忽略的构造方法：view plainprint?1. /*2. *Constructsanew,emptylinkedhashset.(Thispackageprivate3. *constructorisonlyusedbyLinkedHashSet.)Thebacking4. *HashMapinstanceisaLinkedHashMapwiththespecifiedinitial5. *capacityandthespecifiedloadfactor.6. *7. *paraminitialCapacitytheinitialcapacityofthehashmap8. *paramloadFactortheloadfactorofthehashmap9. *paramdummyignored(distinguishesthis10. *constructorfromotherint,floatconstructor.)11. *throwsIllegalArgumentExceptioniftheinitialcapacityisless12. *thanzero,oriftheloadfactorisnonpositive13. */14. HashSet(intinitialCapacity,floatloadFactor,booleandummy)15. map=newLinkedHashMap(initialCapacity,loadFactor);16. 由上面JDK代码可以看出LinkedHashSet底层是使用LinkedHashMap实现的。所以在实现上是比较简单的，是根据dummy这个参数，我们不需要传入，选择构造的是HashSet还是LinkedHashSet。c) LinkedHashSet的使用方法：由于LinkedHashSet继承自HashSet，并且没有提供额外的供使用的方法，所以在使用时与HashSet基本相同，只是面临的是选择的问题。我们根据需要选择不同的数据结构来实现我们的需求。CopyOnWriteArraySet的特点、实现机制及使用方法a) CopyOnWriteArraySet的特点：CopyOnWriteArraySet是java.util.concurrent包中的一个类，继承自AbstractSet，底层使用CopyOnWriteArrayList实现，拥有Set的特点，也具有ArrayList的特点，并且是线程安全的类。b) CopyOnWriteArraySet的实现机制：在实现时使用了写时拷贝的方法以及使用重入锁实现了线程的同步，底层使用CopyOnWriteArrayList来构造出一个实例对象，在添加元素时调用CopyOnWriteArrayList的addIfAbsent方法保证数据不重复，其它实现与CopyOnWriteArrayList类似。c) CopyOnWriteArraySet的使用方法：这仍然面临的是一个选择的问题，HashSet底层也是使用数组实现的，它的优点是存取效率很高，当负载因子很小时，几乎可以达到O(1)级的存取速度，但是它不是线程安全的。当我们需要在多线程并发环境下使用时可以考虑使用这个类，当然为了实现线程安全，这不是一个唯一的方法。TreeSet的特点、实现机制及使用方法a) TreeSet的特点：TreeSet中所放的元素是有序的，并且元素是不能重复的。b) TreeSet的实现机制：TreeSet是如何保持元素的有序不重复的？首先TreeSet底层使用TreeMap实现，和HashSet一样，将每个要放入的元素放到key的位置，value位置放的是一个Object类型的常量。在JDK源码中有下面一段注释：view plainprint?1. /*2. *Constructsanew,emptytreeset,sortedaccordingtothe3. *naturalorderingofitselements.Allelementsinsertedinto4. *thesetmustimplementthelinkComparableinterface.5. *Furthermore,allsuchelementsmustbemutually6. *comparable:pareTo(e2)mustnotthrowa7. *codeClassCastExceptionforanyelementscodee1and8. *codee2intheset.Iftheuserattemptstoaddanelement9. *tothesetthatviolatesthisconstraint(forexample,theuser10. *a