多平台统一管理软件接口,如何实现多平台统一管理软件接口
273
2022-11-19
JAVA HashSet和TreeSet 保证存入元素不会重复的操作
Set是一种数据集合。它与List同样继承与Collection接口。
它与Collection接口中的方法基本一致,并没有对Collection接口进行功能进行功能上的扩充,只是比Collection接口更严格了。与List不同的是,Set中的元素是无无需的,并且都以某种规则保证存入的元素不会出现重复。
它的特点也就是:
1. 元素不会出现重复。
2. 元素是无序的。(存取无序)
3. 元素可以为空。
每种类型的Set所使用的避免元素重复的规则都是不同的,今天我们主要还是看HashSet和TreeSet:
第一种是HashSet:
HashSet
我们先来看看HashSet的构造器是怎么样的:
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing HashMap instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
令人惊讶的是HashSet的结构里实际上就包含了一个HashMap,而初始化HashSet就是给这个对象的Map赋值一个空HashMap对象。
再让我们来看一看插入操作:
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
add操作实际上是向map中插入了一条记录,是以我们所要存的元素为key,以一个空对象为value的记录。
到了这不实际上我们已经能明白,set里的元素是不可能重复的,因为我们对hashMap同一个key进行put,并不会生成新的记录,而是对上一条记录进行覆盖而已。但是hashMap是如何判断Key是否是同一个的呢?让我们来看以下代码
public class SetTest {
public class Obj {
public String name;
public Obj(String name) {
this.name=name;
}
}
public static void main(String[] args) {
Set
String str1 = new String("123");
String str2 = new String("123");
strSet.add(str1);
strSet.add(str2);
System.out.println(str1 == str2);
for(String str : strSet) {
System.out.println(str);
}
Set
Obj o1 = new SetTest().new Obj("1");
Obj o2 = new SetTest().new Obj("1");
objSet.add(o1);
objSet.add(o2);
for(Obj str : objSet) {
System.out.println(str.name);
}
}
}
结果为:
false
123
1
1
那让我们继续看看,在put方法中java代码又干了什么呢?(汗,感觉我从Set讲到HashMap去了)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
在下一层的代码里,先对key本身进行了一个转化hash(key),这个方法的源码是:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
判断key是否为空,如果为空就返回0,不然就对key值取hashCode并与h>>>16的值做异或操作,异或是一种位运算,在此就不做解释了。而>>>是一种位移操作, 在这个hash()方法里,实际上是生成了这个key值对应的hash值。这里做了什么计算,我准备放到另一篇博客里进行讨论,无论怎么样,我们都知道对hashmap put相同的key值,不会重复的,这个是由HashMap的机制由hashCode也就是Hash码解决的,关于HashMap的结构和具体方法,我会在另外一篇博客中单独列出。
TreeSet
当我们new 一个TreeSet的时候,实际上是创建了一个TreeMap,并将这个TreeMap赋值给了TreeSet对象的m.
/**
* The backing map.
*/
private transient NavigableMap
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a set backed by the specified navigable map.
*/
TreeSet(NavigableMap
this.m = m;
}
/**
* Constructs a new, empty tree set, sorted according to the
* natural ordering of its elements. All elements inserted into
* the set must implement the {@link Comparable} interface.
* Furthermore, all such elements must be mutually
* comparable: {@code e1.compareTo(e2)} must not throw a
* {@code ClassCastException} for any elements {@code e1} and
* {@code e2} in the set. If the user attempts to add an element
* to the set that violates this constraint (for example, the user
* attempts to add a string element to a set whose elements are
* integers), the {@code add} call will throw a
* {@code ClassCastException}.
*/
public TreeSet() {
this(new TreeMap
}
而用这个构造器定义的TreeMap是没有指定对比器的:
public TreeMap() {
comparator = null;
}
让我们来看一下TreeSet的add方法的全过程:
public boolean add(E e) {
return m.put(e, PRESENT)==null; // 如果返回值为空则表示我们插入了一个新的元素,如果返回值为非空,则表明我们插入的元素已经存在。
}
实际上也就是向TreeMap以你的要放入的元素为key, 空对象为value做一次put。
public V put(K key, V value) {
Entry
if (t == null) { // 如果根节点为空
compare(key, key); // type (and possibly null) check // 对自身做对比,如果有对比器就用对比器的规则进行对比,如果没有,就用元素自身对比的规则进行对比。为0则相等。我觉得这波其实没有意义,就是一个空的对比。
root = new Entry<>(key, value, null); // 新建一个空的根节点
size = 1; // 设置大小为1
modCount++; //对0做+1
return null; // 返回空值,表示插入成功。
}
int cmp;
Entry
// split comparator and comparable paths
Comparator super K> cpr = comparator; // 用本treeMap的对比器对cpr赋值
if (cpr != null) { // 如果定义的对比器不为空(在TreeSet里是为空的,我们之间说到过)
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else { // 如果对比器为空(在这种情况下是为空的)
if (key == null) // 如果key为空就抛出错误
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable super K> k = (Comparable super K>) key;// 生成可比较的对象Comparable
do {
parent = t; 将父节点(最初是根节点)赋值给parent
cmp = k.compareTo(t.key); //对我们要插入的key与根节点的keyj进行对比
http://if (cmp < 0) // 对比后值小于0,则表示我们插入的key小于根节点的key,就让父节点往左走,并循环直至命中
t = t.left;
else if (cmp > 0) // 对比后值大于0,则表示我们插入的key小于根节点的key,就让父节点往右走,并循环直至命中
t = t.right;
else //当命中,用我们的值替换原有的值一次保证不插入重复的key,并返回替换后的对象
returnkBozX t.setValue(value);
} while (t != null);
}
Entry
if (cmp < 0) // 如果你的这个值是小于叶子节点的,则插入左边,大于则插入右边
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e); // 对整棵树做平衡修正
size++; // size值加1表示我们插入了一个值
modCount++; // modCount也加1
return null;
}
整个过程就是:
1. 先查看根节点是否存在,如果不存在就直接吧这个节点放在根节点上。
2. 如果根节点存在就依顺序向下查找,如果找到对应的节点,就把该节点的值替换。
3. 如果遍历到了叶子节点仍然没有命中,那么就向叶子节点插入一个子节点,小就在左边大就在右边。
因为TreeSet插入的值都是空对象,只有key是有效的,key又是相等就覆盖,所以不会重复
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~