一、基本概念
命中：访问缓存是通过key get到对应value
回源： miss了，未命中导致回读源数据
淘汰：缓存满了，那么就会按照某一种策略，把缓存中的旧对象踢出，而把新的对象加入缓存池。（只有5个存储单元，来了第6个元素。则考虑谁出队）
淘汰策略：即缓存算法，决定到底应该踢出哪些对象
缓存污染：不常用的数据加入进缓存，降低了缓存效率的现象
二、缓存淘汰算法LRU
LRU（Least recently used，最近最少使用）
原理：根据数据的历史访问记录，淘汰最近最少使用的元素
实现：链表，实现简单
1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。
package com.max.mybatis.LRU;
import java.util.HashMap;
public class LRUCache<K, V> {
private int currentCacheSize;
private int CacheCapcity;
private HashMap<K,CacheNode> caches;
private CacheNode first;
private CacheNode last;
public LRUCache(int size){
currentCacheSize = 0;
this.CacheCapcity = size;
caches = new HashMap<K,CacheNode>(size);
}
/**
* 插入元素 （超容量移除队尾元素，新元素插队头）
* 1.put前先校验缓存size已达最大容量，则remove 队尾的key
* 2.为超容量，则赋值node，并把node移动到队头
* @param k
* @param v
*/
public void put(K k,V v){
CacheNode node = caches.get(k);
if(node == null){
//1.put前先校验缓存size已达最大容量，则remove 队尾的key
if(caches.size() >= CacheCapcity){
caches.remove(last.key);
removeLast();
}
node = new CacheNode();
node.key = k;
}
node.value = v;
//2.把node移动到队头
moveToFirst(node);
caches.put(k, node);
}
/**
* 获取元素 命中后将该元素移至对头
* @param k
*/
public Object get(K k){
CacheNode node = caches.get(k);
if(node == null){
return null;
}
moveToFirst(node);
return node.value;
}
/**
* 获取元素 命中后将该元素移至对头
* @param k
*/
public Object remove(K k){
CacheNode node = caches.get(k);
if(node != null){
if(node.pre != null){
node.pre.next=node.next;
}
if(node.next != null){
node.next.pre=node.pre;
}
if(node == first){
first = node.next;
}
if(node == last){
last = node.pre;
}
}
return caches.remove(k);
}
public void clear(){
first = null;
last = null;
caches.clear();
}
private void moveToFirst(CacheNode node){
if(first == node){
return;
}
if(node.next != null){
node.next.pre = node.pre;
}
if(node.pre != null){
node.pre.next = node.next;
}
if(node == last){
last= last.pre;
}
if(first == null || last == null){
first = last = node;
return;
}
node.next=first;
first.pre = node;
first = node;
first.pre=null;
}
private void removeLast(){
if(last != null){
last = last.pre;
if(last == null){
first = null;
}else{
last.next = null;
}
}
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
CacheNode node = first;
while(node != null){
sb.append(String.format("%s:%s ", node.key,node.value));
node = node.next;
}
return sb.toString();
}
class CacheNode{
CacheNode pre;
CacheNode next;
Object key;
Object value;
public CacheNode(){
}
}
public static void main(String[] args) {
LRUCache<Integer,String> lru = new LRUCache<Integer,String>(3);
lru.put(1, "a"); // 1:a
System.out.println(lru.toString());
lru.put(2, "b"); // 2:b 1:a
lru.put(3, "c"); // 3:c 2:b 1:a
lru.put(4, "d"); // 4:d 3:c 2:b
lru.put(1, "aa"); // 1:aa 4:d 3:c
lru.get(1); // 1:aa 5:e 2:bb
lru.remove(12); // 1:aa 5:e 2:bb
lru.remove(1); //5:e 2:bb
}
}适用场景：当存在热点数据时，LRU的效率很好，
缺点：
1.命中时将命中元素移到头部，需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。O（n）
2.非热点数据，偶发性的、周期性的批量操作会导致LRU命中率急剧下降，造成缓存污染。
优化实现
双向链表+哈希表：
1、采用双向链表来实现元素(k-v键值对)的存储
2、同时采用hash表来存储相关的key与value的对应关系。
这样，我们既能在O(1)的时间对key进行操作，同时又能利用Double LinkedList的添加和删除节点的便利性。(get/set都能在O(1)内完成)。