关于LinkedHashmap的个人理解

大多数情况下,只要不涉及线程安全问题,Map基本都可以使用HashMap,不过HashMap有一个问题,就是迭代HashMap的顺序并不是HashMap放置的顺序。HashMap的这一缺点往往会带来困扰,因为有些场景,我们需要一个有序的MapLinkedHashMap就可以做到,它虽然增加了时间和空间上的开销,但是通过维护一个运行于所有条目的双向链表,LinkedHashMap保证了元素迭代的顺序。想要解锁更多新姿势?请访问https://blog.tengshe789.tech/

数据结构

打开源码可以看到:

1
2
3
4
5
6
7
8
9
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
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);
}
}

LinkedHashMap继承了HashMapEntry,并新增加了两个指针

LinkedHashmap数据结构

参照一下网络上搜刮的图片,可以看出数据结构为数组 + 单链表 + 红黑树 + 双链表,比HashMap多了一个双向链表,就是利用了头节点和其余的各个节点之间通过 Entry 中的 afterbefore 指针进行关联。

构造方法

看一下构造方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}


public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}


public LinkedHashMap() {
super();
accessOrder = false;
}

public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}

有四个构造方法,每一个的构造方法第一句话基本都是调用父类HashMap方法。估计是用多态来实现的相关功能。比 HashMap 多了一个 accessOrder 的参数,用来指定按照 LRU 排列方式还是顺序插入的排序方式

添加

LinkedHashMapput() 方法之前先看看 HashMapputVal 方法:

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
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;
}

其实这篇已经是我早有准备的,第一次看源码的时候已经惊了。LinkedHashMap 自己没有重写put方法,全是照着他爹搬过来的,无赖 啊。代码中敲黑板位置,是LinkedHashMap 重写了 afterNodeAccess() 这个方法。

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
//将最近使用的Node e,放在链表的最末尾
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//仅当按照LRU原则且e不在最末尾,才执行修改链表,将e移到链表最末尾的操作
//accessOrder为true则表示按照基于访问的顺序来排列
if (accessOrder && (last = tail) != e) {
//将e赋值临时节点p, b是e的前一个节点, a是e的后一个节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//节点移动过程
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}

2

结束
此片完了~ 想要了解更多精彩新姿势?请访问我的个人博客 本篇为原创内容,已在个人博客率先发表,随后CSDN,segmentfault,juejin同步发出。如有雷同,缘分呢兄弟。赶快加个好友~

-------------本稿が終わる感谢您的阅读-------------