一、LRU
1. LRU原理
LRU--Least Recent Used，在操作系统课程的虚拟内存章节曾经学过，当内存空间不够时需要对内存中的页进行淘汰。LRU即为一种淘汰策略，即淘汰掉最不经常使用的。
以下引用LRU原理和Redis实现——一个今日头条的面试题的图片简单说一下LRU的原理。
假设内存大小只能容纳三个页的大小，其中访问依照7 0 1 2 0 3 0 4的顺序访问，位于最上方的页即为最经常访问的，处于最下方的页为最不经常访问的。
2. LRU实现
我们可以通过使用HashMap和双向链表实现LRU
image
利用HashMap能在常数时间内定位到节点，并且可以通过双向链表访问相邻节点。若需要淘汰节点，可在常数时间内定位到尾部节点并移除；若需要插入或者访问节点，可在常数时间内将节点移至头部。
二、LinkedHashMap
LinkedHashMap的数据结构即为上文介绍LRU实现所采用的数据结构，并且实现了Map接口还继承了HashMap，有关于HashMap的知识点此处不会过多展开，可移步至我另一篇介绍HashMap的文章：我的HashMap果然有问题。
1. LinkedHashMap源码
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
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);
}
}
/**
* 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.
*/
final boolean accessOrder;
...
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and a default load factor (0.75).
*
* @param initialCapacity the initial capacity
* @throws IllegalArgumentException if the initial capacity is negative
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the default initial capacity (16) and load factor (0.75).
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
* the same mappings as the specified map. The <tt>LinkedHashMap</tt>
* instance is created with a default load factor (0.75) and an initial
* capacity sufficient to hold the mappings in the specified map.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
...
其中值得注意的就是accessOrder属性，若accessOrder为false则代表插入顺序，若为true则代表访问顺序。说人话就是在LinkedHashMap中维护的双向链表的顺序，当插入元素时LinkedHashMap会将所插入的元素插入双向链表表尾的位置，而当accessOrder为true时对其中的元素进行访问时，LinkedHashMap会将访问的元素移至双向链表最后端，反之则不会这么做。在LinkedHashMap的put和get方法中我们可以很清楚的看到。
LinkedHashMap的put方法并没有实现，使用的put方法为HashMap的put方法，此处不做介绍。但在HashMap的putVal源码中我们可以看到
这两个方法在HashMap中为空方法，在LinkedHashMap中对这两个方法进行了重写。
//有可能会删除最不常访问的节点，即LinkedHashMap实现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);
}
}
//将节点移至链表最后端
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还对HashMap.Node类进行重写，其中在newNode和newTreeNode方法中实现了对链表的插入。我看到这里不禁感叹多态的强大和灵活性，真的太强了。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
接下来是get方法
public V get(Object key) {
Node<K,V> e;
//getNode继承自HashMap
if ((e = getNode(hash(key), key)) == null)
return null;
//对accessOrder进行了判断，若为true则将节点移至尾部
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
//将节点移至链表尾部
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;
}
}
2. LinkedHashMap实现LRU
现在我们回过头来看看afterNodeInsertion方法。
//有可能会删除最不常访问的节点，即LinkedHashMap实现LRU的关键方法之一
//@param evict if false, the table is in creation mode.
//当调用put方法时，evict恒为true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;、
//其中对头节点（也为待删除节点）first进行removeEldestEntry(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的removeEldestEntry方法恒返回false，故永远无法触发删除头节点操作。但看到protected会想到什么？嘿嘿嘿，protected不就是给我们重写用的？接下来我将重写removeEldestEntry方法实现一个基于LinkedHashMap的简单LRU。
public class MyLRU extends LinkedHashMap {
//容量
private int mysize;
public MyLRU(int size) {
super(16, 0.75f, true);
this.mysize = size;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > mysize;
}
public static void main(String[] args) {
Map map = new MyLRU(3);
for (int i = 0; i < 5; i++) {
map.put(i, i);
if (i == 2) map.get(0);
}
System.out.println("size: " + map.size());
Iterator<Map.Entry> iterator=map.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry entry=iterator.next();
System.out.print(entry.getKey());
System.out.print(" ");
System.out.println(entry.getValue());
}
}
}
大功告成！
下面是私货时间
参考文献：
网友评论