🚀 优质资源分享 🚀

介绍

该实现与HashMap不同的是它维护一个双向链表，可以使HashMap有序。与HashMap一样，该类不安全。

结构

和HashMap的结构非常相似，只不过LinkedHashMap是一个双向链表

LinkedHashMap 分为两种节点 Entry和TreeNode节点
Entry节点结构：

|  | class Entry extends HashMap.Node {  |
|  |  Entry before, after;  |
|  |  Entry(int hash, K key, V value, Node next) {  |
|  | super(hash, key, value, next);  |
|  |  }  |
|  | } |


1
2
3
4
5
6
7
8
9
10

before 和 after 是双向链表中的前继和后继节点
TreeNode节点和HashMap中的一样
从这里能看出LinkedHashMap是一个双向链表

---

LinkedHashMap 有如下属性：

|  | transient LinkedHashMap.Entry head; |
|  | transient LinkedHashMap.Entry tail; |
|  | final boolean accessOrder; |


1
2
3
4
5
6
7

head 和 tail很好理解就是双向链表的头和尾
HashMap中没有accessOrder这个字段，这也是与HashMap最不同的地方，该类有两种取值分别代表不同的意思 ：

• true，按照访问顺序排序
• false，按照插入顺序排序

HashMap预留的一些方法

HashMap 预留了一些方法提供给 LinkedHashMap 使用

|  | // LinkedHashMap重写了以下四个方法来保证双向队列能够正常工作 |
|  | // 创建一个Node节点 |
|  | Node newNode(int hash, K key, V value, Node next){...} |
|  | // 创建树节点 |
|  | TreeNode newTreeNode(int hash, K key, V value, Node next) {...} |
|  | // 树节点和普通节点相互转换 |
|  | Node replacementNode(Node p, Node next) {...} |
|  | TreeNode replacementTreeNode(Node p, Node next) {...} |
|  |  |
|  |  |
|  | // HashMap未实现，留给LinkedHashMap实现 |
|  | // 后置处理 |
|  | // 访问节点后如何处理 |
|  | void afterNodeAccess(Node p) { }  |
|  | // 插入节点后如何处理 |
|  | void afterNodeInsertion(boolean evict) { }  |
|  | // 移除节点后如何处理 |
|  | void afterNodeRemoval(Node p) { } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

afterNodeAccess 、afterNodeInsertion、afterNodeRemoval 这三个方法保证了LinkedHashMap有序，分别会在get 、put、remove 后调用

put和remove 都对顺序没有影响，因为在操作的时候已经调整好了（put放在）。但是get是对顺序有影响的（被访问到了），所以需要重写该方法：

|  | public V get(Object key) {  |
|  |  Node e;  |
|  | // 获取节点 |
|  | if ((e = getNode(hash(key), key)) == null)  |
|  | return null;  |
|  | // 改变顺序 |
|  | if (accessOrder)  |
|  |  afterNodeAccess(e);  |
|  | return e.value;  |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14

通过afterNodeAccess来改变该节点（P）的顺序，该方法分为一下几步：

1. 拆除需要移动的节点P
2. 处理前置节点，前置节点有两种情况
   1. 前置节点为空，表示P为头节点
   2. 前置节点不为空，表示P为中间节点
3. 处理后置节点
   1. 后置节点为空，表示P为尾节点
   2. 后置节点不为空，表示P为中间节点
4. 将该节点移动到tail处

|  | void afterNodeAccess(Node e) { // move node to last  |
|  |  LinkedHashMap.Entry last;  |
|  | if (accessOrder && (last = tail) != e) {  |
|  |  LinkedHashMap.Entry p =  |
|  |  (LinkedHashMap.Entry)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;  |
|  |  }  |
|  | } |


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

afterNodeInsertion 则在putVal中调用
基本逻辑是如果参数为true则尝试删除头节点，但是还需要满足头节点是最’老’的，具体的与removeEldestEntry配合使用，可以继承LinkedHashMap并定制， LinkedHashMap是恒为false的。

|  | protected boolean removeEldestEntry(Map.Entry eldest) {  |
|  | return false;  |
|  | } |


1
2
3
4
5
6
7

如果所有条件都满足则删除头节点

|  | void afterNodeInsertion(boolean evict) { // possibly remove eldest  |
|  |  LinkedHashMap.Entry first;  |
|  | if (evict && (first = head) != null && removeEldestEntry(first)) {  |
|  | K key = first.key;  |
|  |  removeNode(hash(key), key, null, false, true);  |
|  |  }  |
|  | } |


1
2
3
4
5
6
7
8
9
10
11

afterNodeRemoval则在removeNode成功删除节点之后调用:
用来保证在双向链表中删除一个节点仍然能够使结构不被破坏
为被删除节点的头和尾节点建立联系：

|  | void afterNodeRemoval(Node e) { // unlink  |
|  |  LinkedHashMap.Entry p =  |
|  |  (LinkedHashMap.Entry)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;  |
|  | } |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

应用

实现LRU

LRU是一种缓存置换机制，LRU （Least Recently Used）将最近最少使用的内容替换掉。实现非常简单，每次访问某个元素，就将这个元素浮动到栈顶。这样最靠近栈顶的页面就是最近经常访问的，而被压在栈底的就是最近最少使用的，只需要删除栈底的元素。
LinkedHashMap非常方便实现LRU，LinkedHashMap在put操作时同时会判断是否需要删除最’老’的元素。只需要重写removeEldestEntry方法，使得超过容量就删除最’老’的元素。

下面是具体实现：

|  | public class LRU extends LinkedHashMap {  |
|  |  |
|  | /**  |
|  |  * 最大容量  |
|  |  *   |
|  |  * Note： 用位运算就不需要将十进制转换为二进制，直接就为二进制。  |
|  |  */ |
|  | private final int MAX\_CAPACITY = 1 << 30;  |
|  |  |
|  | /**  |
|  |  * 缓存的容量  |
|  |  */ |
|  | private int capacity;  |
|  |  |
|  | public LRU(int capacity) {  |
|  | this(true, capacity);  |
|  |  }  |
|  |  |
|  | public LRU(boolean accessOrder, int capacity) {  |
|  | this(1 << 4, 0.75f, accessOrder, capacity);  |
|  |  }  |
|  |  |
|  | public LRU(int initialCapacity, float loadFactor, boolean accessOrder, int capacity) {  |
|  | super(initialCapacity, loadFactor, accessOrder);  |
|  | this.capacity = capacity;  |
|  |  } |
|  | } |


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

测试：

|  |  LRU lru = new LRU(10);  |
|  | for (int i = 0; i < 10; i++) {  |
|  |  lru.put(i, i * i);  |
|  |  System.out.println("put: (" + i + "," + i * i + ")");  |
|  | int randomKey = (int) (Math.random() * i);  |
|  |  System.out.println("get "+randomKey+": " + lru.get(randomKey));  |
|  |  System.out.println("head->"+lru+"<-tail");  |
|  |  } |


1
2
3
4
5
6
7
8
9
10
11
12

结果：

|  | put: (0,0) |
|  | get 0: 0 |
|  | head->{0=0}<-tail |
|  | --------------- |
|  | put: (1,1) |
|  | get 0: 0 |
|  | head->{1=1, 0=0}<-tail |
|  | --------------- |
|  | put: (2,4) |
|  | get 1: 1 |
|  | head->{0=0, 2=4, 1=1}<-tail |
|  | --------------- |


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16