本篇內(nèi)容介紹了“Java集合HashSet,TreeSet與LinkedHashSet怎么使用”的有關(guān)知識,在實際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學習一下如何處理這些情況吧!希望大家仔細閱讀,能夠?qū)W有所成!
成都創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供奎文網(wǎng)站建設(shè)、奎文做網(wǎng)站、奎文網(wǎng)站設(shè)計、奎文網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、奎文企業(yè)網(wǎng)站模板建站服務(wù),十載奎文做網(wǎng)站經(jīng)驗,不只是建網(wǎng)站,更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable
HashSet繼承AbstractSet類,實現(xiàn)Set、Cloneable、Serializable接口。其中AbstractSet提供 Set 接口的骨干實現(xiàn),從而最大限度地減少了實現(xiàn)此接口所需的工作。 ==Set接口是一種不包括重復(fù)元素的Collection,它維持它自己的內(nèi)部排序,所以隨機訪問沒有任何意義。==
本文基于1.8jdk進行源碼分析。
基本屬性
基于HashMap實現(xiàn),底層使用HashMap保存所有元素
private transient HashMap<E,Object> map; //定義一個Object對象作為HashMap的value private static final Object PRESENT = new Object();
構(gòu)造函數(shù)
/** * 默認構(gòu)造函數(shù) * 初始化一個空的HashMap,并使用默認初始容量為16和加載因子0.75。 */ public HashSet() { map = new HashMap<>(); } /** * 構(gòu)造一個包含指定 collection 中的元素的新 set。 */ public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } /** * 構(gòu)造一個新的空 set,其底層 HashMap 實例具有指定的初始容量和指定的加載因子 */ public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } /** * 構(gòu)造一個新的空 set,其底層 HashMap 實例具有指定的初始容量和默認的加載因子(0.75)。 */ public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } /** * 在API中我沒有看到這個構(gòu)造函數(shù),今天看源碼才發(fā)現(xiàn)(原來訪問權(quán)限為包權(quán)限,不對外公開的) * 以指定的initialCapacity和loadFactor構(gòu)造一個新的空鏈接哈希集合。 * dummy 為標識 該構(gòu)造函數(shù)主要作用是對LinkedHashSet起到一個支持作用 */ HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } 從構(gòu)造函數(shù)中可以看出HashSet所有的構(gòu)造都是構(gòu)造出一個新的HashMap,其中最后一個構(gòu)造函數(shù),為包訪問權(quán)限是不對外公開,僅僅只在使用LinkedHashSet時才會發(fā)生作用。
既然HashSet是基于HashMap,那么對于HashSet而言,其方法的實現(xiàn)過程是非常簡單的。
public Iterator<E> iterator() { return map.keySet().iterator(); }
iterator()方法返回對此 set 中元素進行迭代的迭代器。返回元素的順序并不是特定的。
底層調(diào)用HashMap的keySet返回所有的key,這點反應(yīng)了HashSet中的所有元素都是保存在HashMap的key中,value則是使用的PRESENT對象,該對象為static final。
public int size() { return map.size(); } size()返回此 set 中的元素的數(shù)量(set 的容量)。底層調(diào)用HashMap的size方法,返回HashMap容器的大小。 public boolean isEmpty() { return map.isEmpty(); } isEmpty(),判斷HashSet()集合是否為空,為空返回 true,否則返回false。 public boolean contains(Object o) { return map.containsKey(o); } public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } //最終調(diào)用該方法進行節(jié)點查找 final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //先檢查桶的頭結(jié)點是否存在 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; //不是頭結(jié)點,則遍歷鏈表,如果是樹節(jié)點則使用樹節(jié)點的方法遍歷,直到找到,或者為null if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
contains(),判斷某個元素是否存在于HashSet()中,存在返回true,否則返回false。更加確切的講應(yīng)該是要滿足這種關(guān)系才能返回true:(o==null ? e==null : o.equals(e))。底層調(diào)用containsKey判斷HashMap的key值是否為空。
public boolean add(E e) { return map.put(e, PRESENT)==null; } public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } map的put方法: final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //確認初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //如果桶為空,直接插入新元素,也就是entry if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //如果沖突,分為三種情況 //key相等時讓舊entry等于新entry即可 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //紅黑樹情況 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //如果key不相等,則連成鏈表 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
這里注意一點,hashset只是不允許重復(fù)的元素加入,而不是不允許元素連成鏈表,因為只要key的equals方法判斷為true時它們是相等的,此時會發(fā)生value的替換,因為所有entry的value一樣,所以和沒有插入時一樣的。
而當兩個hashcode相同但key不相等的entry插入時,仍然會連成一個鏈表,長度超過8時依然會和hashmap一樣擴展成紅黑樹,看完源碼之后筆者才明白自己之前理解錯了。所以看源碼還是蠻有好處的。hashset基本上就是使用hashmap的方法再次實現(xiàn)了一遍而已,只不過value全都是同一個object,讓你以為相同元素沒有插入,事實上只是value替換成和原來相同的值而已。
當add方法發(fā)生沖突時,如果key相同,則替換value,如果key不同,則連成鏈表。
add()如果此 set 中尚未包含指定元素,則添加指定元素。如果此Set沒有包含滿足(e==null ? e2==null : e.equals(e2)) 的e2時,則將e2添加到Set中,否則不添加且返回false。
由于底層使用HashMap的put方法將key = e,value=PRESENT構(gòu)建成key-value鍵值對,當此e存在于HashMap的key中,則value將會覆蓋原有value,但是key保持不變,所以如果將一個已經(jīng)存在的e元素添加中HashSet中,新添加的元素是不會保存到HashMap中,所以這就滿足了HashSet中元素不會重復(fù)的特性。
public boolean remove(Object o) { return map.remove(o)==PRESENT; }
remove如果指定元素存在于此 set 中,則將其移除。底層使用HashMap的remove方法刪除指定的Entry。
public void clear() { map.clear(); }
clear從此 set 中移除所有元素。底層調(diào)用HashMap的clear方法清除所有的Entry。
public Object clone() { try { HashSet<E> newSet = (HashSet<E>) super.clone(); newSet.map = (HashMap<E, Object>) map.clone(); return newSet; } catch (CloneNotSupportedException e) { throw new InternalError(); } }
clone返回此 HashSet 實例的淺表副本:并沒有復(fù)制這些元素本身。
后記:
由于HashSet底層使用了HashMap實現(xiàn),使其的實現(xiàn)過程變得非常簡單,如果你對HashMap比較了解,那么HashSet簡直是小菜一碟。有兩個方法對HashMap和HashSet而言是非常重要的,下篇將詳細講解hashcode和equals。
與HashSet是基于HashMap實現(xiàn)一樣,TreeSet同樣是基于TreeMap實現(xiàn)的。在《Java提高篇(二七)-----TreeMap》中LZ詳細講解了TreeMap實現(xiàn)機制,如果客官詳情看了這篇博文或者多TreeMap有比較詳細的了解,那么TreeSet的實現(xiàn)對您是喝口水那么簡單。
我們知道TreeMap是一個有序的二叉樹,那么同理TreeSet同樣也是一個有序的,它的作用是提供有序的Set集合。通過源碼我們知道TreeSet基礎(chǔ)AbstractSet,實現(xiàn)NavigableSet、Cloneable、Serializable接口。
其中AbstractSet提供 Set 接口的骨干實現(xiàn),從而最大限度地減少了實現(xiàn)此接口所需的工作。
NavigableSet是擴展的 SortedSet,具有了為給定搜索目標報告最接近匹配項的導(dǎo)航方法,這就意味著它支持一系列的導(dǎo)航方法。比如查找與指定目標最匹配項。Cloneable支持克隆,Serializable支持序列化。
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
同時在TreeSet中定義了如下幾個變量。
private transient NavigableMap<E,Object> m; //PRESENT會被當做Map的value與key構(gòu)建成鍵值對 private static final Object PRESENT = new Object();
其構(gòu)造方法:
//默認構(gòu)造方法,根據(jù)其元素的自然順序進行排序 public TreeSet() { this(new TreeMap<E,Object>()); } //構(gòu)造一個包含指定 collection 元素的新 TreeSet,它按照其元素的自然順序進行排序。 public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } //構(gòu)造一個新的空 TreeSet,它根據(jù)指定比較器進行排序。 public TreeSet(Collection<? extends E> c) { this(); addAll(c); } //構(gòu)造一個與指定有序 set 具有相同映射關(guān)系和相同排序的新 TreeSet。 public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); } TreeSet(NavigableMap<E,Object> m) { this.m = m; }
二、TreeSet主要方法
1、add:將指定的元素添加到此 set(如果該元素尚未存在于 set 中)。
public boolean add(E e) { return m.put(e, PRESENT)==null; } public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { //空樹時,判斷節(jié)點是否為空 compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; //非空樹,根據(jù)傳入比較器進行節(jié)點的插入位置查找 if (cpr != null) { do { parent = t; //節(jié)點比根節(jié)點小,則找左子樹,否則找右子樹 cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; //如果key的比較返回值相等,直接更新值(一般compareto相等時equals方法也相等) else return t.setValue(value); } while (t != null); } else { //如果沒有傳入比較器,則按照自然排序 if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } //查找的節(jié)點為空,直接插入,默認為紅節(jié)點 Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; //插入后進行紅黑樹調(diào)整 fixAfterInsertion(e); size++; modCount++; return null; }
2、get:獲取元素
public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); }
該方法與put的流程類似,只不過是把插入換成了查找
3、ceiling:返回此 set 中大于等于給定元素的最小元素;如果不存在這樣的元素,則返回 null。
public E ceiling(E e) { return m.ceilingKey(e); }
4、clear:移除此 set 中的所有元素。
public void clear() { m.clear(); }
5、clone:返回 TreeSet 實例的淺表副本。屬于淺拷貝。
public Object clone() { TreeSet<E> clone = null; try { clone = (TreeSet<E>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } clone.m = new TreeMap<>(m); return clone; }
6、comparator:返回對此 set 中的元素進行排序的比較器;如果此 set 使用其元素的自然順序,則返回 null。
public Comparator<? super E> comparator() { return m.comparator(); }
7、contains:如果此 set 包含指定的元素,則返回 true。
public boolean contains(Object o) { return m.containsKey(o); }
8、descendingIterator:返回在此 set 元素上按降序進行迭代的迭代器。
public Iterator<E> descendingIterator() { return m.descendingKeySet().iterator(); }
9、descendingSet:返回此 set 中所包含元素的逆序視圖。
public NavigableSet<E> descendingSet() { return new TreeSet<>(m.descendingMap()); }
10、first:返回此 set 中當前第一個(最低)元素。
public E first() { return m.firstKey(); }
11、floor:返回此 set 中小于等于給定元素的最大元素;如果不存在這樣的元素,則返回 null。
public E floor(E e) { return m.floorKey(e); }
12、headSet:返回此 set 的部分視圖,其元素嚴格小于 toElement。
public SortedSet<E> headSet(E toElement) { return headSet(toElement, false); }
13、higher:返回此 set 中嚴格大于給定元素的最小元素;如果不存在這樣的元素,則返回 null。
public E higher(E e) { return m.higherKey(e); }
14、isEmpty:如果此 set 不包含任何元素,則返回 true。
public boolean isEmpty() { return m.isEmpty(); }
15、iterator:返回在此 set 中的元素上按升序進行迭代的迭代器。
public Iterator<E> iterator() { return m.navigableKeySet().iterator(); }
16、last:返回此 set 中當前最后一個(最高)元素。
public E last() { return m.lastKey(); }
17、lower:返回此 set 中嚴格小于給定元素的最大元素;如果不存在這樣的元素,則返回 null。
public E lower(E e) { return m.lowerKey(e); }
18、pollFirst:獲取并移除第一個(最低)元素;如果此 set 為空,則返回 null。
public E pollFirst() { Map.Entry<E,?> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); }
19、pollLast:獲取并移除最后一個(最高)元素;如果此 set 為空,則返回 null。
public E pollLast() { Map.Entry<E,?> e = m.pollLastEntry(); return (e == null) ? null : e.getKey(); }
20、remove:將指定的元素從 set 中移除(如果該元素存在于此 set 中)。
public boolean remove(Object o) { return m.remove(o)==PRESENT; }
該方法與put類似,只不過把插入換成了刪除,并且要進行刪除后調(diào)整
21、size:返回 set 中的元素數(shù)(set 的容量)。
public int size() { return m.size(); }
22、subSet:返回此 set 的部分視圖
/** * 返回此 set 的部分視圖,其元素范圍從 fromElement 到 toElement。 */ public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new TreeSet<>(m.subMap(fromElement, fromInclusive, toElement, toInclusive)); } /** * 返回此 set 的部分視圖,其元素從 fromElement(包括)到 toElement(不包括)。 */ public SortedSet<E> subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); }
23、tailSet:返回此 set 的部分視圖
/** * 返回此 set 的部分視圖,其元素大于(或等于,如果 inclusive 為 true)fromElement。 */ public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { return new TreeSet<>(m.tailMap(fromElement, inclusive)); } /** * 返回此 set 的部分視圖,其元素大于等于 fromElement。 */ public SortedSet<E> tailSet(E fromElement) { return tailSet(fromElement, true); }
由于TreeSet是基于TreeMap實現(xiàn)的,所以如果我們對treeMap有了一定的了解,對TreeSet那是小菜一碟,我們從TreeSet中的源碼可以看出,其實現(xiàn)過程非常簡單,幾乎所有的方法實現(xiàn)全部都是基于TreeMap的。
LinkedHashSet是HashSet的一個“擴展版本”,HashSet并不管什么順序,不同的是LinkedHashSet會維護“插入順序”。HashSet內(nèi)部使用HashMap對象來存儲它的元素,而LinkedHashSet內(nèi)部使用LinkedHashMap對象來存儲和處理它的元素。這篇文章,我們將會看到LinkedHashSet內(nèi)部是如何運作的及如何維護插入順序的。
我們首先著眼LinkedHashSet的構(gòu)造函數(shù)。在LinkedHashSet類中一共有4個構(gòu)造函數(shù)。這些構(gòu)造函數(shù)都只是簡單地調(diào)用父類構(gòu)造函數(shù)(如HashSet類的構(gòu)造函數(shù))。 下面看看LinkedHashSet的構(gòu)造函數(shù)是如何定義的。
//Constructor - 1 public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); //Calling super class constructor } //Constructor - 2 public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); //Calling super class constructor } //Constructor - 3 public LinkedHashSet() { super(16, .75f, true); //Calling super class constructor } //Constructor - 4 public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); //Calling super class constructor addAll(c); }
在上面的代碼片段中,你可能注意到4個構(gòu)造函數(shù)調(diào)用的是同一個父類的構(gòu)造函數(shù)。這個構(gòu)造函數(shù)(父類的,譯者注)是一個包內(nèi)私有構(gòu)造函數(shù)(見下面的代碼,HashSet的構(gòu)造函數(shù)沒有使用public公開,譯者注),它只能被LinkedHashSet使用。
這個構(gòu)造函數(shù)需要初始容量,負載因子和一個boolean類型的啞值(沒有什么用處的參數(shù),作為標記,譯者注)等參數(shù)。這個啞參數(shù)只是用來區(qū)別這個構(gòu)造函數(shù)與HashSet的其他擁有初始容量和負載因子參數(shù)的構(gòu)造函數(shù),下面是這個構(gòu)造函數(shù)的定義,
HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }
顯然,這個構(gòu)造函數(shù)內(nèi)部初始化了一個LinkedHashMap對象,這個對象恰好被LinkedHashSet用來存儲它的元素。
LinkedHashSet并沒有自己的方法,所有的方法都繼承自它的父類HashSet,因此,對LinkedHashSet的所有操作方式就好像對HashSet操作一樣。
唯一的不同是內(nèi)部使用不同的對象去存儲元素。在HashSet中,插入的元素是被當做HashMap的鍵來保存的,而在LinkedHashSet中被看作是LinkedHashMap的鍵。
這些鍵對應(yīng)的值都是常量PRESENT(PRESENT是HashSet的靜態(tài)成員變量,譯者注)。
LinkedHashSet使用LinkedHashMap對象來存儲它的元素,插入到LinkedHashSet中的元素實際上是被當作LinkedHashMap的鍵保存起來的。
LinkedHashMap的每一個鍵值對都是通過內(nèi)部的靜態(tài)類Entry<K, V>實例化的。這個 Entry<K, V>類繼承了HashMap.Entry類。
這個靜態(tài)類增加了兩個成員變量,before和after來維護LinkedHasMap元素的插入順序。這兩個成員變量分別指向前一個和后一個元素,這讓LinkedHashMap也有類似雙向鏈表的表現(xiàn)。
private static class Entry<K,V> extends HashMap.Entry<K,V> { // These fields comprise the doubly linked list used for iteration. Entry<K,V> before, after; Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); } }
從上面代碼看到的LinkedHashMap內(nèi)部類的前面兩個成員變量——before和after負責維護LinkedHashSet的插入順序。LinkedHashMap定義的成員變量header保存的是 這個雙向鏈表的頭節(jié)點。header的定義就像下面這樣,
接下來看一個例子就知道LinkedHashSet內(nèi)部是如何工作的了。
public class LinkedHashSetExample { public static void main(String[] args) { //Creating LinkedHashSet LinkedHashSet<String> set = new LinkedHashSet<String>(); //Adding elements to LinkedHashSet set.add("BLUE"); set.add("RED"); set.add("GREEN"); set.add("BLACK"); } }
“Java集合HashSet,TreeSet與LinkedHashSet怎么使用”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實用文章!
分享名稱:Java集合HashSet,TreeSet與LinkedHashSet怎么使用
網(wǎng)站路徑:http://jinyejixie.com/article0/jopdoo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供電子商務(wù)、關(guān)鍵詞優(yōu)化、網(wǎng)站營銷、網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計公司、手機網(wǎng)站建設(shè)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)