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

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

article 2025/1/30 13:34:26

含义

最近最少使用算法（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;
    }

    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }

    @Override
    public boolean containsKey(Object key) {
        try {
            lock.lock();
            return super.containsKey(key);
        } finally {
            lock.unlock();
        }
    }


    @Override
    public V get(Object key) {
        try {
            lock.lock();
            return super.get(key);
        } finally {
            lock.unlock();
        }
    }

    @Override
    public 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]
}