LRU 算法的两种实现方式

import java.util.HashMap;
import java.util.LinkedList;

public class Main {

    static class LRUCache<K, V> {
        // 缓冲容量
        private final int cacheSize;
        // 双向链表，存储缓存
        private LinkedList<K> cacheList = new LinkedList<>();
        // 储存缓存的key，用来计算是否命中，命中率则遍历链表
        private HashMap<K, V> map = new HashMap<>();

        public LRUCache(int cacheSize) {
            this.cacheSize = cacheSize;
        }

        public synchronized void put(K key, V val) {
            // 未命中
            if (!map.containsKey(key)) {
                // 如果超过了缓存，将最少访问的移除
                if (map.size() >= cacheSize) {
                    map.remove(cacheList.removeLast());
                }
                cacheList.addFirst(key);
                map.put(key, val);
            } else {
                // 命中，将链表元素往前移动，更新map
                moveToFirst(key);
                map.put(key, val);
            }
        }

        public V get(K key) {
            // 是否命中
            if (!map.containsKey(key)) {
                return null;
            }
            // 移动到前面来
            moveToFirst(key);
            return map.get(key);
        }

        // 移动到双链表前面
        private synchronized void moveToFirst(K key) {
            cacheList.remove(key);
            cacheList.addFirst(key);
        }

        @Override
        public String toString() {
            return cacheList.toString();
        }
    }

    public static void main(String[] args) {
        LRUCache<String, String> lruCache = new LRUCache<String, String>(4);
        lruCache.put("C", null);
        lruCache.put("A", null);
        lruCache.put("D", null);
        lruCache.put("B", null);
        lruCache.put("E", null);
        lruCache.put("B", null);
        lruCache.put("A", null);
        lruCache.put("B", null);
        lruCache.put("C", null);
        lruCache.put("D", null);
        System.out.println(lruCache);
    }
}
/**
[D, C, B, A]
**/

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int val) {
        super.put(key, val);
    }

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