LRU
LRU，最近最少使用，把数据加入一个链表中，按访问时间排序，发生淘汰的时候，把访问时间最旧的淘汰掉。
比如有数据 1，2，1，3，2
此时缓存中已有（1，2）
当3加入的时候，得把后面的2淘汰，变成（3，1）
显然
LRU对于循环出现的数据，缓存命中不高
比如，这样的数据，1，1，1，2，2，2，3，4，1，1，1，2，2，2.....
当走到3，4的时候，1，2会被淘汰掉，但是后面还有很多1，2
LRU的一个实现方法：
用一个双向链表记录访问时间，因为链表插入删除高效，时间新的在前面，旧的在后面。 用一个哈希表记录缓存(key, value)，哈希查找近似O(1)，发生哈希冲突时最坏O(n)， 同时哈希表中得记录 (key, Node(key, value))
package algorithm.cache;
import java.util.HashMap;
import java.util.Map;
public class LRUCache<E> {
private Map<Object, DoublyLinkedNode<E>> data;
//容量
private int capacity;
private DoublyLinkedNode<E> head;
private DoublyLinkedNode<E> tail;
public LRUCache() {
this(10);
}
public LRUCache(int capacity) {
data = new HashMap<>(capacity, 1);
this.capacity = capacity;
}
public int Size() {
return this.data.size();
}
public void put(Object key, E element) {
DoublyLinkedNode<E> newNode = new DoublyLinkedNode();
newNode.key = key;
newNode.element = element;
if (this.data.containsKey(key)) {
DoublyLinkedNode<E> oldNode = this.data.get(key);
this.remove(key, oldNode);
}
if (data.size() == this.capacity) {
removeFail();
}
this.add(key, newNode);
if (data.size() == 1) {
this.head = newNode;
this.tail = newNode;
this.head.next = this.tail;
this.tail.pre = this.head;
}
}
private void removeFail() {
DoublyLinkedNode<E> item = this.tail;
this.tail = item.pre;
data.remove(item.key);
}
private void add(Object key, DoublyLinkedNode<E> item) {
item.next = this.head;
if (this.head != null) {
this.head.pre = item;
}
this.head = item;
data.put(key, item);
}
private void remove(Object key, DoublyLinkedNode<E> item) {
if (item.equals(this.tail)){
this.tail = item.pre;
}
if (item.pre != null) {
item.pre.next = item.next;
}
if (item.next != null) {
item.next.pre = item.pre;
}
data.remove(key);
}
public E get(Object key) {
if (!data.containsKey(key)) {
return null;
}
DoublyLinkedNode<E> item = data.get(key);
this.remove(key, item);
this.add(key, item);
return item.element;
}
private class DoublyLinkedNode<E> {
Object key;
E element;
DoublyLinkedNode pre;
DoublyLinkedNode next;
}
public static void main(String[] args) {
LRUCache<Integer> cache = new LRUCache<>(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println("get 1 = " + cache.get(1));
System.out.println("add 3");
cache.put(3, 3); // 该操作会使得关键字 2 作废
System.out.println("get 2 = " + cache.get(2));
System.out.println("add 4");
cache.put(4, 4); // 该操作会使得关键字 1 作废
System.out.println("get 3 = " + cache.get(3));
System.out.println("get 4 = " + cache.get(4));
System.out.println("get 1 = " + cache.get(1));
}
}
get 1 = 1
add 3
get 2 = null
add 4
get 3 = 3
get 4 = 4
get 1 = null
java官方实现 LinkedHashMap
LinkedHashMap底层就是用的HashMap加双链表实现的，而且本身已经实现了按照访问顺序的存储。 此外，LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数， 方法默认是直接返回false，不会移除元素，所以需要重写该方法。即当缓存满后就移除最不常用的数。
public class LRU<K,V> {
private static final float hashLoadFactory = 0.75f;
private LinkedHashMap<K,V> map;
private int cacheSize;
public LRU(int cacheSize) {
this.cacheSize = cacheSize;
int capacity = (int)Math.ceil(cacheSize / hashLoadFactory) + 1;
map = new LinkedHashMap<K,V>(capacity, hashLoadFactory, true){
private static final long serialVersionUID = 1;
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > LRU.this.cacheSize;
}
};
}
public synchronized V get(K key) {
return map.get(key);
}
public synchronized void put(K key, V value) {
map.put(key, value);
}
public synchronized void clear() {
map.clear();
}
public synchronized int usedSize() {
return map.size();
}
public void print() {
for (Map.Entry<K, V> entry : map.entrySet()) {
System.out.print(entry.getValue() + "--");
}
System.out.println();
}
}
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。
扩展
LRU-K
LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。 相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。
数据第一次被访问时，加入到历史访问列表，如果书籍在访问历史列表中没有达到K次访问，则按照一定的规则（FIFO,LRU）淘汰；当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列中删除，将数据移到缓存队列中，并缓存数据，缓存队列重新按照时间排序；缓存数据队列中被再次访问后，重新排序，需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即“淘汰倒数K次访问离现在最久的数据”。 LRU-K具有LRU的优点，同时还能避免LRU的缺点，实际应用中LRU-2是综合最优的选择。由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象，因此内存消耗会比LRU要多。
two queue
Two queues（以下使用2Q代替）算法类似于LRU-2，不同点在于2Q将LRU-2算法中的访问历史队列（注意这不是缓存数据的）改为一个FIFO缓存队列，即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。当数据第一次访问时，2Q算法将数据缓存在FIFO队列里面，当数据第二次被访问时，则将数据从FIFO队列移到LRU队列里面，两个队列各自按照自己的方法淘汰数据。
新访问的数据插入到FIFO队列中，如果数据在FIFO队列中一直没有被再次访问，则最终按照FIFO规则淘汰；如果数据在FIFO队列中再次被访问到，则将数据移到LRU队列头部，如果数据在LRU队列中再次被访问，则将数据移动LRU队列头部，LRU队列淘汰末尾的数据。
Multi Queue(MQ)
MQ算法根据访问频率将数据划分为多个队列，不同的队列具有不同的访问优先级，其核心思想是：优先缓存访问次数多的数据。详细的算法结构图如下，Q0，Q1....Qk代表不同的优先级队列，Q-history代表从缓存中淘汰数据，但记录了数据的索引和引用次数的队列：
新插入的数据放入Q0，每个队列按照LRU进行管理，当数据的访问次数达到一定次数，需要提升优先级时，将数据从当前队列中删除，加入到高一级队列的头部；为了防止高优先级数据永远不会被淘汰，当数据在指定的时间里没有被访问时，需要降低优先级，将数据从当前队列删除，加入到低一级的队列头部；需要淘汰数据时，从最低一级队列开始按照LRU淘汰，每个队列淘汰数据时，将数据从缓存中删除，将数据索引加入Q-history头部。如果数据在Q-history中被重新访问，则重新计算其优先级，移到目标队列头部。Q-history按照LRU淘汰数据的索引。
MQ需要维护多个队列，且需要维护每个数据的访问时间，复杂度比LRU高。
LRU算法对比
| 对比点 | 对比 |
|---|---|
| 命中率 | LRU-2 > MQ(2) > 2Q > LRU |
| 复杂度 | LRU-2 > MQ(2) > 2Q > LRU |
| 代价 | LRU-2 > MQ(2) > 2Q > LRU |
实现带有过期时间的LRU
// 构造方法：只要有缓存了，过期清除线程就开始工作
public LRU() {
swapExpiredPool.scheduleWithFixedDelay(new ExpiredNode(), 3,3,TimeUnit.SECONDS);
}
public class ExpiredNode implements Runnable {
@Override
public void run() {
// 第一步：获取当前的时间
long now = System.currentTimeMillis();
while (true) {
// 第二步：从过期队列弹出队首元素，如果不存在，或者不过期就返回
Node node = expireQueue.peek();
if (node == null || node.expireTime > now)return;
// 第三步：过期了那就从缓存中删除，并且还要从队列弹出
cache.remove(node.key);
expireQueue.poll();
}// 此过程为while(true)，一直进行判断和删除操作
}
}