溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章運用簡單易懂的例子給大家介紹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 <tt>HashMap</tt> 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> 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);
}
}
}結果為：
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<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是沒有指定對比器的：
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<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 實現保證存入元素不會重復就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
