JAVA HashSet和TreeSet 保证存入元素不会重复的操作

2023-07-14 13:45:04 70

Set是一种数据集合。它与List同样继承与Collection接口。

它与Collection接口中的方法基本一致，并没有对Collection接口进行功能进行功能上的扩充，只是比Collection接口更严格了。与List不同的是，Set中的元素是无无需的，并且都以某种规则保证存入的元素不会出现重复。

它的特点也就是：

1.元素不会出现重复。

2.元素是无序的。（存取无序）

3.元素可以为空。

每种类型的Set所使用的避免元素重复的规则都是不同的，今天我们主要还是看HashSet和TreeSet：

第一种是HashSet：

HashSet

我们先来看看HashSet的构造器是怎么样的：

staticfinallongserialVersionUID=-5024744406713321676L;

privatetransientHashMapmap;

//DummyvaluetoassociatewithanObjectinthebackingMap
privatestaticfinalObjectPRESENT=newObject();

/**
*Constructsanew,emptyset;thebackingHashMapinstancehas
*defaultinitialcapacity(16)andloadfactor(0.75).
*/
publicHashSet(){
map=newHashMap<>();
}

令人惊讶的是HashSet的结构里实际上就包含了一个HashMap，而初始化HashSet就是给这个对象的Map赋值一个空HashMap对象。

再让我们来看一看插入操作：

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

add操作实际上是向map中插入了一条记录，是以我们所要存的元素为key，以一个空对象为value的记录。

到了这不实际上我们已经能明白，set里的元素是不可能重复的，因为我们对hashMap同一个key进行put，并不会生成新的记录，而是对上一条记录进行覆盖而已。但是hashMap是如何判断Key是否是同一个的呢？让我们来看以下代码

publicclassSetTest{

publicclassObj{
publicStringname;
publicObj(Stringname){
this.name=name;
}
}

publicstaticvoidmain(String[]args){
SetstrSet=newHashSet();
Stringstr1=newString("123");
Stringstr2=newString("123");
strSet.add(str1);
strSet.add(str2);
System.out.println(str1==str2);
for(Stringstr:strSet){
System.out.println(str);
}
SetobjSet=newHashSet();
Objo1=newSetTest().newObj("1");
Objo2=newSetTest().newObj("1");
objSet.add(o1);
objSet.add(o2);
for(Objstr:objSet){
System.out.println(str.name);
}
}
}

结果为：

false
123
1
1

那让我们继续看看，在put方法中java代码又干了什么呢？（汗，感觉我从Set讲到HashMap去了）

publicVput(Kkey,Vvalue){
returnputVal(hash(key),key,value,false,true);
}

在下一层的代码里，先对key本身进行了一个转化hash(key)，这个方法的源码是：

staticfinalinthash(Objectkey){
inth;
return(key==null)?0:(h=key.hashCode())^(h>>>16);
}

判断key是否为空，如果为空就返回0，不然就对key值取hashCode并与h>>>16的值做异或操作，异或是一种位运算，在此就不做解释了。而>>>是一种位移操作，在这个hash()方法里，实际上是生成了这个key值对应的hash值。这里做了什么计算，我准备放到另一篇博客里进行讨论，无论怎么样，我们都知道对hashmapput相同的key值，不会重复的，这个是由HashMap的机制由hashCode也就是Hash码解决的，关于HashMap的结构和具体方法，我会在另外一篇博客中单独列出。

TreeSet

当我们new一个TreeSet的时候，实际上是创建了一个TreeMap，并将这个TreeMap赋值给了TreeSet对象的m.

/**
*Thebackingmap.
*/
privatetransientNavigableMapm;

//DummyvaluetoassociatewithanObjectinthebackingMap
privatestaticfinalObjectPRESENT=newObject();

/**
*Constructsasetbackedbythespecifiednavigablemap.
*/
TreeSet(NavigableMapm){
this.m=m;
}
/**
*Constructsanew,emptytreeset,sortedaccordingtothe
*naturalorderingofitselements.Allelementsinsertedinto
*thesetmustimplementthe{@linkComparable}interface.
*Furthermore,allsuchelementsmustbemutually
*comparable:{@codee1.compareTo(e2)}mustnotthrowa
*{@codeClassCastException}foranyelements{@codee1}and
*{@codee2}intheset.Iftheuserattemptstoaddanelement
*tothesetthatviolatesthisconstraint(forexample,theuser
*attemptstoaddastringelementtoasetwhoseelementsare
*integers),the{@codeadd}callwillthrowa
*{@codeClassCastException}.
*/
publicTreeSet(){
this(newTreeMap());//将一个新生成的TreeMap空对象赋值给m，也就是上一方法
}

而用这个构造器定义的TreeMap是没有指定对比器的：

publicTreeMap(){
comparator=null;
}

让我们来看一下TreeSet的add方法的全过程：

publicbooleanadd(Ee){
returnm.put(e,PRESENT)==null;//如果返回值为空则表示我们插入了一个新的元素，如果返回值为非空，则表明我们插入的元素已经存在。
}

实际上也就是向TreeMap以你的要放入的元素为key，空对象为value做一次put。

publicVput(Kkey,Vvalue){
Entryt=root;//定义t为根节点
if(t==null){//如果根节点为空
compare(key,key);//type(andpossiblynull)check//对自身做对比，如果有对比器就用对比器的规则进行对比，如果没有，就用元素自身对比的规则进行对比。为0则相等。我觉得这波其实没有意义，就是一个空的对比。

root=newEntry<>(key,value,null);//新建一个空的根节点
size=1;//设置大小为1
modCount++;//对0做+1
returnnull;//返回空值，表示插入成功。
}
intcmp;
Entryparent;
//splitcomparatorandcomparablepaths
Comparatorcpr=comparator;//用本treeMap的对比器对cpr赋值
if(cpr!=null){//如果定义的对比器不为空（在TreeSet里是为空的，我们之间说到过）
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)//如果key为空就抛出错误
thrownewNullPointerException();
@SuppressWarnings("unchecked")
Comparablek=(Comparable)key;//生成可比较的对象Comparable
do{
parent=t;将父节点（最初是根节点）赋值给parent
cmp=k.compareTo(t.key);//对我们要插入的key与根节点的keyj进行对比
if(cmp<0)//对比后值小于0，则表示我们插入的key小于根节点的key，就让父节点往左走，并循环直至命中
t=t.left;
elseif(cmp>0)//对比后值大于0，则表示我们插入的key小于根节点的key，就让父节点往右走，并循环直至命中
t=t.right;
else//当命中，用我们的值替换原有的值一次保证不插入重复的key，并返回替换后的对象
returnt.setValue(value);
}while(t!=null);
}
Entrye=newEntry<>(key,value,parent);//如果没有在树中命中，则新生成一个树节点此时parent的父节点已经遍历到了某个叶子节点。
if(cmp<0)//如果你的这个值是小于叶子节点的，则插入左边，大于则插入右边
parent.left=e;
else
parent.right=e;
fixAfterInsertion(e);//对整棵树做平衡修正
size++;//size值加1表示我们插入了一个值
modCount++;//modCount也加1
returnnull;
}

整个过程就是：

1.先查看根节点是否存在，如果不存在就直接吧这个节点放在根节点上。

2.如果根节点存在就依顺序向下查找，如果找到对应的节点，就把该节点的值替换。

3.如果遍历到了叶子节点仍然没有命中，那么就向叶子节点插入一个子节点，小就在左边大就在右边。

因为TreeSet插入的值都是空对象，只有key是有效的，key又是相等就覆盖，所以不会重复

以上这篇JAVAHashSet和TreeSet保证存入元素不会重复的操作就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。

JAVA HashSet和TreeSet 保证存入元素不会重复的操作

热门推荐

随机推荐