lru缓存算法的实现-爱代码爱编程
简单介绍LRU缓存算法：
LRU（Least recently used）即最近最少使用。将数据添加到缓存中，当缓存满了的时候，移除最近最少访问的数据，留出空间存放新添加的数据。
1. LRU缓存算法的基本结构
- 缓存大小 + hashmap + 双向链表
- 操作包含两个：
- put()：添加数据到缓存
- get()：获取缓存中的数据
2. 操作描述
get()操作：
- 先判断哈希表中是否存在key
- 如果不存在则直接返回-1
- 如果存在，则通过hashmap定位到链表中key对应的节点，删除该节点，然后在链表尾部插入一个相同的节点（通过删除+添加 替换移动操作，因为移动时间复杂度更高），返回key对应节点的value值
put()操作：
- 先判断哈希表中是否存在key
- 如果存在，则通过hashmap定位到链表中key对应的节点，更新该节点的value为put的新value值，删掉，然后在尾部插入一个相同的节点
- 如果不存在，则在链表尾部插入新节点（同时往hashmap中添加key），再判断链表长度是否超过缓存容量上限，如果超了，则删掉链表的头部节点（同时删除hashmap中对应的key），如果没超，则不做任何处理
3. 基于HashMap和双向链表的原生实现
import java.util.HashMap;
/**
* LRU缓存算法实现：基于HashMap+双向链表
* O(1)复杂度实现get()和put()操作
*/
public class LRUCache{
private int cap; // 缓存大小
private HashMap<Integer, Node> map; // hashmap
public DoubleList cache; // 双向链表
class Node {
public int key, val;
public Node prev, next;
public Node(int key, int val){
this.key = key;
this.val = val;
}
}
class DoubleList {
private Node head, tail;
private int size;
/**
* 初始化双向链表
*/
public DoubleList(){
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
size = 0;
}
/**
* 在链表尾部添加节点
* @param node
*/
public void addLast(Node node){
tail.prev.next = node;
node.prev = tail.prev;
node.next = tail;
tail.prev = node;
map.put(node.key, node); // 将该节点的信息放入map中
size++;
}
/**
* 移除节点
* @param node
*/
public void remove(Node node){
node.prev.next = node.next;
node.next.prev = node.prev;
map.remove(node.key); // 从map中移除该节点的信息
size--;
}
/**
* 移除链表头部节点
* @return
*/
public Node removeFirst(){
if(head.next == tail){
return null;
}
Node first = head.next;
remove(first);
return first;
}
public int size(){
return this.size;
}
}
/**
* 构造函数：初始化缓存大小，HashMap和DoubleList
* @param cap
*/
public LRUCache(int cap){
this.cap = cap;
map = new HashMap<>();
cache = new DoubleList();
}
/**
* 添加的时候，先判断原map中有没有该node：
* 有的话，先移除，再在链表尾部添加该node（保证节点最近刚被访问）
* 没有的话，在链表尾部添加该node，然后判断有没有超出缓存容量：
* 有的话，移除头部节点（最久没被访问）
* 没有的话，不做任何处理
* @param key
* @param val
*/
public void put(int key, int val){
Node node = new Node(key, val);
if(map.containsKey(key)){
cache.remove(node);
cache.addLast(node);
}else{
cache.addLast(node); // 在尾部添加新的节点
if(cache.size > this.cap){ // 超出缓存容量大小
cache.removeFirst(); // 移除头部最久未被访问的节点
}
}
}
/**
* 获取的时候，先判断原map中有没有该node：
* 没有的话直接返回-1，表示不存在
* 有的话则先删除，再将该node添加到链表尾部（保证其最近刚被访问）
*/
public Integer get(int key){
if(!map.containsKey(key)){
return -1;
}
Node node = map.get(key);
cache.remove(node);
cache.addLast(node);
return map.get(key).val;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(3);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
cache.put(4, 4);
System.out.println(cache.get(3));
Node p = cache.cache.head;
// 依次打印缓存中的node值
System.out.println("------cache-------");
while (p!= null) {
System.out.println(p.val);
p = p.next;
}
}
}
4. 基于LinkedHashMap的实现
import java.util.LinkedHashMap;
/**
* LRU缓存算法实现：基于LinkedHashMap
*/
public class LRUCache1 {
private int cap;
private LinkedHashMap<Integer, Integer> cache;
public LRUCache1(int cap){
this.cap = cap;
cache = new LinkedHashMap<>();
}
public Integer get(int key){
if(!cache.containsKey(key)){
return -1;
}else{
Integer val = cache.get(key);
cache.remove(key);
cache.put(key, val);
return val;
}
}
public void put(int key, int val){
if(cache.containsKey(key)){
cache.remove(key);
cache.put(key, val);
}else{
cache.put(key, val);
if(cache.size() >= cap){ // 如果超出缓存，则移除最久未被访问的元素（头部）
Integer first = cache.keySet().iterator().next();
cache.remove(first);
}
}
}
public static void main(String[] args) {
LRUCache1 cache1 = new LRUCache1(4); // 初始化大小为4的缓存
cache1.put(1, 1);
cache1.put(2, 2);
cache1.put(3, 3);
System.out.println("获取key为1的缓存：" + cache1.get(1)); // 查询key为1的缓存后，元素顺序：2 3 1
cache1.put(4, 4); // 添加后，元素顺序：2 3 1 4
cache1.put(5, 5); // 此时缓存容量满了（在尾部添加新元素后，需要删除头部元素），添加后，元素顺序：3 1 4 5
System.out.println(cache1.cache);
}
}