Set是一种数据集合。它与List同样继承与Collection接口。
它与Collection接口中的方法基本一致，并没有对Collection接口进行功能进行功能上的扩充，只是比Collection接口更严格了。与List不同的是，Set中的元素是无无需的，并且都以某种规则保证存入的元素不会出现重复。
它的特点也就是：
1. 元素不会出现重复。
2. 元素是无序的。（存取无序）
3. 元素可以为空。
每种类型的Set所使用的避免元素重复的规则都是不同的，今天我们主要还是看HashSet和TreeSet：
第一种是HashSet：
HashSet
我们先来看看HashSet的构造器是怎么样的：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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 <tt>HashMap</tt> instance has * default initial capacity (16) and load factor (0.75). */ public HashSet() { map = new HashMap<>(); } |
令人惊讶的是HashSet的结构里实际上就包含了一个HashMap，而初始化HashSet就是给这个对象的Map赋值一个空HashMap对象。
再让我们来看一看插入操作：
|
1
2
3
|
public boolean add(E e) { return map.put(e, PRESENT)==null; } |
add操作实际上是向map中插入了一条记录，是以我们所要存的元素为key，以一个空对象为value的记录。
到了这不实际上我们已经能明白，set里的元素是不可能重复的，因为我们对hashMap同一个key进行put，并不会生成新的记录，而是对上一条记录进行覆盖而已。但是hashMap是如何判断Key是否是同一个的呢？让我们来看以下代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
public class SetTest { public class Obj { public String name; public Obj(String name) { this.name=name; } } public static void main(String[] args) { Set<String> strSet = new HashSet<String>(); 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> objSet = new HashSet<Obj>(); 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); } } } |
结果为：
|
1
2
3
4
|
false12311 |
那让我们继续看看，在put方法中java代码又干了什么呢？（汗，感觉我从Set讲到HashMap去了）
|
1
2
3
|
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } |
在下一层的代码里，先对key本身进行了一个转化hash(key)，这个方法的源码是：
|
1
2
3
4
|
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.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/** * The backing map. */ private transient NavigableMap<E,Object> m; // 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<E,Object> m) { 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 <i>mutually * comparable</i>: {@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<E,Object>()); // 将一个新生成的TreeMap空对象赋值给m，也就是上一方法 } |
而用这个构造器定义的TreeMap是没有指定对比器的：
|
1
2
3
|
public TreeMap() { comparator = null; } |
让我们来看一下TreeSet的add方法的全过程：
|
1
2
3
|
public boolean add(E e) { return m.put(e, PRESENT)==null; // 如果返回值为空则表示我们插入了一个新的元素，如果返回值为非空，则表明我们插入的元素已经存在。 } |
实际上也就是向TreeMap以你的要放入的元素为key， 空对象为value做一次put。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
public V put(K key, V value) { Entry<K,V> t = root; // 定义t为根节点 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<K,V> parent; // 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进行对比 if (cmp < 0) // 对比后值小于0，则表示我们插入的key小于根节点的key，就让父节点往左走，并循环直至命中 t = t.left; else if (cmp > 0) // 对比后值大于0，则表示我们插入的key小于根节点的key，就让父节点往右走，并循环直至命中 t = t.right; else //当命中，用我们的值替换原有的值一次保证不插入重复的key，并返回替换后的对象 return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); // 如果没有在树中命中，则新生成一个树节点此时parent的父节点已经遍历到了某个叶子节点。 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又是相等就覆盖，所以不会重复
以上这篇JAVA HashSet和TreeSet 保证存入元素不会重复的操作就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/sinat_38232376/article/details/83655755
