LRU---缓存淘汰策略

古城微笑少年丶 2022-04-11 02:39 305阅读 0赞

## LRU(Least recently used，最近最少使用)最近最久未使用算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。 ##

**基本介绍：淘汰近期没有使用的数据，维持动态数据平衡。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIzMDA2Mw_size_16_color_FFFFFF_t_70]

**步骤分析：**  
![在这里插入图片描述][20181204113215509.png]

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

**代码实现：**  
Java使用LinkedHashMap实现LRU：

package lru;
    
    import java.util.LinkedHashMap;
    import java.util.Map;
    import java.util.Set;
    
    /**
     * @author luanaynxu
     *
     *         2018年12月2日
     */
    public class Lru<K, V> {
    	private final int MAX_CACHE_SIZE; //初始化最大值
    	private final float DEFAULT_LOAD_FACTORY = 0.75f;//Map扩容因子
    
    	LinkedHashMap<K, V> map;
    
    	public Lru(int cacheSize) {
    		MAX_CACHE_SIZE = cacheSize;
    		int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
    		/*
    		 * 第三个参数设置为true，代表linkedlist按访问顺序排序，可作为LRU缓存 第三个参数设置为false，代表按插入顺序排序，可作为FIFO缓存
    		 */
    		map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, true) {
    			/**
    			 * 
    			 */
    			private static final long serialVersionUID = 1L;
    
    			@Override
    			protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    				return size() > MAX_CACHE_SIZE;
    			}
    		};
    	}
    
    	public synchronized void put(K key, V value) {
    		map.put(key, value);
    	}
    
    	public synchronized V get(K key) {
    		return map.get(key);
    	}
    
    	public synchronized void remove(K key) {
    		map.remove(key);
    	}
    
    	public synchronized Set<Map.Entry<K, V>> getAll() {
    		return map.entrySet();
    	}
    
    	@Override
    	public String toString() {
    		StringBuilder stringBuilder = new StringBuilder();
    		for (Map.Entry<K, V> entry : map.entrySet()) {
    			stringBuilder.append(String.format("%s: %s  ", entry.getKey(), entry.getValue()));
    		}
    		return stringBuilder.toString();
    	}
    
    	public static void main(String[] args) {
    		Lru<Integer, Integer> lru1 = new Lru<>(5);
    		lru1.put(1, 1);
    		lru1.put(2, 2);
    		lru1.put(3, 3);
    		System.out.println(lru1);
    		lru1.get(1);// 访问1
    		System.out.println(lru1);
    		lru1.put(4, 4);
    		lru1.put(5, 5);
    		lru1.put(6, 6);// 2由于最近没有使用 被淘汰
    		System.out.println(lru1);
    
    	}
    }

运行结果：

1: 1  2: 2  3: 3  
    2: 2  3: 3  1: 1  
    3: 3  1: 1  4: 4  5: 5  6: 6

**相关分析：**  
【命中率】  
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命 中率急剧下降，缓存污染情况比较严重。  
【复杂度】  
实现简单。  
【代价】  
命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIzMDA2Mw_size_16_color_FFFFFF_t_70]: /images/20220411/1253a51653c346799f548a0ec684f1dc.png
[20181204113215509.png]: /images/20220411/711b8c5895e442a6aab05a704ed217b9.png