WeakHashMap

Java中的四種引用

在JVM中，一個對象如果不再被使用就會被當(dāng)做垃圾給回收掉，判斷一個對象是否是垃圾，通常有兩種方法：引用計數(shù)法和可達(dá)性分析法。不管是哪一種方法判斷一個對象是否是垃圾的條件總是一個對象的引用是都沒有了。

JDK1.2 之后，Java 對引用的概念進(jìn)行了擴(kuò)充，將引用分為了：強(qiáng)引用、軟引用、弱引用、虛引用4 種。而我們的WeakHashMap就是基于弱引用。

強(qiáng)引用

如果一個對象具有強(qiáng)引用，它就不會被垃圾回收器回收。即使當(dāng)前內(nèi)存空間不足，JVM也不會回收它，而是拋出OutOfMemoryError錯誤，使程序異常終止。比如String str = new String("hello");這時候str就是一個強(qiáng)引用。

軟引用

內(nèi)存足夠的時候，軟引用對象不會被回收，只有在內(nèi)存不足時，系統(tǒng)則會回收軟引用對象，如果回收了軟引用對象之后仍然沒有足夠的內(nèi)存，才會拋出內(nèi)存溢出異常。

弱引用

如果一個對象具有弱引用，在垃圾回收時候，一旦發(fā)現(xiàn)弱引用對象，無論當(dāng)前內(nèi)存空間是否充足，都會將弱引用回收。

虛引用

如果一個對象具有虛引用，就相當(dāng)于沒有引用，在任何時候都有可能被回收。使用虛引用的目的就是為了得知對象被GC的時機(jī)，所以可以利用虛引用來進(jìn)行銷毀前的一些操作，比如說資源釋放等。

LinkedHashMap

LinkedHashMap它雖然增加了時間和空間上的開銷，但是通過維護(hù)一個運行于所有條目的雙向鏈表，LinkedHashMap保證了元素迭代的順序。該迭代順序可以是插入順序或者是訪問順序。

LinkedHashMap存儲結(jié)構(gòu)

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;
/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;
/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 *
 * @serial
 */
final boolean accessOrder;
/**
 * HashMap.Node subclass for normal LinkedHashMap entries.
 */
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

LinkedHashMap的結(jié)點結(jié)構(gòu)在繼承于HashMap的基礎(chǔ)上，增加了 before 和 after 屬性來確保插入順序。并且還維護(hù)了頭結(jié)點 head 和尾結(jié)點 tail 。在插入數(shù)據(jù)時，不但需要通過哈希算法進(jìn)行存儲，還需要通過 before 和 after 模擬雙向鏈表存儲結(jié)構(gòu)，進(jìn)行插入順序的維護(hù)。

LinkedHashMap所繼承于HashMap結(jié)點中的 next 屬性是用于維護(hù)HashMap中table數(shù)組中存儲的鏈表。而其獨有的 before 和 after 是模擬雙向鏈表進(jìn)行結(jié)點插入順序的維護(hù)

TreeMap

在前面我們通過HashMap中插入順序無序引出了LinkedHashMap的使用，但是我們又可以發(fā)現(xiàn)，這兩種存儲方式在迭代時均不是按照數(shù)據(jù)的大小順序進(jìn)行遍歷的，而當(dāng)我們需要將數(shù)據(jù)按照大小順序迭代時，就需要此時的TreeMap集合了。

• TreeMap是一個大小有序的key-value集合，底層結(jié)構(gòu)是紅黑樹，不允許插入null值。
• TreeMap采用紅黑樹的插入和刪除方法，通過比較key決定新元素的插入位置，也通過紅黑樹的有序性質(zhì)進(jìn)行刪除。
• TreeMap需要通過Comparable或Comparator進(jìn)行元素的排序。

TreeMap的存儲結(jié)構(gòu)

// Red-black mechanics
private static final boolean RED   = false;
private static final boolean BLACK = true;
/**
 * Node in the Tree.  Doubles as a means to pass key-value pairs back to
 * user (see Map.Entry).
 */
static final class Entry<K,V> implements Map.Entry<K,V> {
    //key,val是存儲的原始數(shù)據(jù)
    K key;
    V value;
    //定義了結(jié)點的左孩子
    Entry<K,V> left = null;
    //定義了結(jié)點的右孩子
    Entry<K,V> right = null;
    //通過該節(jié)點可以反過來往上找到自己的父親
    Entry<K,V> parent;
    //默認(rèn)情況下為黑色節(jié)點，可調(diào)整
    boolean color = BLACK;
    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}

黑樹規(guī)則特點：

1、節(jié)點分為紅色或者黑色；

2、根節(jié)點必為黑色；

3、葉子節(jié)點都為黑色，且為null；

4、連接紅色節(jié)點的兩個子節(jié)點都為黑色（紅黑樹不會出現(xiàn)相鄰的紅色節(jié)點）；

5、從任意節(jié)點出發(fā)，到其每個葉子節(jié)點的路徑中包含相同數(shù)量的黑色節(jié)點；

6、新加入到紅黑樹的節(jié)點為紅色節(jié)點；

紅黑樹自平衡基本操作：

1、變色：在不違反上述紅黑樹規(guī)則特點情況下，將紅黑樹某個node節(jié)點顏色由紅變黑，或者由黑變紅；

2、左旋：逆時針旋轉(zhuǎn)兩個節(jié)點，讓一個節(jié)點被其右子節(jié)點取代，而該節(jié)點成為右子節(jié)點的左子節(jié)點；

3、右旋：順時針旋轉(zhuǎn)兩個節(jié)點，讓一個節(jié)點被其左子節(jié)點取代，而該節(jié)點成為左子節(jié)點的右子節(jié)點；

Set

Set集合類似于一個罐子，程序可以依次把多個對象“丟進(jìn)”Set集合，而Set集合通常不能記住元素的添加順序。實際上Set就是Collection只是行為略有不同(Set不允許包含重復(fù)元素)。

Set集合不允許包含相同的元素，如果試圖把兩個相同元素加入同一個Set集合中，則添加操作失敗，add()方法返回false，且新元素不會被加入。

Set集合的特征

• Set集合，基礎(chǔ)自Collection。特征是插入無序，不可指定位置訪問。
• Set集合的實現(xiàn)類可說是基于Map集合去寫的。通過內(nèi)部封裝Map集合來實現(xiàn)的比如HashSet內(nèi)部封裝了HashMap。
• Set集合的數(shù)據(jù)庫不能重復(fù)（== 或 eqauls）的元素。
• Set集合的常用實現(xiàn)類有 HashSet、TreeSet。

HashSet

HashSet是Set接口的典型實現(xiàn)，大多數(shù)時候使用Set集合時就是使用這個實現(xiàn)類。HashSet按Hash算法來存儲集合中的元素，因此具有很好的存取和查找性能。底層數(shù)據(jù)結(jié)構(gòu)是哈希表。

HashSet特點

HashSet具有以下特點：

• 不能保證元素的排列順序，順序可能與添加順序不同，順序也可能發(fā)生變化；
• HashSet不是同步的；
• 集合元素值可以是null；

HashSet的存儲結(jié)構(gòu)

當(dāng)向HashSet集合中存入一個元素時，HashSet會調(diào)用該對象的hashCode方法來得到該對象的hashCode值，然后根據(jù)該hashCode值決定該對象在HashSet中的存儲位置。如果有兩個元素通過equals方法比較true，但它們的hashCode方法返回的值不相等，HashSet將會把它們存儲在不同位置，依然可以添加成功。

也就是說。HashSet集合判斷兩個元素的標(biāo)準(zhǔn)是兩個對象通過equals方法比較相等，并且兩個對象的hashCode方法返回值也相等。

即：靠元素重寫hashCode方法和equals方法來判斷兩個元素是否相等，如果相等則覆蓋原來的元素，以此來確保元素的唯一性。

TreeSet

TreeSet是SortedSet接口的實現(xiàn)類，TreeSet可以確保集合元素處于排序狀態(tài)。

存儲結(jié)構(gòu) TreeSet內(nèi)部實現(xiàn)的是紅黑樹，默認(rèn)整形排序為從小到大。

常用方法

與HashSet集合相比，TreeSet還提供了幾個額外方法：

• Comparator comparator()：如果TreeSet采用了定制順序，則該方法返回定制排序所使用的Comparator，如果TreeSet采用自然排序，則返回null；
• Object first()：返回集合中的第一個元素；
• Object last()：返回集合中的最后一個元素；
• Object lower(Object e)：返回指定元素之前的元素。
• Object higher(Object e)：返回指定元素之后的元素。
• SortedSet subSet（Object fromElement，Object toElement）：返回此Set的子集合，含頭不含尾；
• SortedSet headSet(Object toElement)：返回此Set的子集，由小于toElement的元素組成；
• SortedSet tailSet(Object fromElement)：返回此Set的子集，由大于fromElement的元素組成;

排序方式

TreeSet支持兩種排序方法：自然排序和定制排序，在默認(rèn)情況下，采用的是自然排序。

EnumSet

EnumSet類的特點：

• EnumSet是一個專門為枚舉類設(shè)計的集合類，EnumSet中的所有元素都必須是指定枚舉類型的枚舉值，該枚舉類型在創(chuàng)建EnumSet時顯式或隱式地指定。
• EnumSet的集合元素也是有序的，EnumSet以枚舉值在Enum類內(nèi)的定義順序來決定集合元素的順序。
• EnumSet在內(nèi)部以位向量的形式存儲，這種存儲形式非常緊湊、高效，因此EnumSet對象占用內(nèi)存很小，而且運行效率很好。
• EnumSet集合不允許加入null元素。

EnumSet類沒有暴露任何構(gòu)造器來創(chuàng)建該類的實例，EnumSet類提供了以下類方法來創(chuàng)建EnumSet對象。

• EnumSet allOf(Class elementType)：創(chuàng)建一個包含指定枚舉類里所有枚舉值的EnumSet集合。
• EnumSet complementOf(EnumSet s)：創(chuàng)建一個其元素類型與指定EnumSet里元素類型相同的EnumSet集合，新的集合里包含原集合不包含的枚舉值。
• EnumSet copyOf(Collection c)：使用一個普通集合來創(chuàng)建EnumSet集合；
• EnumSet copyOf(EnumSet s)：復(fù)制原集合；
• EnumSet noneOf(Class elementType)：創(chuàng)建一個元素類型為指定枚舉類型的空EnumSet；
• EnumSet of(E first，E...rest)：創(chuàng)建一個包含一個或多個枚舉值的EnumSet集合。傳入的枚舉值必須是同一枚舉類。
• EnumSet range(E from,E to)：創(chuàng)建一個包含從from到to枚舉值范圍所有枚舉值的EnumSet集合。

到此這篇關(guān)于Java中的WeakHashMap、LinkedHashMap、TreeMap與Set詳解的文章就介紹到這了,更多相關(guān)Java的WeakHashMap、TreeMap與Set內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論