HashSet哈希鏈表

Map、Set集合存放是無序的，然而LinkedHashSet和LinkedHashMap等集合卻有序

原因：LinkedHashSet與LinkedHashMap底層是通過雙向鏈表來實(shí)現(xiàn)排序的。

雙向鏈表里面的數(shù)據(jù)在邏輯上的存儲是連續(xù)的，連續(xù)自然也就有順序。

有序的原因關(guān)鍵在LinkedHashMap的Node 節(jié)點(diǎn)上。

LinkedHashMap 繼承自HashMap 并且實(shí)現(xiàn)了Map接口。

源碼如下：

/**
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.Entry 繼承自HashMap.Node 除了Node 本身有的幾個屬性外，額外增加了before after 用于指向前一個Entry 后一個Entry。

也就是說，元素之間維持著一條總的鏈表數(shù)據(jù)結(jié)構(gòu)。正式因?yàn)檫@個鏈表才保證了LinkedHashMap的有序性。

LinkedHashSet集合也是根據(jù)元素hashCode值來決定元素存儲位置，但它同時使用鏈表維護(hù)元素的次序，這樣使得元素看起來是以插入的順序保存的。

也就是說，當(dāng)遍歷LinkedHashSet集合里元素時，HashSet將會按元素的添加順序來訪問集合里的元素，因此LinkedHashSet可以保證元素按插入順序輸出。

而Set對每個對象只接受一次，里面的值不允許重復(fù)，是無序的數(shù)據(jù)結(jié)構(gòu)；

LinkeHashSet是set集合的一個實(shí)現(xiàn)，具有set集合不重復(fù)的特點(diǎn)，同時具有可預(yù)測的迭代順序，即輸入順序。

這種雙鏈表的結(jié)構(gòu)一條用于儲存元素，一條用于記錄順序。

而Map Set集合內(nèi)是單鏈表或稀疏數(shù)組，各元素之間并沒有維持一條總的鏈表結(jié)構(gòu)，所以Map和Set是無序的

LinkedHashSet的4種構(gòu)造函數(shù):

1. 第一種構(gòu)造函數(shù)初始化一個空的LinkedHashSet： LinkedHashSet( )；
2. 第二種構(gòu)造函數(shù)使用Collection元素集初始化LinkedHashSet： LinkedHashSet(Collection c)；
3. 第三種構(gòu)造函數(shù)用給定的容量初始化LinkedHashSet： LinkedHashSet(int capacity)；
4. 第四種構(gòu)造函數(shù)通過傳入的容量和填充比初始化LinkedHashSet： LinkedHashSet(int capacity, float fillRatio)；

運(yùn)行結(jié)果：

這兩斷代碼我們可以得出：LinkedHashSet 底層采用雙向鏈表實(shí)現(xiàn)，可以保證元素的插入順序，又因?yàn)槭荋ashSet的子類，所以插入的元素不能重復(fù)。

到此這篇關(guān)于淺談Java中的LinkedHashSet哈希鏈表的文章就介紹到這了,更多相關(guān)Java的LinkedHashSet內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論