当前位置：首页 > news >正文

LRU缓存

news 2025/11/23 22:46:59

LRU缓存（Least Recently Used，最近最少使用）是一种数据缓存机制，旨在解决计算机内存中数据的替换问题。当缓存空间不足时，LRU缓存会淘汰最近最久未被使用的数据，以确保缓存中始终存储着最新和最频繁使用的数据。

在这里插入图片描述

class LRUCache {
class Node{int key,val;Node pre,next;public Node(){}public Node(int key,int val){this.key = key;this.val = val;}
}
private ConcurrentHashMap<Integer,Node> cache = new ConcurrentHashMap<>();
private int size;
private int capacity;
private Node head = new Node();
private Node tail = new Node();public LRUCache(int capacity) {this.capacity = capacity;size = 0;head.next = tail;tail.pre = head;}public int get(int key) {Node node = cache.get(key);if(node == null)return -1;moveToHead(node);return node.val;}public void put(int key, int value) {Node node = cache.get(key);if(node != null){node.val = value;moveToHead(node);}else{Node newNode = new Node(key,value);cache.put(key,newNode);addToHead(newNode);++size;if(size > capacity){Node removeNode = removeTail();cache.remove(removeNode.key);--size;}}}public void moveToHead(Node node){removeNode(node);addToHead(node);}public void removeNode(Node node){node.pre.next = node.next;node.next.pre = node.pre;}public void addToHead(Node node){node.pre = head;node.next  = head.next;head.next.pre = node;head.next = node;}public Node removeTail(){Node removeNode = tail.pre;removeNode(removeNode);return removeNode;}
}