模拟缓存淘汰算法LRU（Java实现）

Bertha 。 2021-12-19 04:45 465阅读 0赞

也是一个面试题，题目是这样的：

> 假设有这样的缓存，如果get到数据返回成功，如果没有get到数据，那么返回失败，不管能否get到数据，总是会把  
> 最新的记录加入缓存，同时缓存有个大小限制，可以无限添加，但是都会把前面的数据挤掉。如果给出缓存大小，
> 
> 并给出一个查询的列表，用程序模拟这个过程，并求出缓存命中失败的次数。
> 
> 比如，输入：int size=4,int\[\] data=\{1,2,3,4,3,5,3,2,1,5,4\}  
> 输出：8

根据题目中给定的数组，缓存是否命中过程如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

其实说这个算法是LRU不太准确，网上也有类似的缓存命中的题，这道题的大概是说会有一个缓存，刚开始什么也没有，当慢慢存储的时候，数据会达到给定的size，当缓存空间不足的时候，需要将缓存空间做一个清理，也就是所谓的淘汰一部分数据，这部分数据，从题目意思来看，就是最早加入到缓存中的数据，这里根据题意，我给出了这样的解法，我们构造一个队列，默认遵循FIFO（先进先出）的队列，每次存入队列之前，需要判断是否需要删除队头的元素。最后还需要一个辅助的查找方法，遍历队列，查找指定的元素。最后再给出一个方法：通过输入数组参数计算缓存命中失败次数。

这个题目的代码如下所示：

package com.xxx.algorithm;
    import java.util.Iterator;
    import java.util.Queue;
    import java.util.concurrent.ArrayBlockingQueue;
    public class CacheDemo {
    	private static Queue<Integer> queue = new ArrayBlockingQueue<Integer>(4);
    	
    	public static boolean find(int value){
    		System.out.println(queue);
    		Iterator<Integer> it = queue.iterator();
    		while(it.hasNext()){
    			int val = it.next();
    			if(value==val)
    				return true;
    		}
    		return false;
    	}
    	
    	public static int get(int value){
    		boolean exist = find(value);
    		if(queue.size()==4){
    			queue.poll();
    		}
    		queue.add(value);
    		return exist?1:0;
    	}
    	
    	public static int failCount(int[] data){
    		int count = 0;
    		for(int i=0;i<data.length;i++){
    			if(get(data[i])==0){
    				count++;
    			}
    		}
    		return count;
    	}
    	
    	public static void main(String[] args) {
    		int[] data = {1,2,3,4,3,5,3,2,1,5,4};
    		int count = failCount(data);
    		System.out.println("failCount->"+count);
    	}
    }

运行打印结果：

[]
    [1]
    [1, 2]
    [1, 2, 3]
    [1, 2, 3, 4]
    [2, 3, 4, 3]
    [3, 4, 3, 5]
    [4, 3, 5, 3]
    [3, 5, 3, 2]
    [5, 3, 2, 1]
    [3, 2, 1, 5]
    failCount->8

这个简单的算法，能够满足题目要求。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: /images/20211218/446e1308d49e40ee8d04e7ac258a866b.png