通过分析LinkedHashMap了解LRU
通过分析LinkedHashMap了解LRU
我们都知道LRU是最近最少使用,根据数据的历史访问记录来进行淘汰数据的。其核心思想是如果数据最近被访问过，那么将来访问的几率也更高。在这里提一下，Redis缓存和MyBatis二级缓存更新策略算法中就有LRU。画外音：LFU是频率最少使用，根据数据历史访问的频率来进行淘汰数据。其核心思想是如果数据过去被访问多次，那么将来访问的几率也更高。
图文无关.png
分析LinkedHashMap中的LRU
其实一提到LRU，我们就应该想到LinkedHashMap。LRU是通过双向链表来实现的。当某个位置的数据被命中，通过调整该数据的位置，将其移动至尾部。新插入的元素也是直接放入尾部(尾插法)。这样一来，最近被命中的元素就向尾部移动，那么链表的头部就是最近最少使用的元素所在的位置。
HashMap的afterNodeAccess()、afterNodeInsertion()、afterNodeRemoval()方法都是空实现，留着LinkedHashMap去重写。LinkedHashMap靠重写这3个方法就完成了核心功能的实现。不得不感叹，LinkedHashMap设计之妙。
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { } 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;
}
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);
}
}
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != 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;
}
}在LinkedHashMap的get()方法中，我们每次获取元素的时候，都要调用afterNodeAccess(e)都要将元素移动到尾部。话外音：accessOrder为true，是基于访问排序，accessOrder为基于插入排序。我们想要LinkedHashMap实现LRU功能，accessOrder必须为true。如果accessOrder为false，那就是FIFO了。
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;
}我们可以看到插入数据的时候，如果removeEldestEntry(first)返回true，按照LRU策略，那么会删除头节点。
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);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}LinkedHashMap大体的LRU架子都为我们搭好了。那我们怎么去基于LinkedHashMap实现LRU呢。先别慌，我们先看看MyBatis中的LruCache是怎么实现的。
public class LruCache implements Cache {
private final Cache delegate;
private Map<Object, Object> keyMap;
private Object eldestKey;
public LruCache(Cache delegate) {
this.delegate = delegate;
setSize(1024);
}
@Override
public String getId() {
return delegate.getId();
}
@Override
public int getSize() {
return delegate.getSize();
}
public void setSize(final int size) {
keyMap = new LinkedHashMap<Object, Object>(size, .75F, true) {
private static final long serialVersionUID = 4267176411845948333L;
@Override
protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
boolean tooBig = size() > size;
if (tooBig) {
eldestKey = eldest.getKey();
}
return tooBig;
}
};
}
@Override
public void putObject(Object key, Object value) {
delegate.putObject(key, value);
cycleKeyList(key);
}
@Override
public Object getObject(Object key) {
keyMap.get(key); //touch
return delegate.getObject(key);
}
@Override
public Object removeObject(Object key) {
return delegate.removeObject(key);
}
@Override
public void clear() {
delegate.clear();
keyMap.clear();
}
@Override
public ReadWriteLock getReadWriteLock() {
return null;
}
private void cycleKeyList(Object key) {
keyMap.put(key, key);
if (eldestKey != null) {
delegate.removeObject(eldestKey);
eldestKey = null;
}
}
}我们可以照葫芦画瓢，来手写LRU。其实我们只要把accessOrder设置为true，重写removeEldestEntry(eldest)即可。我们在removeEldestEntry(eldest)加上什么时候执行LRU操作的逻辑，比如map里面的元素数量超过指定的大小，开始删除最近最少使用的元素，为后续新增的元素腾出位置来。
我们来看看自己手写的LRU例子
1.首先往map里面添加了5个元素，使用的是尾插法，顺序应该是1,2,3,4,5。
2.调用了map.put("6", "6")，通过尾插法插入元素6，此时的顺序是1,2,3,4,5,6，然后 LinkedHashMap调用removeEldestEntry()，map里面的元素数量是6，大于指定的size，返回true。LinkedHashMap会删除头节点的元素，此时顺序应该是2,3,4,5,6。
3.调用了map.get("2")，元素2被命中，元素2需要移动到链表尾部，此时的顺序是3,4,5,6,2
4.调用了map.put("7", "7")，和步骤2一样的操作。此时的顺序是4,5,6,2,7
5.调用了map.get("4"),和步骤3一样的操作。此时的顺序是5,6,2,7,4
@Test
public void test1() {
int size = 5;
/**
* false, 基于插入排序
* true, 基于访问排序
*/
Map<String, String> map = new LinkedHashMap<String, String>(size, .75F,
false) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
boolean tooBig = size() > size;
if (tooBig) {
System.out.println("最近最少使用的key=" + eldest.getKey());
}
return tooBig;
}
};
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");
map.put("4", "4");
map.put("5", "5");
System.out.println(map.toString());
map.put("6", "6");
map.get("2");
map.put("7", "7");
map.get("4");
System.out.println(map.toString());
}HashMap来实现LRU
上面我们是用LinkedHashMap里面搭好的LRU架子来实现LRU的。现在我们脱离LinkedHashMap这个容器，手动去维护链表中元素的关系，也就是仿照LinkedHashMap里面的LRU实现写出属于自己的afterNodeRemoval()、afterNodeInsertion()、afterNodeAccess()方法。其实也是照着葫芦画瓢，只不过这一次难度升了几颗星。
话外音：HashMap的查询、插入、修改、删除平均时间复杂度都是O(1)。最坏的情况是所有的key都散列到一个Entry中，时间复杂度会退化成O(N)。这就是为什么Java8的HashMap引入了红黑树的原因。当Entry中的链表长度超过8，链表会进化成红黑树。红黑树是一个自平衡二叉查找树，它的查询/插入/修改/删除的平均时间复杂度为O(log(N))。
尾插法
1.首先我们采用的是尾插法，也就是新插入的元素或者命中的元素往尾部移动，头部的元素即是最近最少使用。
public class MyLru01<K, V> {
private int maxSize;
private Map<K, Entry<K, V>> map;
private Entry head;
private Entry tail;
public MyLru01(int maxSize) {
this.maxSize = maxSize;
map = new HashMap<>();
}
public void put(K key, V value) {
Entry<K, V> entry = new Entry<>();
entry.key = key;
entry.value = value;
afterEntryInsertion(entry);
map.put(key, entry);
if (map.size() > maxSize) {
map.remove(head.key);
afterEntryRemoval(head);
}
}
private void afterEntryInsertion(Entry<K, V> entry) {
if (entry != null) {
if (head == null) {
head = entry;
tail = head;
return;
}
if (tail != entry) {
Entry<K, V> pred = tail;
entry.before = pred;
tail = entry;
pred.after = entry;
}
}
}
private void afterEntryAccess(Entry<K, V> entry) {
Entry<K, V> last;
if ((last = tail) != entry) {
Entry<K, V> p = entry, b = p.before, a = p .after;
p.before = p.after = null;
if (b == null) {
head = a;
} else {
b.after = a;
}
if (a == null) {
last = b;
} else {
a.before = b;
}
if (last == null) {
head = p;
} else {
p.before = last;
last.after = p;
}
tail = p;
}
}
private Entry<K, V> getEntry(K key) {
return map.get(key);
}
public V get(K key) {
Entry<K, V> entry = this.getEntry(key);
if (entry == null) {
return null;
}
afterEntryAccess(entry);
return entry.value;
}
public void remove(K key) {
Entry<K, V> entry = this.getEntry(key);
afterEntryRemoval(entry);
}
private void afterEntryRemoval(Entry<K, V> entry) {
if (entry != null) {
Entry<K, V> p = entry, 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;
}
}
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
Entry<K, V> entry = head;
while (entry != null) {
sb.append(String.format("%s:%s", entry.key, entry.value));
sb.append(" ");
entry = entry.after;
}
return sb.toString();
}
static final class Entry<K, V> {
private Entry before;
private Entry after;
private K key;
private V value;
}
public static void main(String[] args) {
MyLru01<String, String> map = new MyLru01<>(5);
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");
map.put("4", "4");
map.put("5", "5");
System.out.println(map.toString());
map.put("6", "6");
map.get("2");
map.put("7", "7");
map.get("4");
System.out.println(map.toString());
}
}2.运行结果也是5,6,2,7,4,与之前用LinkedHashMap实现的LRU运行结果一致。后面会分析写代码的思路。
image.png
3.定义Entry中的双向链表结构。
static final class Entry<K, V> {
private Entry before;
private Entry after;
private K key;
private V value;
}4.把key，value包装成Entry节点。调用afterEntryInsertion(entry)方法，把Entry节点移动到双向链表尾部。然后将key,Entry放入到HashMap中。如果map中元素的数量大于maxSize，则删除双向链表中的头结点(头结点所在的元素就是最近最少使用的元素)。首先在map中删除head.key对应着的元素，然后调用 afterEntryRemoval(head)，在双向链表中删除头节点。
public void put(K key, V value) {
Entry<K, V> entry = new Entry<>();
entry.key = key;
entry.value = value;
afterEntryInsertion(entry);
map.put(key, entry);
if (map.size() > maxSize) {
map.remove(head.key);
afterEntryRemoval(head);
}
}5.如果双向链表head节点为空的话，证明双向链表为空。那么我们把新插入的元素置为head节点和tail节点。否则我们把插入当前节点至尾部。这里是怎么插入呢？tail节点之前是尾部节点，现在突然要插入一个节点(entry节点)。那么tail节点再也不能占据尾部的位置，我们把置它为pre节点。pre节点也就是新的tail节点(也就是entry节点)的前一个节点。entry的先驱节点指向pre，pre节点的后继节点指向entry，这样就完成了尾插入。
private void afterEntryInsertion(Entry<K, V> entry) {
if (entry != null) {
if (head == null) {
head = entry;
tail = head;
return;
}
if (tail != entry) {
Entry<K, V> pred = tail;
entry.before = pred;
tail = entry;
pred.after = entry;
}
}
}6.我们是怎么在双向链表中删除一个节点呢？现在要删除的节点是entry节点。我们首先获取它的先驱节点b和后继节点a。如果b等于null，那么删除entry节点后，head节点应该为a。如果b不等于null，b的后继节点应该指向a。同样如果a等于null，那么删除entry节点后，tail节点应该为b。如果a不等于null，a的先驱节点应该指向b。这样就完成删除操作，如果还没明白的话，自己拿个笔画张图就差不多了。
public void afterEntryRemoval(Entry<K, V> entry) {
if (entry != null) {
Entry<K, V> p = entry, 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;
}
}
}7.我们通过get()方法命中了entry节点。那么我们怎么把entry节点移动至双向链表中的尾部呢？如果当前节点已位于尾部，那么我们什么也不做。如果当前节点不在尾部，和上面操作一样首先获取它的先驱节点b和后继节点a。然后把先驱节点和后继节点都置为null，方便后续操作。
如果b节点等于null，那么移动entry节点至尾部后，head节点应该为a节点。
如果b节点不等于null，那么b的后继节点应该指向a。
如果a节点等于null，那么新的尾部节点的前一个节点应该为b。
如果a节点不等于null，那么a的先驱节点应该指向b。
如果last节点(也就是新尾部节点的前一个节点)等于null的话，说明head节点应该为p节点。
如果last节点不等于null的话，我们把p的先驱节点指向last，last的后继节点指向p。最后新的尾部节点就是p。
过程有点绕，如果不明白的话，可以动手画图。
private void afterEntryAccess(Entry<K, V> entry) {
Entry<K, V> last;
if ((last = tail) != entry) {
Entry<K, V> p = entry, b = p.before, a = p .after;
p.before = p.after = null;
if (b == null) {
head = a;
} else {
b.after = a;
}
if (a == null) {
last = b;
} else {
a.before = b;
}
if (last == null) {
head = p;
} else {
p.before = last;
last.after = p;
}
tail = p;
}
}头插法
头插法其实和尾插法大同小异，区别就是新插入的节点或者是命中的节点都移动至双向链表的头部，那么双向链表的尾部节点中所在的元素就是最近最少使用的元素。
头插法.png
头插法的代码实现和尾插法基本一致，只是afterEntryInsertion()和afterEntryAccess()方法有所改动。改动的地方其实可以用上面的文字概括了！
再来说说下面例子中元素位置变化的过程吧 1.因为头插入法，5个元素插入完毕后。顺序应该是5,4,3,2,1
2.执行map.put("6", "6")后，把元素6插入到头部，并删除掉尾部元素1，顺序是6,5,4,3,2。
3.执行map.get("2")后，将元素2移动到头部，顺序是2,6,5,4,3
4.执行map.put("7", "7")后，把元素7插入到头部，并删除掉尾部元素,3，顺序是7,2,6,5,4
5.执行map.get("4")后，把元素4移动到头部，最后的顺序是4,7,2,6,5
image.png
/**
* @author cmazxiaoma
* @version V1.0
* @Description: TODO
* @date 2018/9/3 9:19
*/
public class MyLru02<K, V> {
private int maxSize;
private Map<K, Entry<K, V>> map;
private Entry<K, V> head;
private Entry<K, V> tail;
public MyLru02(int maxSize) {
this.maxSize = maxSize;
map = new HashMap<>();
}
public void put(K key, V value) {
Entry<K, V> entry = new Entry<>();
entry.key = key;
entry.value = value;
afterEntryInsertion(entry);
map.put(key, entry);
if (map.size() > maxSize) {
map.remove(tail.key);
afterEntryRemoval(tail);
}
}
public void afterEntryInsertion(Entry<K, V> entry) {
if (entry != null) {
if (head == null) {
head = entry;
tail = head;
return;
}
// if entry is not head
if (head != entry) {
entry.after = head;
entry.before = null;
head.before = entry;
head = entry;
}
}
}
public void afterEntryRemoval(Entry<K, V> entry) {
if (entry != null) {
Entry<K, V> p = entry, 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;
}
}
}
public void afterEntryAccess(Entry<K, V> entry) {
Entry<K, V> first;
if ((first = head) != entry) {
Entry<K, V> p = entry, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null) {
first = a;
} else {
b.after = a;
}
if (a == null) {
tail = b;
} else {
a.before = b;
}
if (first == null) {
tail = p;
} else {
p.after = first;
first.before = p;
}
head = p;
}
}
public void remove(K key) {
Entry<K, V> entry = this.getEntry(key);
afterEntryRemoval(entry);
}
public V get(K key) {
Entry<K, V> entry = this.getEntry(key);
if (entry == null) {
return null;
}
afterEntryAccess(entry);
return entry.value;
}
private Entry<K, V> getEntry(K key) {
Entry<K, V> entry = map.get(key);
if (entry == null) {
return null;
}
return entry;
}
@Override
public String toString() {
Entry<K, V> p = head;
StringBuffer sb = new StringBuffer();
while(p != null) {
sb.append(String.format("%s:%s", p.key, p.value));
sb.append(" ");
p = p.after;
}
return sb.toString();
}
static final class Entry<K, V> {
private Entry<K, V> before;
private Entry<K, V> after;
private K key;
private V value;
}
public static void main(String[] args) {
MyLru02<String, String> map = new MyLru02<>(5);
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");
map.put("4", "4");
map.put("5", "5");
System.out.println(map.toString());
map.put("6", "6");
map.get("2");
map.put("7", "7");
map.get("4");
System.out.println(map.toString());
}
}尾言
大家好，我是cmazxiaoma(寓意是沉梦昂志的小马)，感谢各位阅读本文章。 小弟不才。 如果您对这篇文章有什么意见或者错误需要改进的地方,欢迎与我讨论。 如果您觉得还不错的话,希望你们可以点个赞。 希望我的文章对你能有所帮助。 有什么意见、见解或疑惑，欢迎留言讨论。
最后送上：心之所向，素履以往。生如逆旅，一苇以航。
saoqi.png
腾讯云开发者
