Set是一種數(shù)據(jù)集合。它與List同樣繼承與Collection接口。

它與Collection接口中的方法基本一致，并沒有對Collection接口進(jìn)行功能進(jìn)行功能上的擴(kuò)充，只是比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)造器是怎么樣的：

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對象。

再讓我們來看一看插入操作：

public boolean add(E e) { return map.put(e, PRESENT)==null; }

add操作實際上是向map中插入了一條記錄，是以我們所要存的元素為key，以一個空對象為value的記錄。

到了這不實際上我們已經(jīng)能明白，set里的元素是不可能重復(fù)的，因為我們對hashMap同一個key進(jìn)行put，并不會生成新的記錄，而是對上一條記錄進(jìn)行覆蓋而已。但是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> 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é)果為：

false12311

那讓我們繼續(xù)看看，在put方法中java代碼又干了什么呢？（汗，感覺我從Set講到HashMap去了）

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

在下一層的代碼里，先對key本身進(jìn)行了一個轉(zhuǎn)化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值對應(yīng)的hash值。這里做了什么計算，我準(zhǔn)備放到另一篇博客里進(jìn)行討論，無論怎么樣，我們都知道對hashmap put相同的key值，不會重復(fù)的，這個是由HashMap的機(jī)制由hashCode也就是Hash碼解決的，關(guān)于HashMap的結(jié)構(gòu)和具體方法，我會在另外一篇博客中單獨列出。

TreeSet

當(dāng)我們new 一個TreeSet的時候，實際上是創(chuàng)建了一個TreeMap，并將這個TreeMap賦值給了TreeSet對象的m.

/** * 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是沒有指定對比器的：

public TreeMap() { comparator = null; }

讓我們來看一下TreeSet的add方法的全過程：

public boolean add(E e) { return m.put(e, PRESENT)==null; // 如果返回值為空則表示我們插入了一個新的元素，如果返回值為非空，則表明我們插入的元素已經(jīng)存在。 }

實際上也就是向TreeMap以你的要放入的元素為key， 空對象為value做一次put。

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ī)則進(jìn)行對比，如果沒有，就用元素自身對比的規(guī)則進(jìn)行對比。為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é)點）賦值給parentcmp = k.compareTo(t.key); //對我們要插入的key與根節(jié)點的keyj進(jìn)行對比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ǎng)。