現(xiàn)在2021年的12月，這個(gè)年頭也馬上要結(jié)束了，哎，時(shí)間過(guò)得可以真快呀！

敬頌冬綏

• 
  

• 這一年也經(jīng)歷了很多事情，比如：

• 工作上：換了3家工作，工作道路崎嶇彎折。

• 技術(shù)上也在一點(diǎn)一點(diǎn)的進(jìn)步和成長(zhǎng)

• 生活上也是一步一步的按照計(jì)劃中做

• 愛(ài)情上，還是一樣沒(méi)啥進(jìn)展，沒(méi)有對(duì)象

• 人際關(guān)系上，還行只要我能幫忙的我都去了

• 職場(chǎng)上，上半年不是那么的順利，但是我還是咬住牙挺過(guò)來(lái)了，下半年在職場(chǎng)上一切正常，按部就班的工作

• 交流上，還是那么的耿直，有啥話說(shuō)啥話，多嘴，口無(wú)遮攔導(dǎo)致有時(shí)自己的無(wú)意間得罪了對(duì)方，這方面還的學(xué)習(xí)學(xué)習(xí)

• 孝敬和態(tài)度上，對(duì)父母也沒(méi)啥太大的幫助，只要不要給他們添麻煩就行，自己生活，養(yǎng)活自己就可以了

• 在對(duì)待弟弟的事情上，也多了一些教導(dǎo)和督促，來(lái)自媽媽的嘮叨，身上有多了一份責(zé)任。

  
  

圖片展示

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?一年的記錄：

? ? ? ? 圖片以2021整年為導(dǎo)向，突顯出我什么時(shí)候在干了什么有趣的事情

01

LinkedHashSet and LinkedHashMap

如果你已看過(guò)前面關(guān)于HashSet和HashMap，以及TreeSet和TreeMap的講解，一定能夠想到本文將要講解的LinkedHashSet和LinkedHashMap其實(shí)也是一回事。LinkedHashSet和LinkedHashMap在Java里也有著相同的實(shí)現(xiàn)，前者僅僅是對(duì)后者做了一層包裝，也就是說(shuō)LinkedHashSet里面有一個(gè)LinkedHashMap（適配器模式）**。因此本文將重點(diǎn)分析LinkedHashMap。

LinkedHashMap實(shí)現(xiàn)了Map接口，即允許放入key為null的元素，也允許插入value為null的元素。從名字上可以看出該容器是linked list和HashMap的混合體，也就是說(shuō)它同時(shí)滿足HashMap和linked list的某些特性?？蓪inkedHashMap看作采用linked list增強(qiáng)的HashMap。

事實(shí)上LinkedHashMap是HashMap的直接子類，二者唯一的區(qū)別是LinkedHashMap在HashMap的基礎(chǔ)上，采用雙向鏈表（doubly-linked list）的形式將所有entry連接起來(lái)，這樣是為保證元素的迭代順序跟插入順序相同。上圖給出了LinkedHashMap的結(jié)構(gòu)圖，主體部分跟HashMap完全一樣，多了header指向雙向鏈表的頭部（是一個(gè)啞元），該雙向鏈表的迭代順序就是entry的插入順序。

除了可以保迭代歷順序，這種結(jié)構(gòu)還有一個(gè)好處：迭代LinkedHashMap時(shí)不需要像HashMap那樣遍歷整個(gè)table，而只需要直接遍歷header指向的雙向鏈表即可，也就是說(shuō)LinkedHashMap的迭代時(shí)間就只跟entry的個(gè)數(shù)相關(guān)，而跟table的大小無(wú)關(guān)。

有兩個(gè)參數(shù)可以影響LinkedHashMap的性能：初始容量（inital capacity）和負(fù)載系數(shù)（load factor）。初始容量指定了初始table的大小，負(fù)載系數(shù)用來(lái)指定自動(dòng)擴(kuò)容的臨界值。當(dāng)entry的數(shù)量超過(guò)capacity*load_factor時(shí)，容器將自動(dòng)擴(kuò)容并重新哈希。對(duì)于插入元素較多的場(chǎng)景，將初始容量設(shè)大可以減少重新哈希的次數(shù)。

將對(duì)象放入到LinkedHashMap或LinkedHashSet中時(shí)，有兩個(gè)方法需要特別關(guān)心：hashCode()和equals()。hashCode()方法決定了對(duì)象會(huì)被放到哪個(gè)bucket里，當(dāng)多個(gè)對(duì)象的哈希值沖突時(shí)，equals()方法決定了這些對(duì)象是否是“同一個(gè)對(duì)象”。所以，如果要將自定義的對(duì)象放入到LinkedHashMap或LinkedHashSet中，需要*@Override*hashCode()和equals()方法。

通過(guò)如下方式可以得到一個(gè)跟源Map 迭代順序一樣的LinkedHashMap：

void foo(Map m) { ? ?Map copy = new LinkedHashMap(m); ? ?...}

出于性能原因，LinkedHashMap是非同步的（not synchronized），如果需要在多線程環(huán)境使用，需要程序員手動(dòng)同步；或者通過(guò)如下方式將LinkedHashMap包裝成（wrapped）同步的：

Map m = Collections.synchronizedMap(new LinkedHashMap(...));


方法剖析

get()

get(Object key)方法根據(jù)指定的key值返回對(duì)應(yīng)的value。該方法跟HashMap.get()方法的流程幾乎完全一樣，讀者可自行參考前文，這里不再贅述。

put()

put(K key, V value)方法是將指定的key, value對(duì)添加到map里。該方法首先會(huì)對(duì)map做一次查找，看是否包含該元組，如果已經(jīng)包含則直接返回，查找過(guò)程類似于get()方法；如果沒(méi)有找到，則會(huì)通過(guò)addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。

注意，這里的插入有兩重含義：

1.從table的角度看，新的entry需要插入到對(duì)應(yīng)的bucket里，當(dāng)有哈希沖突時(shí)，采用頭插法將新的entry插入到?jīng)_突鏈表的頭部。

2.從header的角度看，新的entry需要插入到雙向鏈表的尾部。

addEntry()代碼如下：

// LinkedHashMap.addEntry()void addEntry(int hash, K key, V value, int bucketIndex) { ? ?if ((size >= threshold) && (null != table[bucketIndex])) { ? ? ? ?resize(2 * table.length);// 自動(dòng)擴(kuò)容，并重新哈希 ? ? ? ?hash = (null != key) ? hash(key) : 0; ? ? ? ?bucketIndex = hash & (table.length-1);// hash%table.length ? ?} ? ?// 1.在沖突鏈表頭部插入新的entry ? ?HashMap.Entry<K,V> old = table[bucketIndex]; ? ?Entry<K,V> e = new Entry<>(hash, key, value, old); ? ?table[bucketIndex] = e; ? ?// 2.在雙向鏈表的尾部插入新的entry ? ?e.addBefore(header); ? ?size++;}


上述代碼中用到了addBefore()方法將新entry e插入到雙向鏈表頭引用header的前面，這樣e就成為雙向鏈表中的最后一個(gè)元素。addBefore()的代碼如下：

• 
  

// LinkedHashMap.Entry.addBefor()，將this插入到existingEntry的前面private void addBefore(Entry<K,V> existingEntry) { ? ?after ?= existingEntry; ? ?before = existingEntry.before; ? ?before.after = this; ? ?after.before = this;}

上述代碼只是簡(jiǎn)單修改相關(guān)entry的引用而已。

remove()

remove(Object key)的作用是刪除key值對(duì)應(yīng)的entry，該方法的具體邏輯是在removeEntryForKey(Object key)里實(shí)現(xiàn)的。removeEntryForKey()方法會(huì)首先找到key值對(duì)應(yīng)的entry，然后刪除該entry（修改鏈表的相應(yīng)引用）。查找過(guò)程跟get()方法類似。

注意，這里的刪除也有兩重含義：

1.從table的角度看，需要將該entry從對(duì)應(yīng)的bucket里刪除，如果對(duì)應(yīng)的沖突鏈表不空，需要修改沖突鏈表的相應(yīng)引用。

2.從header的角度來(lái)看，需要將該entry從雙向鏈表中刪除，同時(shí)修改鏈表中前面以及后面元素的相應(yīng)引用。

removeEntryForKey()對(duì)應(yīng)的代碼如下：

// LinkedHashMap.removeEntryForKey()，刪除key值對(duì)應(yīng)的entryfinal Entry<K,V> removeEntryForKey(Object key) { ?...... ?int hash = (key == null) ? 0 : hash(key); ? ?int i = indexFor(hash, table.length);// hash&(table.length-1) ? ?Entry<K,V> prev = table[i];// 得到?jīng)_突鏈表 ? ?Entry<K,V> e = prev; ? ?while (e != null) {// 遍歷沖突鏈表 ? ? ? ?Entry<K,V> next = e.next; ? ? ? ?Object k; ? ? ? ?if (e.hash == hash && ? ? ? ? ? ?((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要?jiǎng)h除的entry ? ? ? ? ? ?modCount++; size--; ? ? ? ? ? ?// 1. 將e從對(duì)應(yīng)bucket的沖突鏈表中刪除 ? ? ? ? ? ?if (prev == e) table[i] = next; ? ? ? ? ? ?else prev.next = next; ? ? ? ? ? ?// 2. 將e從雙向鏈表中刪除 ? ? ? ? ? ?e.before.after = e.after; ? ? ? ? ? ?e.after.before = e.before; ? ? ? ? ? ?return e; ? ? ? ?} ? ? ? ?prev = e; e = next; ? ?} ? ?return e;}

LinkedHashSet

前面已經(jīng)說(shuō)過(guò)LinkedHashSet是對(duì)LinkedHashMap的簡(jiǎn)單包裝，對(duì)LinkedHashSet的函數(shù)調(diào)用都會(huì)轉(zhuǎn)換成合適的LinkedHashMap方法，因此LinkedHashSet的實(shí)現(xiàn)非常簡(jiǎn)單，這里不再贅述。

• 
  

public class LinkedHashSet<E> ? ?extends HashSet<E> ? ?implements Set<E>, Cloneable, java.io.Serializable { ? ?...... ? ?// LinkedHashSet里面有一個(gè)LinkedHashMap ? ?public LinkedHashSet(int initialCapacity, float loadFactor) { ? ? ? ?map = new LinkedHashMap<>(initialCapacity, loadFactor); ? ?} ?...... ? ?public boolean add(E e) {//簡(jiǎn)單的方法轉(zhuǎn)換 ? ? ? ?return map.put(e, PRESENT)==null; ? ?} ? ?......}


LinkedHashMap經(jīng)典用法

LinkedHashMap除了可以保證迭代順序外，還有一個(gè)非常有用的用法：可以輕松實(shí)現(xiàn)一個(gè)采用了FIFO替換策略的緩存。具體說(shuō)來(lái)，LinkedHashMap有一個(gè)子類方法protected boolean removeEldestEntry(Map.Entry<K,V> eldest)，該方法的作用是告訴Map是否要?jiǎng)h除“最老”的Entry，所謂最老就是當(dāng)前Map中最早插入的Entry，如果該方法返回true，最老的那個(gè)元素就會(huì)被刪除。在每次插入新元素的之后LinkedHashMap會(huì)自動(dòng)詢問(wèn)removeEldestEntry()是否要?jiǎng)h除最老的元素。這樣只需要在子類中重載該方法，當(dāng)元素個(gè)數(shù)超過(guò)一定數(shù)量時(shí)讓removeEldestEntry()返回true，就能夠?qū)崿F(xiàn)一個(gè)固定大小的FIFO策略的緩存。示例代碼如下：

• 
  

/** 一個(gè)固定大小的FIFO替換策略的緩存 */class FIFOCache<K, V> extends LinkedHashMap<K, V>{ ? ?private final int cacheSize; ? ?public FIFOCache(int cacheSize){ ? ? ? ?this.cacheSize = cacheSize; ? ?}
? ?// 當(dāng)Entry個(gè)數(shù)超過(guò)cacheSize時(shí)，刪除最老的Entry ? ?@Override ? ?protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { ? ? ? return size() > cacheSize; ? ?}}