概述：
LinkedHashMap實現(xiàn)Map繼承HashMap，基于Map的哈希表和鏈該列表實現(xiàn)，具有可預(yù)知的迭代順序。
LinedHashMap維護(hù)著一個運行于所有條目的雙重鏈表結(jié)構(gòu)，該鏈表定義了迭代順序，可以是插入或者訪問順序。
LintHashMap的節(jié)點對象繼承HashMap的節(jié)點對象，并增加了前后指針 before after：
|
1
2
3
4
5
6
7
8
9
|
/** * LinkedHashMap節(jié)點對象 */ 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); } } |
lintHashMap初始化：
accessOrder,簡單說就是這個用來控制元素的順序，
accessOrder為true: 表示按照訪問的順序來，也就是誰最先訪問，就排在第一位
accessOrder為false表示按照存放順序來，就是你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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } /** * 生成一個空的LinkedHashMap,并指定其容量大小，負(fù)載因子使用默認(rèn)的0.75， * accessOrder為false表示按照存放順序來，就是你put元素的時候的順序 * accessOrder為true: 表示按照訪問的順序來，也就是誰最先訪問，就排在第一位 */ public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } /** * 生成一個空的HashMap,容量大小使用默認(rèn)值16，負(fù)載因子使用默認(rèn)值0.75 * 默認(rèn)將accessOrder設(shè)為false，按插入順序排序. */ public LinkedHashMap() { super(); accessOrder = false; } /** * 根據(jù)指定的map生成一個新的HashMap,負(fù)載因子使用默認(rèn)值，初始容量大小為Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY) * 默認(rèn)將accessOrder設(shè)為false，按插入順序排序. */ public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); } /** * 生成一個空的LinkedHashMap,并指定其容量大小和負(fù)載因子， * 默認(rèn)將accessOrder設(shè)為true，按訪問順序排序 */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } |
putMapEntries(m,false)調(diào)用父類HashMap的方法，繼而根據(jù)HashMap的put來實現(xiàn)數(shù)據(jù)的插入：
|
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
|
/** * Implements Map.putAll and Map constructor * * @param m the map * @param evict false when initially constructing this map, else * true (relayed to method afterNodeInsertion). */final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { // pre-size float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t); } else if (s > threshold) resize(); for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } }} |
存儲：
put調(diào)用的HashMap的put方法，調(diào)用兩個空方法，由LinkedHashMap實現(xiàn)
|
1
2
3
|
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } |
|
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
|
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } |
在hashmap中紅色部分為空實現(xiàn):
|
1
2
|
void afterNodeAccess(Node<K,V> p) { }void afterNodeInsertion(boolean evict) { } |
然后看下LinkedHashMap怎么實現(xiàn)這兩方法：
將當(dāng)前節(jié)點e移動到雙向鏈表的尾部。每次LinkedHashMap中有元素被訪問時，就會按照訪問先后來排序，先訪問的在雙向鏈表中靠前，越后訪問的越接近尾部。當(dāng)然只有當(dāng)accessOrder為true時，才會執(zhí)行這個操作。
|
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
|
void afterNodeAccess(Node<K,V> e) { LinkedHashMap.Entry<K,V> last; // 若訪問順序為true，且訪問的對象不是尾結(jié)點 if (accessOrder && (last = tail) != e) { // 向下轉(zhuǎn)型，記錄p的前后結(jié)點 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // p的后結(jié)點為空 p.after = null; // 如果p的前結(jié)點為空 if (b == null) // a為頭結(jié)點 head = a; else // p的前結(jié)點不為空 // b的后結(jié)點為a b.after = a; // p的后結(jié)點不為空 if (a != null) // a的前結(jié)點為b a.before = b; else // p的后結(jié)點為空 // 后結(jié)點為最后一個結(jié)點 last = b; // 若最后一個結(jié)點為空 if (last == null) // 頭結(jié)點為p head = p; else { // p鏈入最后一個結(jié)點后面 p.before = last; last.after = p; } // 尾結(jié)點為p tail = p; // 增加結(jié)構(gòu)性修改數(shù)量 ++modCount; } } |
afterNodeInsertion方法 evict為true時刪除雙向鏈表的頭節(jié)點
|
1
2
3
4
5
6
7
8
|
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; //頭結(jié)點不為空，刪除頭結(jié)點 if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); }} |
刪除操作調(diào)用HashMap的remove方法實現(xiàn)元素刪除，remove調(diào)用removeNode，而removeNode有一個方法需要LinkedHashMap來實現(xiàn)：
將e節(jié)點從雙向鏈表中刪除，更改e前后節(jié)點引用關(guān)系，使之重新連成完整的雙向鏈表。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b;} |
讀取：
e不為空，則獲取e的value值并返回。
|
1
2
3
4
5
6
7
8
|
public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; } |
accessOrder為true,也就是說按照訪問順序獲取內(nèi)容。
|
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
|
void afterNodeAccess(Node<K,V> e) { LinkedHashMap.Entry<K,V> last; // 若訪問順序為true，且訪問的對象不是尾結(jié)點 if (accessOrder && (last = tail) != e) { // 向下轉(zhuǎn)型，記錄p的前后結(jié)點 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // p的后結(jié)點為空 p.after = null; // 如果p的前結(jié)點為空 if (b == null) // a為頭結(jié)點 head = a; else // p的前結(jié)點不為空 // b的后結(jié)點為a b.after = a; // p的后結(jié)點不為空 if (a != null) // a的前結(jié)點為b a.before = b; else // p的后結(jié)點為空 // 后結(jié)點為最后一個結(jié)點 last = b; // 若最后一個結(jié)點為空 if (last == null) // 頭結(jié)點為p head = p; else { // p鏈入最后一個結(jié)點后面 p.before = last; last.after = p; } // 尾結(jié)點為p tail = p; // 增加結(jié)構(gòu)性修改數(shù)量 ++modCount; }} |
LinkedHashMap的幾個迭代器：
抽象類LinkedHashIterator 實現(xiàn)具體刪除，判斷是否存在下個結(jié)點，迭代的邏輯。
LinkedKeyIterator 繼承自LinkedHashIterator，實現(xiàn)了Iterator接口，對LinkedHashMap中的key進(jìn)行迭代。
LinkedValueIterator 繼承自LinkedHashIterator，實現(xiàn)了Iterator接口，對LinkedHashMap中的Value進(jìn)行迭代
LinkedEntryIterator 繼承自LinkedHashIterator，實現(xiàn)了Iterator接口，對LinkedHashMap中的結(jié)點進(jìn)行迭代
|
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
|
abstract class LinkedHashIterator { //下一個節(jié)點 LinkedHashMap.Entry<K,V> next; //當(dāng)前節(jié)點 LinkedHashMap.Entry<K,V> current; //期望的修改次數(shù) int expectedModCount; LinkedHashIterator() { //next賦值為頭結(jié)點 next = head; //賦值修改次數(shù) expectedModCount = modCount; //當(dāng)前節(jié)點賦值為空 current = null; } //是否存在下一個結(jié)點 public final boolean hasNext() { return next != null; } final LinkedHashMap.Entry<K,V> nextNode() { LinkedHashMap.Entry<K,V> e = next; //檢查是否存在結(jié)構(gòu)性改變 if (modCount != expectedModCount) throw new ConcurrentModificationException(); //結(jié)點為null NoSuchElementException if (e == null) throw new NoSuchElementException(); //不為null,賦值當(dāng)前節(jié)點 current = e; //賦值下一個結(jié)點 next = e.after; return e; } //刪除操作 public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; //移除結(jié)點操作 removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } } final class LinkedKeyIterator extends LinkedHashIterator implements Iterator<K> { public final K next() { return nextNode().getKey(); } } final class LinkedValueIterator extends LinkedHashIterator implements Iterator<V> { public final V next() { return nextNode().value; } } final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } } |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://www.cnblogs.com/androidsuperman/p/7605869.html
