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

它與Collection接口中的方法基本一致，并沒有對(duì)Collection接口進(jìn)行功能進(jìn)行功能上的擴(kuò)充，只是比Collection接口更嚴(yán)格了。與List不同的是，Set中的元素是無無需的，并且都以某種規(guī)則保證存入的元素不會(huì)出現(xiàn)重復(fù)。

它的特點(diǎn)也就是：

1. 元素不會(huì)出現(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)里實(shí)際上就包含了一個(gè)HashMap，而初始化HashSet就是給這個(gè)對(duì)象的Map賦值一個(gè)空HashMap對(duì)象。

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

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

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

到了這不實(shí)際上我們已經(jīng)能明白，set里的元素是不可能重復(fù)的，因?yàn)槲覀儗?duì)hashMap同一個(gè)key進(jìn)行put，并不會(huì)生成新的記錄，而是對(duì)上一條記錄進(jìn)行覆蓋而已。但是hashMap是如何判斷Key是否是同一個(gè)的呢？讓我們來看以下代碼

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); }

在下一層的代碼里，先對(duì)key本身進(jìn)行了一個(gè)轉(zhuǎn)化hash(key)，這個(gè)方法的源碼是：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

判斷key是否為空，如果為空就返回0，不然就對(duì)key值取hashCode并與h>>>16的值做異或操作，異或是一種位運(yùn)算，在此就不做解釋了。而>>>是一種位移操作， 在這個(gè)hash()方法里，實(shí)際上是生成了這個(gè)key值對(duì)應(yīng)的hash值。這里做了什么計(jì)算，我準(zhǔn)備放到另一篇博客里進(jìn)行討論，無論怎么樣，我們都知道對(duì)hashmap put相同的key值，不會(huì)重復(fù)的，這個(gè)是由HashMap的機(jī)制由hashCode也就是Hash碼解決的，關(guān)于HashMap的結(jié)構(gòu)和具體方法，我會(huì)在另外一篇博客中單獨(dú)列出。

TreeSet

當(dāng)我們new 一個(gè)TreeSet的時(shí)候，實(shí)際上是創(chuàng)建了一個(gè)TreeMap，并將這個(gè)TreeMap賦值給了TreeSet對(duì)象的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>()); // 將一個(gè)新生成的TreeMap空對(duì)象賦值給m，也就是上一方法 }

而用這個(gè)構(gòu)造器定義的TreeMap是沒有指定對(duì)比器的：

public TreeMap() { comparator = null; }

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

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

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

public V put(K key, V value) { Entry<K,V> t = root; // 定義t為根節(jié)點(diǎn) if (t == null) { // 如果根節(jié)點(diǎn)為空 compare(key, key); // type (and possibly null) check // 對(duì)自身做對(duì)比，如果有對(duì)比器就用對(duì)比器的規(guī)則進(jìn)行對(duì)比，如果沒有，就用元素自身對(duì)比的規(guī)則進(jìn)行對(duì)比。為0則相等。我覺得這波其實(shí)沒有意義，就是一個(gè)空的對(duì)比。 root = new Entry<>(key, value, null); // 新建一個(gè)空的根節(jié)點(diǎn) size = 1; // 設(shè)置大小為1 modCount++; //對(duì)0做+1 return null; // 返回空值，表示插入成功。 } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; // 用本treeMap的對(duì)比器對(duì)cpr賦值 if (cpr != null) { // 如果定義的對(duì)比器不為空（在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 { // 如果對(duì)比器為空（在這種情況下是為空的） if (key == null) // 如果key為空就拋出錯(cuò)誤throw new NullPointerException(); @SuppressWarnings('unchecked') Comparable<? super K> k = (Comparable<? super K>) key;// 生成可比較的對(duì)象Comparable do {parent = t; 將父節(jié)點(diǎn)（最初是根節(jié)點(diǎn)）賦值給parentcmp = k.compareTo(t.key); //對(duì)我們要插入的key與根節(jié)點(diǎn)的keyj進(jìn)行對(duì)比if (cmp < 0) // 對(duì)比后值小于0，則表示我們插入的key小于根節(jié)點(diǎn)的key，就讓父節(jié)點(diǎn)往左走，并循環(huán)直至命中 t = t.left;else if (cmp > 0) // 對(duì)比后值大于0，則表示我們插入的key小于根節(jié)點(diǎn)的key，就讓父節(jié)點(diǎn)往右走，并循環(huán)直至命中 t = t.right;else //當(dāng)命中，用我們的值替換原有的值一次保證不插入重復(fù)的key，并返回替換后的對(duì)象 return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); // 如果沒有在樹中命中，則新生成一個(gè)樹節(jié)點(diǎn)此時(shí)parent的父節(jié)點(diǎn)已經(jīng)遍歷到了某個(gè)葉子節(jié)點(diǎn)。 if (cmp < 0) // 如果你的這個(gè)值是小于葉子節(jié)點(diǎn)的，則插入左邊，大于則插入右邊 parent.left = e; else parent.right = e; fixAfterInsertion(e); // 對(duì)整棵樹做平衡修正 size++; // size值加1表示我們插入了一個(gè)值 modCount++; // modCount也加1 return null; }

整個(gè)過程就是：

1. 先查看根節(jié)點(diǎn)是否存在，如果不存在就直接吧這個(gè)節(jié)點(diǎn)放在根節(jié)點(diǎn)上。

2. 如果根節(jié)點(diǎn)存在就依順序向下查找，如果找到對(duì)應(yīng)的節(jié)點(diǎn)，就把該節(jié)點(diǎn)的值替換。

3. 如果遍歷到了葉子節(jié)點(diǎn)仍然沒有命中，那么就向葉子節(jié)點(diǎn)插入一個(gè)子節(jié)點(diǎn)，小就在左邊大就在右邊。

因?yàn)門reeSet插入的值都是空對(duì)象，只有key是有效的，key又是相等就覆蓋，所以不會(huì)重復(fù)

以上這篇JAVA HashSet和TreeSet 保證存入元素不會(huì)重復(fù)的操作就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持好吧啦網(wǎng)。