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

最近最少使用算法（LRU最近最少使用）缓存替换算法

news 2025/7/21 14:03:03

含义

最近最少使用算法（LRU）是一种缓存替换算法，用于在缓存空间有限的情况下，选择最少使用的数据项进行替换。该算法的核心思想是基于时间局部性原理，即刚被访问的数据在未来也很有可能被再次访问。

实现

LRU算法的实现可以通过一个双向链表和一个哈希表来完成。双向链表用于按照访问顺序维护缓存中的数据项，哈希表用于存储数据项的引用，以便快速定位和访问。

如果缓存未满，则直接将新的数据项插入链表头部。
如果缓存已满，则将链表尾部的数据项移除，并将新的数据项插入链表头部。

实现链表

1. 新数据插入到链表头部；
1. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
1. 当链表满的时候，将链表尾部的数据丢弃。

特点

存在问题：

当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。

复杂度 : 实现简单。

代价 :命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。（即：LRU算法的实现需要维护一个适当的数据结构，所以在实际应用中可能会有一定的开销。）

代码实现LRU

注意事项：

需要保证多线程下数据的一致性；

方法1、使用synchronized 字段保证线程同步；
方法2、使用Lock ，它是一个接口，用于支持更灵活的线程同步

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.Map;/*** 类说明：利用LinkedHashMap实现简单的缓存， 必须实现removeEldestEntry方法，具体参见JDK文档** @param <K>* @param <V>* @author dennis*/
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {private final int maxCapacity;private static final float DEFAULT_LOAD_FACTOR = 0.75f;private final Lock lock = new ReentrantLock();public LRULinkedHashMap(int maxCapacity) {super(maxCapacity, DEFAULT_LOAD_FACTOR, true);this.maxCapacity = maxCapacity;}@Overrideprotected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {return size() > maxCapacity;}@Overridepublic boolean containsKey(Object key) {try {lock.lock();return super.containsKey(key);} finally {lock.unlock();}}@Overridepublic V get(Object key) {try {lock.lock();return super.get(key);} finally {lock.unlock();}}@Overridepublic V put(K key, V value) {try {lock.lock();return super.put(key, value);} finally {lock.unlock();}}public int size() {try {lock.lock();return super.size();} finally {lock.unlock();}}public void clear() {try {lock.lock();super.clear();} finally {lock.unlock();}}public Collection<Map.Entry<K, V>> getAll() {try {lock.lock();return new ArrayList<Map.Entry<K, V>>(super.entrySet());} finally {lock.unlock();}}
}

测试代码：测试结果见备注已经抛弃了`test1` 而替换为了最近一次使用过的`test3`

@Test
public  void a1() {LRULinkedHashMap lruLinkedHashMap = new LRULinkedHashMap(3);lruLinkedHashMap.put("test","1235314");lruLinkedHashMap.put("test1","1235314");lruLinkedHashMap.get("test");lruLinkedHashMap.put("test2","1235314");System.out.println(lruLinkedHashMap.getAll()); // [test1=1235314, test=1235314, test2=1235314]lruLinkedHashMap.put("test3","1235314");System.out.println(lruLinkedHashMap.getAll()); // [test=1235314, test2=1235314, test3=1235314]
}