LinkedHashMap是HashMap的子類，與HashMap有著同樣的存儲結構，但它加入了一個雙向鏈表的頭結點，將所有put到LinkedHashmap的節(jié)點一一串成了一個雙向循環(huán)鏈表，因此它保留了節(jié)點插入的順序，可以使節(jié)點的輸出順序與輸入順序相同。
LinkedHashMap可以用來實現(xiàn)LRU算法（這會在下面的源碼中進行分析）。
LinkedHashMap同樣是非線程安全的，只在單線程環(huán)境下使用。
LinkedHashMap源碼剖析
LinkedHashMap源碼如下（加入了詳細的注釋）：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
package java.util; import java.io.*; public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { private static final long serialVersionUID = 3801124242820219131L; //雙向循環(huán)鏈表的頭結點，整個LinkedHashMap中只有一個header， //它將哈希表中所有的Entry貫穿起來，header中不保存key-value對，只保存前后節(jié)點的引用 private transient Entry<K,V> header; //雙向鏈表中元素排序規(guī)則的標志位。 //accessOrder為false，表示按插入順序排序 //accessOrder為true，表示按訪問順序排序 private final boolean accessOrder; //調用HashMap的構造方法來構造底層的數(shù)組 public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; //鏈表中的元素默認按照插入順序排序 } //加載因子取默認的0.75f public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } //加載因子取默認的0.75f，容量取默認的16 public LinkedHashMap() { super(); accessOrder = false; } //含有子Map的構造方法，同樣調用HashMap的對應的構造方法 public LinkedHashMap(Map<? extends K, ? extends V> m) { super(m); accessOrder = false; } //該構造方法可以指定鏈表中的元素排序的規(guī)則 public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } //覆寫父類的init()方法（HashMap中的init方法為空）， //該方法在父類的構造方法和Clone、readObject中在插入元素前被調用， //初始化一個空的雙向循環(huán)鏈表，頭結點中不保存數(shù)據(jù)，頭結點的下一個節(jié)點才開始保存數(shù)據(jù)。 void init() { header = new Entry<K,V>(-1, null, null, null); header.before = header.after = header; } //覆寫HashMap中的transfer方法，它在父類的resize方法中被調用， //擴容后，將key-value對重新映射到新的newTable中 //覆寫該方法的目的是為了提高復制的效率， //這里充分利用雙向循環(huán)鏈表的特點進行迭代，不用對底層的數(shù)組進行for循環(huán)。 void transfer(HashMap.Entry[] newTable) { int newCapacity = newTable.length; for (Entry<K,V> e = header.after; e != header; e = e.after) { int index = indexFor(e.hash, newCapacity); e.next = newTable[index]; newTable[index] = e; } } //覆寫HashMap中的containsValue方法， //覆寫該方法的目的同樣是為了提高查詢的效率， //利用雙向循環(huán)鏈表的特點進行查詢，少了對數(shù)組的外層for循環(huán) public boolean containsValue(Object value) { // Overridden to take advantage of faster iterator if (value==null) { for (Entry e = header.after; e != header; e = e.after) if (e.value==null) return true; } else { for (Entry e = header.after; e != header; e = e.after) if (value.equals(e.value)) return true; } return false; } //覆寫HashMap中的get方法，通過getEntry方法獲取Entry對象。 //注意這里的recordAccess方法， //如果鏈表中元素的排序規(guī)則是按照插入的先后順序排序的話，該方法什么也不做， //如果鏈表中元素的排序規(guī)則是按照訪問的先后順序排序的話，則將e移到鏈表的末尾處。 public V get(Object key) { Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; e.recordAccess(this); return e.value; } //清空HashMap，并將雙向鏈表還原為只有頭結點的空鏈表 public void clear() { super.clear(); header.before = header.after = header; } //Enty的數(shù)據(jù)結構，多了兩個指向前后節(jié)點的引用 private static class Entry<K,V> extends HashMap.Entry<K,V> { // These fields comprise the doubly linked list used for iteration. Entry<K,V> before, after; //調用父類的構造方法 Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); } //雙向循環(huán)鏈表中，刪除當前的Entry private void remove() { before.after = after; after.before = before; } //雙向循環(huán)立鏈表中，將當前的Entry插入到existingEntry的前面 private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; } //覆寫HashMap中的recordAccess方法（HashMap中該方法為空）， //當調用父類的put方法，在發(fā)現(xiàn)插入的key已經(jīng)存在時，會調用該方法， //調用LinkedHashmap覆寫的get方法時，也會調用到該方法， //該方法提供了LRU算法的實現(xiàn)，它將最近使用的Entry放到雙向循環(huán)鏈表的尾部， //accessOrder為true時，get方法會調用recordAccess方法 //put方法在覆蓋key-value對時也會調用recordAccess方法 //它們導致Entry最近使用，因此將其移到雙向鏈表的末尾 void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; //如果鏈表中元素按照訪問順序排序，則將當前訪問的Entry移到雙向循環(huán)鏈表的尾部， //如果是按照插入的先后順序排序，則不做任何事情。 if (lm.accessOrder) { lm.modCount++; //移除當前訪問的Entry remove(); //將當前訪問的Entry插入到鏈表的尾部 addBefore(lm.header); } } void recordRemoval(HashMap<K,V> m) { remove(); } } //迭代器 private abstract class LinkedHashIterator<T> implements Iterator<T> { Entry<K,V> nextEntry = header.after; Entry<K,V> lastReturned = null; /** * The modCount value that the iterator believes that the backing * List should have. If this expectation is violated, the iterator * has detected concurrent modification. */ int expectedModCount = modCount; public boolean hasNext() { return nextEntry != header; } public void remove() { if (lastReturned == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); LinkedHashMap.this.remove(lastReturned.key); lastReturned = null; expectedModCount = modCount; } //從head的下一個節(jié)點開始迭代 Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (nextEntry == header) throw new NoSuchElementException(); Entry<K,V> e = lastReturned = nextEntry; nextEntry = e.after; return e; } } //key迭代器 private class KeyIterator extends LinkedHashIterator<K> { public K next() { return nextEntry().getKey(); } } //value迭代器 private class ValueIterator extends LinkedHashIterator<V> { public V next() { return nextEntry().value; } } //Entry迭代器 private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } } // These Overrides alter the behavior of superclass view iterator() methods Iterator<K> newKeyIterator() { return new KeyIterator(); } Iterator<V> newValueIterator() { return new ValueIterator(); } Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } //覆寫HashMap中的addEntry方法，LinkedHashmap并沒有覆寫HashMap中的put方法， //而是覆寫了put方法所調用的addEntry方法和recordAccess方法， //put方法在插入的key已存在的情況下，會調用recordAccess方法， //在插入的key不存在的情況下，要調用addEntry插入新的Entry void addEntry(int hash, K key, V value, int bucketIndex) { //創(chuàng)建新的Entry，并插入到LinkedHashMap中 createEntry(hash, key, value, bucketIndex); //雙向鏈表的第一個有效節(jié)點（header后的那個節(jié)點）為近期最少使用的節(jié)點 Entry<K,V> eldest = header.after; //如果有必要，則刪除掉該近期最少使用的節(jié)點， //這要看對removeEldestEntry的覆寫,由于默認為false，因此默認是不做任何處理的。 if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } else { //擴容到原來的2倍 if (size >= threshold) resize(2 * table.length); } } void createEntry(int hash, K key, V value, int bucketIndex) { //創(chuàng)建新的Entry，并將其插入到數(shù)組對應槽的單鏈表的頭結點處，這點與HashMap中相同 HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<K,V>(hash, key, value, old); table[bucketIndex] = e; //每次插入Entry時，都將其移到雙向鏈表的尾部， //這便會按照Entry插入LinkedHashMap的先后順序來迭代元素， //同時，新put進來的Entry是最近訪問的Entry，把其放在鏈表末尾 ，符合LRU算法的實現(xiàn) e.addBefore(header); size++; } //該方法是用來被覆寫的，一般如果用LinkedHashmap實現(xiàn)LRU算法，就要覆寫該方法， //比如可以將該方法覆寫為如果設定的內存已滿，則返回true，這樣當再次向LinkedHashMap中put //Entry時，在調用的addEntry方法中便會將近期最少使用的節(jié)點刪除掉（header后的那個節(jié)點）。 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; } } |
總結
關于LinkedHashMap的源碼，給出以下幾點比較重要的總結：
1、從源碼中可以看出，LinkedHashMap中加入了一個head頭結點，將所有插入到該LinkedHashMap中的Entry按照插入的先后順序依次加入到以head為頭結點的雙向循環(huán)鏈表的尾部。
1、實際上就是HashMap和LinkedList兩個集合類的存儲結構的結合。在LinkedHashMapMap中，所有put進來的Entry都保存在哈希表中，但它又額外定義了一個以head為頭結點的空的雙向循環(huán)鏈表，每次put進來Entry，除了將其保存到對哈希表中對應的位置上外，還要將其插入到雙向循環(huán)鏈表的尾部。
2、LinkedHashMap由于繼承自HashMap，因此它具有HashMap的所有特性，同樣允許key和value為null。
3、注意源碼中的accessOrder標志位，當它false時，表示雙向鏈表中的元素按照Entry插入LinkedHashMap到中的先后順序排序，即每次put到LinkedHashMap中的Entry都放在雙向鏈表的尾部，這樣遍歷雙向鏈表時，Entry的輸出順序便和插入的順序一致，這也是默認的雙向鏈表的存儲順序；當它為true時，表示雙向鏈表中的元素按照訪問的先后順序排列，可以看到，雖然Entry插入鏈表的順序依然是按照其put到LinkedHashMap中的順序，但put和get方法均有調用recordAccess方法（put方法在key相同，覆蓋原有的Entry的情況下調用recordAccess方法），該方法判斷accessOrder是否為true，如果是，則將當前訪問的Entry（put進來的Entry或get出來的Entry）移到雙向鏈表的尾部（key不相同時，put新Entry時，會調用addEntry，它會調用creatEntry，該方法同樣將新插入的元素放入到雙向鏈表的尾部，既符合插入的先后順序，又符合訪問的先后順序，因為這時該Entry也被訪問了），否則，什么也不做。
4、注意構造方法，前四個構造方法都將accessOrder設為false，說明默認是按照插入順序排序的，而第五個構造方法可以自定義傳入的accessOrder的值，因此可以指定雙向循環(huán)鏈表中元素的排序規(guī)則，一般要用LinkedHashMap實現(xiàn)LRU算法，就要用該構造方法，將accessOrder置為true。
5、LinkedHashMap并沒有覆寫HashMap中的put方法，而是覆寫了put方法中調用的addEntry方法和recordAccess方法，我們回過頭來再看下HashMap的put方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// 將“key-value”添加到HashMap中 public V put(K key, V value) { // 若“key為null”，則將該鍵值對添加到table[0]中。 if (key == null) return putForNullKey(value); // 若“key不為null”，則計算該key的哈希值，然后將其添加到該哈希值對應的鏈表中。 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 若“該key”對應的鍵值對已經(jīng)存在，則用新的value取代舊的value。然后退出！ if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 若“該key”對應的鍵值對不存在，則將“key-value”添加到table中 modCount++; //將key-value添加到table[i]處 addEntry(hash, key, value, i); return null; } |
當要put進來的Entry的key在哈希表中已經(jīng)在存在時，會調用recordAccess方法，當該key不存在時，則會調用addEntry方法將新的Entry插入到對應槽的單鏈表的頭部。
我們先來看recordAccess方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//覆寫HashMap中的recordAccess方法（HashMap中該方法為空）， //當調用父類的put方法，在發(fā)現(xiàn)插入的key已經(jīng)存在時，會調用該方法， //調用LinkedHashmap覆寫的get方法時，也會調用到該方法， //該方法提供了LRU算法的實現(xiàn)，它將最近使用的Entry放到雙向循環(huán)鏈表的尾部， //accessOrder為true時，get方法會調用recordAccess方法 //put方法在覆蓋key-value對時也會調用recordAccess方法 //它們導致Entry最近使用，因此將其移到雙向鏈表的末尾 void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; //如果鏈表中元素按照訪問順序排序，則將當前訪問的Entry移到雙向循環(huán)鏈表的尾部， //如果是按照插入的先后順序排序，則不做任何事情。 if (lm.accessOrder) { lm.modCount++; //移除當前訪問的Entry remove(); //將當前訪問的Entry插入到鏈表的尾部 addBefore(lm.header); } } |
該方法會判斷accessOrder是否為true，如果為true，它會將當前訪問的Entry（在這里指put進來的Entry）移動到雙向循環(huán)鏈表的尾部，從而實現(xiàn)雙向鏈表中的元素按照訪問順序來排序（最近訪問的Entry放到鏈表的最后，這樣多次下來，前面就是最近沒有被訪問的元素，在實現(xiàn)、LRU算法時，當雙向鏈表中的節(jié)點數(shù)達到最大值時，將前面的元素刪去即可，因為前面的元素是最近最少使用的），否則什么也不做。
再來看addEntry方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
//覆寫HashMap中的addEntry方法，LinkedHashmap并沒有覆寫HashMap中的put方法， //而是覆寫了put方法所調用的addEntry方法和recordAccess方法， //put方法在插入的key已存在的情況下，會調用recordAccess方法， //在插入的key不存在的情況下，要調用addEntry插入新的Entry void addEntry(int hash, K key, V value, int bucketIndex) { //創(chuàng)建新的Entry，并插入到LinkedHashMap中 createEntry(hash, key, value, bucketIndex); //雙向鏈表的第一個有效節(jié)點（header后的那個節(jié)點）為近期最少使用的節(jié)點 Entry<K,V> eldest = header.after; //如果有必要，則刪除掉該近期最少使用的節(jié)點， //這要看對removeEldestEntry的覆寫,由于默認為false，因此默認是不做任何處理的。 if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } else { //擴容到原來的2倍 if (size >= threshold) resize(2 * table.length); } } void createEntry(int hash, K key, V value, int bucketIndex) { //創(chuàng)建新的Entry，并將其插入到數(shù)組對應槽的單鏈表的頭結點處，這點與HashMap中相同 HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<K,V>(hash, key, value, old); table[bucketIndex] = e; //每次插入Entry時，都將其移到雙向鏈表的尾部， //這便會按照Entry插入LinkedHashMap的先后順序來迭代元素， //同時，新put進來的Entry是最近訪問的Entry，把其放在鏈表末尾 ，符合LRU算法的實現(xiàn) e.addBefore(header); size++; } |
同樣是將新的Entry插入到table中對應槽所對應單鏈表的頭結點中，但可以看出，在createEntry中，同樣把新put進來的Entry插入到了雙向鏈表的尾部，從插入順序的層面來說，新的Entry插入到雙向鏈表的尾部，可以實現(xiàn)按照插入的先后順序來迭代Entry，而從訪問順序的層面來說，新put進來的Entry又是最近訪問的Entry，也應該將其放在雙向鏈表的尾部。
上面還有個removeEldestEntry方法，該方法如下：
|
1
2
3
4
5
6
7
|
//該方法是用來被覆寫的，一般如果用LinkedHashmap實現(xiàn)LRU算法，就要覆寫該方法， //比如可以將該方法覆寫為如果設定的內存已滿，則返回true，這樣當再次向LinkedHashMap中put //Entry時，在調用的addEntry方法中便會將近期最少使用的節(jié)點刪除掉（header后的那個節(jié)點）。 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; } } |
該方法默認返回false，我們一般在用LinkedHashMap實現(xiàn)LRU算法時，要覆寫該方法，一般的實現(xiàn)是，當設定的內存（這里指節(jié)點個數(shù)）達到最大值時，返回true，這樣put新的Entry（該Entry的key在哈希表中沒有已經(jīng)存在）時，就會調用removeEntryForKey方法，將最近最少使用的節(jié)點刪除（head后面的那個節(jié)點，實際上是最近沒有使用）。
6、LinkedHashMap覆寫了HashMap的get方法：
|
1
2
3
4
5
6
7
8
9
10
11
|
//覆寫HashMap中的get方法，通過getEntry方法獲取Entry對象。 //注意這里的recordAccess方法， //如果鏈表中元素的排序規(guī)則是按照插入的先后順序排序的話，該方法什么也不做， //如果鏈表中元素的排序規(guī)則是按照訪問的先后順序排序的話，則將e移到鏈表的末尾處。 public V get(Object key) { Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; e.recordAccess(this); return e.value; } |
先取得Entry，如果不為null，一樣調用recordAccess方法，上面已經(jīng)說得很清楚，這里不在多解釋了。
7、最后說說LinkedHashMap是如何實現(xiàn)LRU的。
首先，當accessOrder為true時，才會開啟按訪問順序排序的模式，才能用來實現(xiàn)LRU算法。我們可以看到，無論是put方法還是get方法，都會導致目標Entry成為最近訪問的Entry，因此便把該Entry加入到了雙向鏈表的末尾（get方法通過調用recordAccess方法來實現(xiàn)，put方法在覆蓋已有key的情況下，也是通過調用recordAccess方法來實現(xiàn)，在插入新的Entry時，則是通過createEntry中的addBefore方法來實現(xiàn)），這樣便把最近使用了的Entry放入到了雙向鏈表的后面，多次操作后，雙向鏈表前面的Entry便是最近沒有使用的，這樣當節(jié)點個數(shù)滿的時候，刪除的最前面的Entry(head后面的那個Entry)便是最近最少使用的Entry。
結束語
以上就是本文關于Java集合框架源碼分析之LinkedHashMap詳解的全部內容，希望對大家學習Java能夠有所幫助。歡迎大家參閱本站其他專題，感謝大家讀服務器之家的支持！
原文鏈接：http://blog.csdn.net/ylyg050518/article/details/78065671
