缓存的本质是以空间换时间,那么缓存的容量大小肯定是有限的,当缓存被占满时,缓存中的那些数据应该被清理出去,那些数据应该被保留呢?这就需要缓存的淘汰策略来决定。
事实上,常用的缓存的淘汰策略有三种:先进先出算法(First in First out FIFO);淘汰一定时期内被访问次数最少的页面(Least Frequently Used LFU);淘汰最长时间未被使用的页面(Least Recently Used LRU)
这些算法在不同层次的缓存上执行时具有不同的效率,需要结合具体的场景来选择。
FIFO算法即先进先出算法,常采用队列实现。在缓存中,它的设计原则是:如果一个数据最先进入缓存中,则应该最早淘汰掉
LRU算法是根据对数据的历史访问次数来进行淘汰数据的,通常使用链表来实现。在缓存中,它的设计原则是:如果数据最近被访问过,那么将来它被访问的几率也很高。
步骤:
LFU 算法是根据数据的历史访问频率来淘汰数据,因此,LFU算法中的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。在缓存中,它的设计原则是:如果数据被访问多次,那么将来它的访问频率也会更高。
步骤:
利用双向链表与散列表的结合:
<Integer, ListNode>
,哈希表的键用于存储输入的 key,哈希表的值用于存储双向链表的节点moveNodeToLast(node)
import java.util.HashMap; //定义LIstNode class ListNode{ int key; int val; ListNode pre; ListNode next; public ListNode(){ } public ListNode(int key,int val){ this.key = key; this.val = val; } } public class LRU { private int capacity; public HashMap<Integer,ListNode> hashMap; //定义的双向链表 public ListNode head; public ListNode tail; //定义构造函数,初始化变量 public LRU(int capacity){ this.capacity = capacity; head = new ListNode(); tail = new ListNode(); head.next = tail; tail.pre = head; hashMap = new HashMap<>(); } //链表操作:删除某个节点 private void removeNode(ListNode listNode){ // listNode.pre = listNode.next; listNode.pre.next = listNode.next; listNode.next.pre = listNode.pre; } //链表操作:添加新的节点,添加到最后 private void appednList(ListNode listNode){ //将其添加到我们的虚拟列表的表尾部 tail.pre.next = listNode; listNode.pre = tail.pre; listNode.next = tail; tail.pre = listNode; } //链表:将节点从当前位置移动到链表最后 private void moveNode(ListNode listNode){ removeNode(listNode); appednList(listNode); } //redisCache操作_get 指定 key 节点 public int get(int key){ if(hashMap.containsKey(key)){ ListNode listNode = hashMap.get(key); //调整list Node 的位置 moveNode(listNode); return listNode.val; }else{ return -1; } } //想象为 redis 中的 put 操作 public void put(int key,int value){ if(hashMap.containsKey(key)){ ListNode listNode = hashMap.get(key); listNode.val = value; moveNode(listNode); } else { if(hashMap.size()==this.capacity){ //此时缓存区已满,需要进行刷新删除那些不需要的 //LRU删除最前面的即可 hashMap.remove(head.next); removeNode(head.next); } //满了就 flush 后添加,没满就直接添加 ListNode listNode = new ListNode(key,value); hashMap.put(key,listNode); appednList(listNode); } } }
测试代码:
import java.util.HashMap; public class LRUTest { public static void showHashMap(ListNode head){ ListNode node= head.next; System.out.println("==================="); while(node!=null && node.key!=0){ System.out.println(""+node.key+":"+node.val); node = node.next; } } public static void main(String[] args) { LRU lurCache = new LRU(5); lurCache.put(1,1); lurCache.put(2,2); lurCache.put(3,3); lurCache.put(4,4); lurCache.put(5,5); showHashMap(lurCache.head); lurCache.put(1,10); showHashMap(lurCache.head); lurCache.put(6,6); showHashMap(lurCache.head); } }