LinkedHashMap表层分析

img

LinkedHashMap可以理解为HashMap+LinkedList组成的

有HashMap的数据结构,也有LinkedList维护插入元素的先后顺序

LinkedHashMap其中有很多方法是重用HashMap里面的,在此只分析有区别部分

属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* The head (eldest) of the doubly linked list.
* 头节点
*/
transient LinkedHashMap.Entry<K,V> head;

/**
* The tail (youngest) of the doubly linked list.
* 尾节点
*/
transient LinkedHashMap.Entry<K,V> tail;

/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
* true则表示按照基于访问的顺序来排列,意思就是最近使用的entry,放在链表的最末尾
* false则表示按照插入顺序来
* @serial
*/
final boolean accessOrder;

方法

LinkedHashMap没有重写插入的put方法,而是直接调用的HashMap方法里面的put方法
但是HashMap里面的putVal方法newNode的时候,被LinkedHashMap里面的newNode重写了

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
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//LinkedHashMap在调用put的时候,会调用这个newNode方法
//这里新建了一个LinkedHashMap下面的Entry节点,维护有before, after这两个节点
//保证了数据插入的顺序
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
//将数据放到list的最后面
linkNodeLast(p);
return p;
}


// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
//获取到最后一个节点
LinkedHashMap.Entry<K,V> last = tail;
//将p节点放到最后
tail = p;
//如果last为null,表示该节点为null,则将p节点也放到头节点上
if (last == null)
head = p;
else {
//维护先后顺序
//将p的上一个节点设置为在为插入之前的最后一个节点
p.before = last;
//将未插入之前的最后一个节点的后节点设置为p
last.after = p;
}
}

LinkedHashMap也没有重写removeNode,删除的代码复用,只是调用了afterNodeRemoval去维护双向链表保证列表顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
//如果e节点的before为null
//标识e节点为第一个,被删除之后,e节点的after节点(后一个节点)前移,变成第一个节点
if (b == null)
head = a;
else
//如果不为null,则将e节点的后一个节点设置成b节点的下一个节点,中间去掉e的连接
b.after = a;
if (a == null)
//如果e为后面节点为null,则去掉e之后,b为最后一个节点
tail = b;
else
//a节点的前面就要去连b节点
a.before = b;
}
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
public V get(Object key) {
Node<K,V> e;
//调用的是HashMap里面的getNode
if ((e = getNode(hash(key), key)) == null)
return null;
//如果是按照使用的顺序排列则需要去重新排列一下
if (accessOrder)
afterNodeAccess(e);
return e.value;
}


void afterNodeAccess(Node<K,V> e) { // move node to last 将e节点移到最后
LinkedHashMap.Entry<K,V> last;
//如果e节点不是最后一个
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//先将p节点的后面设置为null,因为p节点被访问之后 就会被放到最后
p.after = null;
//如果b等于null,则证明e前面没有节点,则将e后面的节点放到前面去
//反之将e节点的下一个节点a连到b的后节点上去
if (b == null)
head = a;
else
b.after = a;
// 如果e的后面不为null,则要将a的前节点连到b
//否则标识e就是最后一个节点,则将b放到last
if (a != null)
a.before = b;
else
last = b;
//如果last为null,表示e前面也没有节点,则将p放到head
//反之将e节点的之前设置为last
//last之后的节点设置为p
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}

测试用例

LinkedHashMap是在HashMap的基础上面,维护了一条双向链表,保证了LinkedHashMap的插入的顺序和遍历的顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//HashMap插入和读取都是无序状态
Map<String,Object> map=new HashMap<>();
for (int i=0;i<10000;i++){
map.put("key"+i,i);
}
Iterator map1it=map.entrySet().iterator();
while(map1it.hasNext())
{
Map.Entry<String, Object> entry= (Map.Entry<String, Object> )map1it.next();
System.out.println("Key: "+entry.getKey()+" Value: "+entry.getValue());
}
//LinkedHashMap有维护一个双向链表,插入和读取都是有序状态
Map<String,Object> linkedmap=new LinkedHashMap<>();
for (int i=0;i<10000;i++){
linkedmap.put("key"+i,i);
}
Iterator linkedmaplit=linkedmap.entrySet().iterator();
while(linkedmaplit.hasNext())
{
Map.Entry<String, Object> entry= (Map.Entry<String, Object> )linkedmaplit.next();
System.out.println("Key: "+entry.getKey()+" Value: "+entry.getValue());
}

LRU算法

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高

-------------本文结束感谢您的阅读-------------
0%