java 中HashMap、HashSet、TreeMap、TreeSet判断元素相同的几种方法比较
java中HashMap、HashSet、TreeMap、TreeSet判断元素相同的几种方法比较
1.1 HashMap
先来看一下HashMap里面是怎么存放元素的。Map里面存放的每一个元素都是key-value这样的键值对，而且都是通过put方法进行添加的，而且相同的key在Map中只会有一个与之关联的value存在。put方法在Map中的定义如下。
Vput(Kkey,Vvalue);
它用来存放key-value这样的一个键值对，返回值是key在Map中存放的旧value，如果之前不存在则返回null。HashMap的put方法是这样实现的。
publicVput(Kkey,Vvalue){
if(key==null)
returnputForNullKey(value);
inthash=hash(key);
inti=indexFor(hash,table.length);
for(Entry<K,V>e=table[i];e!=null;e=e.next){
Objectk;
if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
VoldValue=e.value;
e.value=value;
e.recordAccess(this);
returnoldValue;
}
}
modCount++;
addEntry(hash,key,value,i);
returnnull;
}
从上我们可以看到在添加对应的key-value这样的组合时，如果原本已经存在对应的key，则直接改变对应的value，并返回旧的value，而在判断key是否存在的时候是先比较key的hashCode，再比较相等或equals的。这里可能我们还看不出来，直接从上面代码来看是比较的对应Map.Entry的hashCode和key的hashCode，而实际上在后面我们可以看到Map.Entry的hashCode其实就是其存放key的hashCode。而如果对应的key原本不存在的话将调用addEntry将对应的key-value添加到Map中。addEntry传递的参数hash就是对应key的hashCode。接着我们来看一下addEntry的方法定义。
voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
if((size>=threshold)&&(null!=table[bucketIndex])){
resize(2*table.length);
hash=(null!=key)?hash(key):0;
bucketIndex=indexFor(hash,table.length);
}
createEntry(hash,key,value,bucketIndex);
}
voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex){
Entry<K,V>e=table[bucketIndex];
table[bucketIndex]=newEntry<>(hash,key,value,e);
size++;
}
addEntry的核心是调用createEntry来建立表示对应key-value的Map.Entry对象并进行存放，很显然上述table是一个Map.Entry的数组。Map.Entry中用一个属性hash保存了对应key的hashCode。还是来看一下上面调用的Map.Entry的构造方法吧。
Entry(inth,Kk,Vv,Entry<K,V>n){
value=v;
next=n;
key=k;
hash=h;
}
很显然，其内部保存了对应key、value和key对应的hashCode。
了解了HashMap是怎样存放元素的以后，我们再来看HashMap是怎样存放元素的就比较简单了。HashMap中判断元素是否相同主要有两个方法，一个是判断key是否相同，一个是判断value是否相同。其实在介绍HashMap是怎样存放元素时我们已经介绍了HashMap是怎样判断元素Key是否相同的，那就是首先得hashCode相同，其次是key相等或equals。Map中判断key是否相同是通过containsKey()方法进行的，其在HashMap中的实现如下。
publicbooleancontainsKey(Objectkey){
returngetEntry(key)!=null;
}
finalEntry<K,V>getEntry(Objectkey){
inthash=(key==null)?0:hash(key);
for(Entry<K,V>e=table[indexFor(hash,table.length)];
e!=null;
e=e.next){
Objectk;
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
returne;
}
returnnull;
}
很明显，它就是先判断key的hashCode是否相同，再判断key是否相等或equals的。
Map中用来判断value是否相同是通过containsValue方法来判断的，其在HashMap中的实现如下。
publicbooleancontainsValue(Objectvalue){
if(value==null)
returncontainsNullValue();
Entry[]tab=table;
for(inti=0;i<tab.length;i++)
for(Entrye=tab[i];e!=null;e=e.next)
if(value.equals(e.value))
returntrue;
returnfalse;
}
很显然，对于非null形式的value是通过value的equals来进行判断的，而null形式的只要相等即可，即保存的元素中有value为null即可。
1.2 HashSet
知道了HashMap是如何存放元素和判断元素是否相同的方式以后，我们再来看HashSet是如何判断元素是否相同就比较简单了。
HashSet中的元素其实是通过HashMap来保存的，在每个HashSet对象中都持有一个对应的HashMap对象的引用，在对HashSet进行元素的添加、删除等操作时都是通过其持有的HashMap来进行的。在保存元素时其会将对应的元素作为持有的HashMap的key来进行保存，对应的value是一个常量Object，所以其在保存的时候判断元素是否相同所使用的是HashMap判断key是否相同的逻辑。其在判断是否包含某一元素时也是调用了所持有的HashMap的containsKey方法来进行判断的。
publicbooleancontains(Objecto){
returnmap.containsKey(o);
}
有兴趣的朋友可以去看一下HashSet的源码。
1.3 TreeMap
TreeMap中存放的元素都是有序的，而且是根据key进行排序的。TreeMap在对存放的元素进行排序时有两种方式，一种是通过自身持有的Comparator进行排序，另一种是通过实现了Comparable接口的key进行排序，优先使用第一种方式，当持有的Comparator（默认为null）为null时则采用第二种方式。TreeMap好几个构造方法，可以通过其构造方法来初始化其持有的Comparator。我们还是先来看一下TreeMap是如何保存元素的，其put方法实现如下。
publicVput(Kkey,Vvalue){
Entry<K,V>t=root;
if(t==null){
compare(key,key);//type(andpossiblynull)check
root=newEntry<>(key,value,null);
size=1;
modCount++;
returnnull;
}
intcmp;
Entry<K,V>parent;
//splitcomparatorandcomparablepaths
Comparator<?superK>cpr=comparator;
if(cpr!=null){
do{
parent=t;
cmp=cpr.compare(key,t.key);
if(cmp<0)
t=t.left;
elseif(cmp>0)
t=t.right;
else
returnt.setValue(value);
}while(t!=null);
}
else{
if(key==null)
thrownewNullPointerException();
Comparable<?superK>k=(Comparable<?superK>)key;
do{
parent=t;
cmp=k.compareTo(t.key);
if(cmp<0)
t=t.left;
elseif(cmp>0)
t=t.right;
else
returnt.setValue(value);
}while(t!=null);
}
Entry<K,V>e=newEntry<>(key,value,parent);
if(cmp<0)
parent.left=e;
else
parent.right=e;
fixAfterInsertion(e);
size++;
modCount++;
returnnull;
}
从上述实现我们可以看到，第一个元素将直接存进去。之后的元素分两种情况进行，一种是持有的Comparator不为空的情况，一种是持有的Comparator为空的情况。Comparator不为空的时候将通过Comparator来确定存放元素的位置，其中有一点很重要的是当通过Comparator比较了现有元素的key与当前存放元素的key的结果为0时，将认为当前存放的元素key在原有Map中已经存在，然后改变原有的key对应的value为新value，然后就直接返回了旧value。当持有的Comparator为空时将通过实现了Comparable接口的key的compareTo方法来决定元素存放的位置，有一点与使用Comparator类似的地方是当原有key作为Comparable与新存入的key进行比较的结果为0时将认为新存入的key在原Map中已经存在，将直接改变对应的原key的value，而不再新存入key-value对。实际上其判断元素是否存在的containsKey方法的主要实现逻辑也是类似的，具体实现如下。
publicbooleancontainsKey(Objectkey){
returngetEntry(key)!=null;
}
finalEntry<K,V>getEntry(Objectkey){
//Offloadcomparator-basedversionforsakeofperformance
if(comparator!=null)
returngetEntryUsingComparator(key);
if(key==null)
thrownewNullPointerException();
Comparable<?superK>k=(Comparable<?superK>)key;
Entry<K,V>p=root;
while(p!=null){
intcmp=k.compareTo(p.key);
if(cmp<0)
p=p.left;
elseif(cmp>0)
p=p.right;
else
returnp;
}
returnnull;
}
因为TreeMap判断元素是否存在的逻辑是通过判断Comparator或Comparable进行比较后的结果是否为0，所以我们在使用TreeMap希望实现某种类似于元素equals的逻辑时要特别小心。
TreeMap的containsValue的逻辑还是判断的对应的value是否equals，与HashMap类似，有兴趣的朋友可以查看一下TreeMap的源码。
1.4 TreeSet
TreeSet也是的Set的一种实现，其存放的元素是不重复的，而且是有序的，默认情况下所存放的元素必须实现Comparable接口，因为默认情况下将把元素当做Comparable对象进行比较。TreeSet也是可以通过Comparator来比较其中存放的元素的，这可以在构造TreeSet的时候通过传入一个Comparator对象或一个持有Comparator对象的TreeMap来实现。TreeSet的实现与HashSet的实现类似，其内部也持有了一个Map的引用，只不过它引用的不是HashMap，而是TreeMap。TreeSet中元素的新增、删除等操作都是由其持有的TreeMap来实现的，所以与HashSet类似，TreeSet中判断元素是否相同的方式与TreeMap是一致的，也是通过Comparator或Comparable来判定的，而不是传统的equals方法。有兴趣的朋友可以去查看一下TreeSet的源码。
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！