Lru缓存算法的简易设计及实现_设计lru缓存

---

前言

LRU算法又称最近最少使用算法，它的基本思想是长期不被使用的数据，在未来被用到的几率也不大，所以当新的数据进来时我们可以优先把这些数据替换掉。

---

一、LinkedHashMap中key的顺序

LinkedHashMap是一个特殊的Map对象,底层会基于双向列表记录Map中的key的添加顺序或访问顺序:

1.当使用无参构造器构建LinkedHashMap对象时,存储对象默认会记录key的添加顺序,如下示例,输出结果为:{F=100,A=200,M=300}

 public static void main(String[] args) {
        LinkedHashMap<Object,Object> map=new LinkedHashMap<>();
        map.put("F", 100);
        map.put("A", 200);
        map.put("M", 300);
        map.get("A");
        System.out.println(map);
 
    }

2.通过带参构造方法构建LinkedHashMap对象时,会记录key的访问顺序,如下示例,输出结果为:

{F=100,A=200,M=300,P=400}

 public static void main(String[] args) {
        LinkedHashMap<Object,Object> map=new LinkedHashMap<>(3,0.75f,true);
        map.put("F", 100);
        map.put("A", 200);
        map.put("M", 300);
        map.get("A");
        map.put("P",400);
        System.out.println(map);
 
    }

3.LinkedHashMap类有一个removeEldestEntry()方法:在每次执行put方法时都会调用此方法,用于判断容器是否已经满了,该方法的返回值为布尔型,如果返回值为true,此时会先移除(最近访问最少:最早添加的且后期没有访问)再放入,默认的返回值为false

创建LinkedHashMap匿名内部类对象,再重写removeEldestEntry()方法,即可实现当容器满了,移除元素后添加,示例如下,输出结果为:

{F=100,A=200,E=400}

有了这个结果,我们就可以基于LinkedHashMap设计一个简单的Lru缓存

 public static void main(String[] args) {
        LinkedHashMap<Object,Object> map=
                new LinkedHashMap(3,0.75f,true){
                    //每次执行put方法都会调用此方法，用于判断容器是否已经满了
                    //方法返回true表示已满，此时会先移除(最近访问最少)再放入。
                    @Override
                    protected boolean removeEldestEntry(Map.Entry eldest) {
                        return size()>3;//默认值是false(表示不移除，即便是满了)
                    }
                };
        map.put("F", 100);
        map.put("A", 200);
        map.put("M", 300);
        map.get("F");
        map.get("A");
        map.put("E", 400);
        System.out.println(map);
 
    }

图示:

---

二、设计Lru

1.准备Cache标准接口

该接口起到规范定义的作用,代码如下：

public interface Cache {
    
    void putObject(Object key,Object value);
 
    Object getObject(Object key);
 
    Object removeObject(Object key);
 
    void clear();
 
    int size();
}

2.准备接口实现类

用于简易Cache实现:

/**
 * 简易Cache实现
 * 1)存储结构：散列表(基于JAVA中的hashmap存储)
 * 2)淘汰算法：没有(直到到内存溢出)
 * 3)线程安全：否
 * 4)缓存对对象的引用？强引用
 * 5)对象获取：浅拷贝(获取对象地址)
 */
public class PerpetualCache implements Cache{
 
    private HashMap<Object,Object> cache=new HashMap<>();
    @Override
    public void putObject(Object key, Object value) {
        cache.put(key, value);
    }
 
    @Override
    public Object getObject(Object key) {
        return cache.get(key);
    }
 
    @Override
    public Object removeObject(Object key) {
        return cache.remove(key);
    }
 
    @Override
    public void clear() {
        cache.clear();
    }
 
    @Override
    public int size() {
        return cache.size();
    }
 
    @Override
    public String toString() {
        return "PerpetualCache{" +
                "cache=" + cache.toString() +
                '}';
    }
}

3.设计Lru

给定四个属性:

Cache cache,用于存储数据

int maxCap,设定最容量

LinkedHashMap<Object,Object> keyAccessOrders,用于记录key的访问顺序

Object eldEstKey,用于记录访问次数最少的key

a.当我们向cache中添加元素同时,往keyAccessOrders添加元素,keyAccessOrders的value可以按喜好添加,key必须保持与cache一致,因为key是保证顺序的关键

b.同理,当我们在访问,移除或清空cache时,keyAccessOrders需要同步操作

c.当容器满了,eldEstKey有值,且为访问次数最少的key,所以通过判断eldEstKey是否有值即可判断容器是否已满,如果满了,根据eldEstKey值移除访问次数最少的cache(keyAccessOrders会自动移除),同时将eldEstKey重新赋值为null

Override
            protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
                boolean isFull= size()>maxCap;
                if(isFull)eldEstKey=eldest.getKey();//获取最近访问次数最少的key
                return isFull;
            }
        };
    }
 
    @Override
    public void putObject(Object key, Object value) {
        //1.向Cache中添加新的元素
        cache.putObject(key, value);
        //2.记录key的访问顺序
        keyAccessOrders.put(key, key);
        //3.Cache满了则移除最近访问次数最少的key/value
        if(eldEstKey!=null){
            cache.removeObject(eldEstKey);
            eldEstKey=null;
        }
    }
 
    @Override
    public Object getObject(Object key) {
        //1.记录key的访问顺序
        keyAccessOrders.get(key);
        //2.返回cache中的指定key对应的value
        return cache.getObject(key);
    }
 
    @Override
    public Object removeObject(Object key) {
        Object object = cache.removeObject(key);
        keyAccessOrders.remove(key);
        return object;
    }
 
    @Override
    public void clear() {
           cache.clear();
           keyAccessOrders.clear();
    }
 
    @Override
    public int size() {
        return cache.size();
    }
 
    @Override
    public String toString() {
        return "LruCache{" +
                "cache=" + cache.toString() +
                '}';
    }

如下测试,输出结果为:LruCache{cache=PerpetualCache{cache={A=100, D=400, E=500}}}

public static void main(String[] args) {
        Cache cache=new LruCache(//负责添加算法
                new PerpetualCache(),//负责存数据
                3);
        cache.putObject("A", 100);
        cache.putObject("B", 200);
        cache.putObject("C", 300);
        cache.getObject("A");
        cache.putObject("D", 400);
        cache.putObject("E", 500);
        System.out.println(cache);
    }
 
}

---

三、使用

以实际业务为例:

客户端第一次向服务器发送请求时,控制台输出Get Data from Database,因为通过key查询缓存,查询不到对应的数据,所以向数据库请求数据,并将数据存入缓存中

当客户端再次向服务器发送请求时,只要缓存数据没有移除,则控制台不输出任何内容,因为服务器直接向缓存中拿数据了

private Cache cache=new LruCache(new PerpetualCache(),3);
@GetMapping("/list")
public List<User> list(){
    Object obj = cache.getObject("userListKey");
    if(obj != null){
        return (List<User>)obj;//向下造型
    }
    System.out.println("Get Data from Database");
    List<User> list = mapper.list();
    cache.putObject("userListKey",list);
    return list;
}

---

总结

如果只是设计Lru算法,简单实现,其设计方法还可以更简单,只要围绕HashLinkedMap类的key的顺序思考即可,如上设计方式比较灵活,也方便之后做增强装饰.