labuladong公众号算法学习笔记

LRU算法

LRU算法算法描述算法设计代码实现

LRU算法

LRU算法是一种缓存淘汰策略。 LRU全称为Least Recently Used，也就是我们认为最近使用过的数据应该是有用的。

算法描述

//缓存容量为2 LRUCache cache = new LRUCache(2); //可以理解为队列，左为队头，右为队尾。 //最近使用的在队头，久未使用的在队尾。 //圆括号表示键值对（key,val） cache.put(1,1);//cache=[(1,1)] cache.put(2,2);//cache=[(2,2),(1,1)] cache.get(1);//返回1，由于最近使用了1，所以cache=[(1,1),(2,2)] cache.put(3,3); //放入，由于容量已满，所以删除久未使用的的内容（即队尾数据） //然后将新数据插入队头 //cache=[(3,3),(1,1)] cache.get(2);//2不存在，返回-1，未找到 cache.put(1,4); //cache=[(1,4),(3,3)] //键1已经存在，把原始值1覆盖为4,同时要把键值对提前到队头

算法设计

cache数据结构的必要条件：

元素必须有时序，以区分最近使用的和久未使用的的数据，当容量满后要删除最久未使用的元素腾出来位置在cache中快速找到某个key是否已存在并得到对应的val每次访问cache的key需要将这个元素变为最近使用的，要支持在任意位置快速插入和删除元素

即，哈希链表，是哈希表和双向链表的结合体。

代码实现

（先自己实现LRU，便于理解） 链表节点：

class Node{ public int key,val; public Node next,prev; public Node(int k,int v){ this.key=k; this.val=v; } }

双链表：

class DoubleList{ //头尾虚节点 private Node head,tail; //链表元素数 private int size; public DoubleList(){ //初始化双向链表的数据 head = new Node(0,0); tail = new Node(0,0); head.next = tail; tail.prev = head; size=0; } //在链表尾部添加节点x public void addLast(Node x){ x.prev = tail.prev; x.next = tail; tail.prev.next = x; tail.prev = x; size++; } //删除链表的x节点 public void remove(Node x){ x.prev.next = x.next; x.next.prev = x.prev; size--; } //删除链表中第一个节点，并返回该节点 public Node removeFirst(){ if(head.next == tail) return null; Node first = head.next; remove(first); return first; } //返回链表长度 public int size(){return size;} }

靠尾部的数据是最近使用的，靠头部的数据是最久未使用的

class LRUCache{ //key->Node(key,val) private HashMap<Integer,Node> map; //Node(k1,v1)<->Node(k2,v2) private DoubleList cache; private int cap; public LRUCache(int capacity){ this.cap=capacity; map = new HashMap<>(); cache = new DoubleList(); } //将某个key提升为最近使用的 private void makeRecently(int key){ Node x = map.get(key); //先删除这个节点 cache.remove(x); //重新查到队尾 cache.addLast(x); } //添加最近使用的元素 private void addRecently(int key,int val){ Node x = new Node(key,val); cache.addLast(x); map.put(key,x); } //删除某个key private void deleteKey(int key){ Node x = map.get(key); cache.remove(x); map.remove(key); } //删除最久未使用的的元素 private void removeLeastRecently(){ Node deleteNode = cache.removeFirst(); int deleteKey = deleteNode.key; map.remove(deleteKey); } public int get(int key){ if(!map.containsKey) return 01; makeRecently(key); return map.get(key).val; } public void put(int key,int val){ if(map.containsKey(key)){ //删除旧元素 deleteKey(key); //新插入的元素为最近使用的数据 addRecently(key,val); return; } if(cap == cache.size()) removeLeastRecently(); addRecently(key,val); } }

（利用java自带库）