常用算法 - lru cache

# lru cache

LRU (最近最少使用) (opens new window) 是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

leetcode: https://leetcode.cn/problems/lru-cache/ (opens new window)

# java 实现


import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author FengJianxin
 * @since 2022/3/7
 */
public class LruCache extends LinkedHashMap<String, Object> implements Cache {

    private final int capacity;

    public LruCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    @Override
    public void set(String key, Object value) {
        super.put(key, value);
    }

    @Override
    public Object get(String key) {
        return getOrDefault(key, null);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Object> eldest) {
        return super.size() > capacity;
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

LinkedHashMap 每次调用 get 方法都会将数据移动到链表末尾。每次添加元素时，如果 removeEldestEntry 方法返回 true，则会删除第一个链表元素

#lru cache