WeakHashMap

Java中的四種引用

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

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

強(qiáng)引用

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

軟引用

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

弱引用

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

虛引用

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

LinkedHashMap

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

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

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

TreeMap

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

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

TreeMap的存儲(chǔ)結(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是存儲(chǔ)的原始數(shù)據(jù)
    K key;
    V value;
    //定義了結(jié)點(diǎn)的左孩子
    Entry<K,V> left = null;
    //定義了結(jié)點(diǎn)的右孩子
    Entry<K,V> right = null;
    //通過(guò)該節(jié)點(diǎn)可以反過(guò)來(lái)往上找到自己的父親
    Entry<K,V> parent;
    //默認(rèn)情況下為黑色節(jié)點(diǎn)，可調(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;
    }
}

黑樹(shù)規(guī)則特點(diǎn)：

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

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

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

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

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

6、新加入到紅黑樹(shù)的節(jié)點(diǎn)為紅色節(jié)點(diǎn)；

紅黑樹(shù)自平衡基本操作：

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

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

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

Set

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

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

Set集合的特征

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

HashSet

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

HashSet特點(diǎn)

HashSet具有以下特點(diǎn)：

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

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

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

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

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

TreeSet

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

存儲(chǔ)結(jié)構(gòu) TreeSet內(nèi)部實(shí)現(xiàn)的是紅黑樹(shù)，默認(rèn)整形排序?yàn)閺男〉酱蟆?/p>

常用方法

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

• Comparator comparator()：如果TreeSet采用了定制順序，則該方法返回定制排序所使用的Comparator，如果TreeSet采用自然排序，則返回null；
• Object first()：返回集合中的第一個(gè)元素；
• Object last()：返回集合中的最后一個(gè)元素；
• 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類的特點(diǎn)：

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

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

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

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

最新評(píng)論