概述：
LinkedHashMap实现Map继承HashMap，基于Map的哈希表和链该列表实现，具有可预知的迭代顺序。
LinedHashMap维护着一个运行于所有条目的双重链表结构，该链表定义了迭代顺序，可以是插入或者访问顺序。
LintHashMap的节点对象继承HashMap的节点对象，并增加了前后指针 before after：
|
1
2
3
4
5
6
7
8
9
|
/** * LinkedHashMap节点对象 */ 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,并指定其容量大小，负载因子使用默认的0.75， * accessOrder为false表示按照存放顺序来，就是你put元素的时候的顺序 * accessOrder为true: 表示按照访问的顺序来，也就是谁最先访问，就排在第一位 */ public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } /** * 生成一个空的HashMap,容量大小使用默认值16，负载因子使用默认值0.75 * 默认将accessOrder设为false，按插入顺序排序. */ public LinkedHashMap() { super(); accessOrder = false; } /** * 根据指定的map生成一个新的HashMap,负载因子使用默认值，初始容量大小为Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY) * 默认将accessOrder设为false，按插入顺序排序. */ public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); } /** * 生成一个空的LinkedHashMap,并指定其容量大小和负载因子， * 默认将accessOrder设为true，按访问顺序排序 */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } |
putMapEntries(m,false)调用父类HashMap的方法，继而根据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
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调用的HashMap的put方法，调用两个空方法，由LinkedHashMap实现
|
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中红色部分为空实现:
|
1
2
|
void afterNodeAccess(Node<K,V> p) { }void afterNodeInsertion(boolean evict) { } |
然后看下LinkedHashMap怎么实现这两方法：
将当前节点e移动到双向链表的尾部。每次LinkedHashMap中有元素被访问时，就会按照访问先后来排序，先访问的在双向链表中靠前，越后访问的越接近尾部。当然只有当accessOrder为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
|
void afterNodeAccess(Node<K,V> e) { LinkedHashMap.Entry<K,V> last; // 若访问顺序为true，且访问的对象不是尾结点 if (accessOrder && (last = tail) != e) { // 向下转型，记录p的前后结点 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // p的后结点为空 p.after = null; // 如果p的前结点为空 if (b == null) // a为头结点 head = a; else // p的前结点不为空 // b的后结点为a b.after = a; // p的后结点不为空 if (a != null) // a的前结点为b a.before = b; else // p的后结点为空 // 后结点为最后一个结点 last = b; // 若最后一个结点为空 if (last == null) // 头结点为p head = p; else { // p链入最后一个结点后面 p.before = last; last.after = p; } // 尾结点为p tail = p; // 增加结构性修改数量 ++modCount; } } |
afterNodeInsertion方法 evict为true时删除双向链表的头节点
|
1
2
3
4
5
6
7
8
|
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; //头结点不为空，删除头结点 if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); }} |
删除操作调用HashMap的remove方法实现元素删除，remove调用removeNode，而removeNode有一个方法需要LinkedHashMap来实现：
将e节点从双向链表中删除，更改e前后节点引用关系，使之重新连成完整的双向链表。
|
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,也就是说按照访问顺序获取内容。
|
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，且访问的对象不是尾结点 if (accessOrder && (last = tail) != e) { // 向下转型，记录p的前后结点 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // p的后结点为空 p.after = null; // 如果p的前结点为空 if (b == null) // a为头结点 head = a; else // p的前结点不为空 // b的后结点为a b.after = a; // p的后结点不为空 if (a != null) // a的前结点为b a.before = b; else // p的后结点为空 // 后结点为最后一个结点 last = b; // 若最后一个结点为空 if (last == null) // 头结点为p head = p; else { // p链入最后一个结点后面 p.before = last; last.after = p; } // 尾结点为p tail = p; // 增加结构性修改数量 ++modCount; }} |
LinkedHashMap的几个迭代器：
抽象类LinkedHashIterator 实现具体删除，判断是否存在下个结点，迭代的逻辑。
LinkedKeyIterator 继承自LinkedHashIterator，实现了Iterator接口，对LinkedHashMap中的key进行迭代。
LinkedValueIterator 继承自LinkedHashIterator，实现了Iterator接口，对LinkedHashMap中的Value进行迭代
LinkedEntryIterator 继承自LinkedHashIterator，实现了Iterator接口，对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
|
abstract class LinkedHashIterator { //下一个节点 LinkedHashMap.Entry<K,V> next; //当前节点 LinkedHashMap.Entry<K,V> current; //期望的修改次数 int expectedModCount; LinkedHashIterator() { //next赋值为头结点 next = head; //赋值修改次数 expectedModCount = modCount; //当前节点赋值为空 current = null; } //是否存在下一个结点 public final boolean hasNext() { return next != null; } final LinkedHashMap.Entry<K,V> nextNode() { LinkedHashMap.Entry<K,V> e = next; //检查是否存在结构性改变 if (modCount != expectedModCount) throw new ConcurrentModificationException(); //结点为null NoSuchElementException if (e == null) throw new NoSuchElementException(); //不为null,赋值当前节点 current = e; //赋值下一个结点 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; //移除结点操作 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(); } } |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://www.cnblogs.com/androidsuperman/p/7605869.html
