linkedset使用技巧？從源碼的角度來對(duì)LinkedHashSet尋根問底！先一覽LinkedHashSet類中的所有方法，發(fā)現(xiàn)就是一些構(gòu)造方法，沒什么特別的。。spliterator方法也只是個(gè)

linkedset使用技巧？

從源碼的角度來對(duì)LinkedHashSet尋根問底！

先一覽LinkedHashSet類中的所有方法，發(fā)現(xiàn)就是一些構(gòu)造方法，沒什么特別的。。spliterator方法也只是個(gè)迭代器！

從構(gòu)造器中的super方法點(diǎn)過去可得見端倪，原來構(gòu)造器中的父級(jí)構(gòu)造器使用的是LinkedHashMap進(jìn)行實(shí)例化，那么LinkedHashSet的特性勢(shì)必跟LinkedHashMap息息相關(guān)，換句話說LinkedHashSet的輸出有序來自于LinkedHashMap；

下面對(duì)LinkedHashMap進(jìn)行詳細(xì)分析：

LinkedHashMap繼承HashMap，實(shí)現(xiàn)了Map，很明顯LinkedHashMap也算是HashMap，還保存了數(shù)組 鏈表的結(jié)構(gòu)，至于有序的原因肯定不會(huì)是因?yàn)镸ap接口和繼承HashMap，也就是說LinkedHashMap的有序，肯定就是在LinkedHashMap類中實(shí)現(xiàn)的；

HashMap的底層數(shù)據(jù)結(jié)構(gòu)是使用數(shù)組中的位置作為桶，每個(gè)桶中放置一份鏈表（或者紅黑樹），而hashCod

Sardine調(diào)用put方法的底層實(shí)現(xiàn)怎么做？

hashmap put方法的實(shí)現(xiàn)：

12345678910111213141516171819 首先對(duì)key做null檢查。如果key是null，會(huì)被存儲(chǔ)到table[0]，因?yàn)閚ull的hash值總是0。

key的hashcode()方被調(diào)用，然后計(jì)算hash值。hash值用來找到存儲(chǔ)Entry對(duì)象的數(shù)組的索引。有時(shí)候hash函數(shù)可能寫的很不好，所以JDK的設(shè)計(jì)者添加了另一個(gè)叫做hash()的方法，它接收剛才計(jì)算的hash值作為參數(shù)。如果你想了解更多關(guān)于hash()函數(shù)的東西，可以參考：hashmap中的hash和indexFor方法

indexFor(hash,table.length)用來計(jì)算在table數(shù)組中存儲(chǔ)Entry對(duì)象的精確的索引。

在我們的例子中已經(jīng)看到，如果兩個(gè)key有相同的hash值(也叫)，他們會(huì)以鏈表的形式來存儲(chǔ)。所以，這里我們就迭代鏈表。

· 如果在剛才計(jì)算出來的索引位置沒有元素，直接把Entry對(duì)象放在那個(gè)索引上。

· 如果索引上有元素，然后會(huì)進(jìn)行迭代，一直到Entry-gtnext是null。當(dāng)前的Entry對(duì)象變成鏈表的下一個(gè)節(jié)點(diǎn)。

· 如果我們?cè)俅畏湃胪瑯拥膋ey會(huì)怎樣呢？邏輯上，它應(yīng)該替換老的value。事實(shí)上，它確實(shí)是這么做的。在迭代的過程中，會(huì)調(diào)用equals()方法來檢查key的相等性(key.equals(k))，如果這個(gè)方法返回true，它就會(huì)用當(dāng)前Entry的value來替換之前的value。

2.hashMap get方法的解析：

1234567 當(dāng)你傳遞一個(gè)key從hashmap總獲取value的時(shí)候：

對(duì)key進(jìn)行null檢查。如果key是null，table[0]這個(gè)位置的元素將被返回。

key的hashcode()方法被調(diào)用，然后計(jì)算hash值。

indexFor(hash,table.length)用來計(jì)算要獲取的Entry對(duì)象在table數(shù)組中的精確的位置，使用剛才計(jì)算的hash值。

在獲取了table數(shù)組的索引之后，會(huì)迭代鏈表，調(diào)用equals()方法檢查key的相等性，如果equals()方法返回true，get方法返回Entry對(duì)象的value，否則，返回null。

3.要牢記以下關(guān)鍵點(diǎn)：

· HashMap有一個(gè)叫做Entry的內(nèi)部類，它用來存儲(chǔ)key-value對(duì)?！?上面的Entry對(duì)象是存儲(chǔ)在一個(gè)叫做table的Entry數(shù)組中?！?table的索引在邏輯上叫做“桶”(bucket)，它存儲(chǔ)了鏈表的第一個(gè)元素。· key的hashcode()方法用來找到Entry對(duì)象所在的桶?！?如果兩個(gè)key有相同的hash值，他們會(huì)被放在table數(shù)組的同一個(gè)桶里面?！?key的equals()方法用來確保key的唯一性?！?value對(duì)象的equals()和hashcode()方法根本一點(diǎn)用也沒有。簡單地說，HashMap 在底層將 key-value 當(dāng)成一個(gè)整體進(jìn)行處理，這個(gè)整體就是一個(gè) Entry 對(duì)象。HashMap 底層采用一個(gè) Entry[] 數(shù)組來保存所有的 key-value 對(duì)，當(dāng)需要存儲(chǔ)一個(gè) Entry 對(duì)象時(shí)，會(huì)根據(jù)hash算法來決定其在數(shù)組中的存儲(chǔ)位置，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲(chǔ)位置；當(dāng)需要取出一個(gè)Entry時(shí)， 也會(huì)根據(jù)hash算法找到其在數(shù)組中的存儲(chǔ)位置，再根據(jù)equals方法從該位置上的鏈表中取出該Entry。

HashMap的resize（rehash）

當(dāng)hashmap中的元素越來越多的時(shí)候，碰撞的幾率也就越來越高（因?yàn)閿?shù)組的長度是固定的），所以為了提高查詢的效率，就要對(duì)hashmap的數(shù)組進(jìn)行擴(kuò)容，數(shù)組擴(kuò)容這個(gè)操作也會(huì)出現(xiàn)在ArrayList中，所以這是一個(gè)通用的操作，很多人對(duì)它的性能表示過懷疑，不過想想我們的“均攤”原理，就釋然了，而在hashmap數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去，這就是resize。 那么hashmap什么時(shí)候進(jìn)行擴(kuò)容呢？當(dāng)hashmap中的元素個(gè)數(shù)超過數(shù)組大小*loadFactor時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值為0.75，也就是說，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)hashmap中元素個(gè)數(shù)超過16*0.7512的時(shí)候，就把數(shù)組的大小擴(kuò)展為2*1632，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，而這是一個(gè)非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知hashmap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高h(yuǎn)ashmap的性能。比如說，我們有1000個(gè)元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適，不過上面annegu已經(jīng)說過，即使是1000，hashmap也自動(dòng)會(huì)將其設(shè)置為1024。 但是new HashMap(1024)還不是更合適的，因?yàn)?.75*1000 lt 1000, 也就是說為了讓0.75 * size gt 1000, 我們必須這樣new HashMap(2048)才最合適，既考慮了amp的問題，也避免了resize的問題。