Java 容器类源码详解 Set

2023-08-21 06:54:04 330

前言

Set表示由无重复对象组成的集合，也是集合框架中重要的一种集合类型，直接扩展自Collection接口。在一个Set中，不能有两个引用指向同一个对象，或两个指向null的引用。如果对象a和b的引用满足条件a.equals(b)，那么这两个对象也不能同时出现在集合中。

通常Set是不要求元素有序的，但也有一些有序的实现，如SortedMap接口、LinkedHashSet接口等。

概述

Set的具体实现通常都是基于Map的。因为Map中键是唯一的，因而在基于Map实现Set时，只需要关心Map中的键，和键关联的值不需要有意义，使用一个任意的对象“占位”即可。我们在前面分析Map中的迭代器时，KeySet()方法得到的就是一个Set。

前面我们分析过Map接口的几个具体实现，通用的实现HahsMap，插入或访问序的LinkedHashMap，按照键升序的TreeMap。同样，在Set的具体实现中，也有HashSet、LinkedHashSet和TreeSet等，分别和Map一一对应，它们的特性对应着相应的Map实现的特性。下面基于HashSet的实现做一个简略的介绍。

HashSet的实现

publicclassHashSet
extendsAbstractSet
implementsSet,Cloneable,java.io.Serializable
{
staticfinallongserialVersionUID=-5024744406713321676L;
privatetransientHashMapmap;
//DummyvaluetoassociatewithanObjectinthebackingMap
privatestaticfinalObjectPRESENT=newObject();
publicHashSet(){
map=newHashMap<>();
}
publicHashSet(Collectionc){
map=newHashMap<>(Math.max((int)(c.size()/.75f)+1,16));
addAll(c);
}
publicHashSet(intinitialCapacity,floatloadFactor){
map=newHashMap<>(initialCapacity,loadFactor);
}
publicHashSet(intinitialCapacity){
map=newHashMap<>(initialCapacity);
}
HashSet(intinitialCapacity,floatloadFactor,booleandummy){
map=newLinkedHashMap<>(initialCapacity,loadFactor);
}
}

从成员变量和构造方法可以清楚地看到，内部使用了一个HahsMap，同时定义了一个无意义的空的静态Object对象(占用8byte)PRESENT。既然map中和键关联的值没有意义，为什么不干脆使用null呢？我们看一下add()方法：

publicbooleanadd(Ee){
returnmap.put(e,PRESENT)==null;
}

Map的put()方法在添加一个新的键时会返回null，在更新一个已经存在的键关联的值时会返回旧值。因而Set中的add()方法可以据此判断新加入的元素是否改变了集合，如果改变了就返回true。因而PRESENT不可以使用null。

其它的方法这里简单地列一下，都是基于map实现的：

publicbooleancontains(Objecto){
returnmap.containsKey(o);
}
publicbooleanremove(Objecto){
returnmap.remove(o)==PRESENT;
}
publicIteratoriterator(){
returnmap.keySet().iterator();
}
publicintsize(){
returnmap.size();
}
publicbooleanisEmpty(){
returnmap.isEmpty();
}
publicvoidclear(){
map.clear();
}
@SuppressWarnings("unchecked")
publicObjectclone(){
try{
HashSetnewSet=(HashSet)super.clone();
newSet.map=(HashMap)map.clone();
returnnewSet;
}catch(CloneNotSupportedExceptione){
thrownewInternalError(e);
}
}
//序列化
privatevoidwriteObject(java.io.ObjectOutputStreams)
throwsjava.io.IOException{
//Writeoutanyhiddenserializationmagic
s.defaultWriteObject();
//WriteoutHashMapcapacityandloadfactor
s.writeInt(map.capacity());
s.writeFloat(map.loadFactor());
//Writeoutsize
s.writeInt(map.size());
//Writeoutallelementsintheproperorder.
for(Ee:map.keySet())
s.writeObject(e);
}
privatevoidreadObject(java.io.ObjectInputStreams)
throwsjava.io.IOException,ClassNotFoundException{
//Readinanyhiddenserializationmagic
s.defaultReadObject();

//Readcapacityandverifynon-negative.
intcapacity=s.readInt();
if(capacity<0){
thrownewInvalidObjectException("Illegalcapacity:"+
capacity);
}
//ReadloadfactorandverifypositiveandnonNaN.
floatloadFactor=s.readFloat();
if(loadFactor<=0||Float.isNaN(loadFactor)){
thrownewInvalidObjectException("Illegalloadfactor:"+
loadFactor);
}
//Readsizeandverifynon-negative.
intsize=s.readInt();
if(size<0){
thrownewInvalidObjectException("Illegalsize:"+
size);
}
//Setthecapacityaccordingtothesizeandloadfactorensuringthat
//theHashMapisatleast25%fullbutclampingtomaximumcapacity.
capacity=(int)Math.min(size*Math.min(1/loadFactor,4.0f),
HashMap.MAXIMUM_CAPACITY);
//CreatebackingHashMap
map=(((HashSet)this)instanceofLinkedHashSet?
newLinkedHashMap(capacity,loadFactor):
newHashMap(capacity,loadFactor));
//Readinallelementsintheproperorder.
for(inti=0;i


小结


Set的内部通常是基于Map来实现的，Map中的Key构成了Set，而Value全部使用一个无意义的Object。
Set的特征与其内部的Set的特征是一致的。基于HashMap的HashSet是无序时的最佳通用实现，基于LinkedHashMap的LinkedHashSet保留插入或访问的顺序，基于TreeMap的TreeSet可以按照元素升序排列，要求元素实现Comaprable接口或自定义比较器。
HashSet,LinkedHashSet,TreeSet都不是线程安全的，在多线程环境下使用时要注意同步问题。
CopyOnWriteArraySet是一个线程安全的实现，但是并不是基于Map实现的，而是通过CopyOnWriteArrayList实现的。使用addIfAbsent()方法进行去重，性能比较一般。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

Java 容器类源码详解 Set

热门推荐

随机推荐