Set是一種數(shù)據(jù)集合。它與List同樣繼承與Collection接口。
它與Collection接口中的方法基本一致，并沒有對Collection接口進行功能進行功能上的擴充，只是比Collection接口更嚴(yán)格了。與List不同的是，Set中的元素是無無需的，并且都以某種規(guī)則保證存入的元素不會出現(xiàn)重復(fù)。
它的特點也就是：
1. 元素不會出現(xiàn)重復(fù)。
2. 元素是無序的。（存取無序）
3. 元素可以為空。
每種類型的Set所使用的避免元素重復(fù)的規(guī)則都是不同的，今天我們主要還是看HashSet和TreeSet：
第一種是HashSet：
HashSet
我們先來看看HashSet的構(gòu)造器是怎么樣的：
|
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的結(jié)構(gòu)里實際上就包含了一個HashMap，而初始化HashSet就是給這個對象的Map賦值一個空HashMap對象。
再讓我們來看一看插入操作：
|
1
2
3
|
public boolean add(E e) { return map.put(e, PRESENT)==null; } |
add操作實際上是向map中插入了一條記錄，是以我們所要存的元素為key，以一個空對象為value的記錄。
到了這不實際上我們已經(jīng)能明白，set里的元素是不可能重復(fù)的，因為我們對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); } } } |
結(jié)果為：
|
1
2
3
4
|
false12311 |
那讓我們繼續(xù)看看，在put方法中java代碼又干了什么呢？（汗，感覺我從Set講到HashMap去了）
|
1
2
3
|
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } |
在下一層的代碼里，先對key本身進行了一個轉(zhuǎn)化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值對應(yīng)的hash值。這里做了什么計算，我準(zhǔn)備放到另一篇博客里進行討論，無論怎么樣，我們都知道對hashmap put相同的key值，不會重復(fù)的，這個是由HashMap的機制由hashCode也就是Hash碼解決的，關(guān)于HashMap的結(jié)構(gòu)和具體方法，我會在另外一篇博客中單獨列出。
TreeSet
當(dāng)我們new 一個TreeSet的時候，實際上是創(chuàng)建了一個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，也就是上一方法 } |
而用這個構(gòu)造器定義的TreeMap是沒有指定對比器的：
|
1
2
3
|
public TreeMap() { comparator = null; } |
讓我們來看一下TreeSet的add方法的全過程：
|
1
2
3
|
public boolean add(E e) { return m.put(e, PRESENT)==null; // 如果返回值為空則表示我們插入了一個新的元素，如果返回值為非空，則表明我們插入的元素已經(jīng)存在。 } |
實際上也就是向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為根節(jié)點 if (t == null) { // 如果根節(jié)點為空 compare(key, key); // type (and possibly null) check // 對自身做對比，如果有對比器就用對比器的規(guī)則進行對比，如果沒有，就用元素自身對比的規(guī)則進行對比。為0則相等。我覺得這波其實沒有意義，就是一個空的對比。 root = new Entry<>(key, value, null); // 新建一個空的根節(jié)點 size = 1; // 設(shè)置大小為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; 將父節(jié)點（最初是根節(jié)點）賦值給parent cmp = k.compareTo(t.key); //對我們要插入的key與根節(jié)點的keyj進行對比 if (cmp < 0) // 對比后值小于0，則表示我們插入的key小于根節(jié)點的key，就讓父節(jié)點往左走，并循環(huán)直至命中 t = t.left; else if (cmp > 0) // 對比后值大于0，則表示我們插入的key小于根節(jié)點的key，就讓父節(jié)點往右走，并循環(huán)直至命中 t = t.right; else //當(dāng)命中，用我們的值替換原有的值一次保證不插入重復(fù)的key，并返回替換后的對象 return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); // 如果沒有在樹中命中，則新生成一個樹節(jié)點此時parent的父節(jié)點已經(jīng)遍歷到了某個葉子節(jié)點。 if (cmp < 0) // 如果你的這個值是小于葉子節(jié)點的，則插入左邊，大于則插入右邊 parent.left = e; else parent.right = e; fixAfterInsertion(e); // 對整棵樹做平衡修正 size++; // size值加1表示我們插入了一個值 modCount++; // modCount也加1 return null; } |
整個過程就是：
1. 先查看根節(jié)點是否存在，如果不存在就直接吧這個節(jié)點放在根節(jié)點上。
2. 如果根節(jié)點存在就依順序向下查找，如果找到對應(yīng)的節(jié)點，就把該節(jié)點的值替換。
3. 如果遍歷到了葉子節(jié)點仍然沒有命中，那么就向葉子節(jié)點插入一個子節(jié)點，小就在左邊大就在右邊。
因為TreeSet插入的值都是空對象，只有key是有效的，key又是相等就覆蓋，所以不會重復(fù)
以上這篇JAVA HashSet和TreeSet 保證存入元素不會重復(fù)的操作就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/sinat_38232376/article/details/83655755
