基于 LinkedHashMap 的 LRU 算法实现

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private final ReadWriteLock rwLock = new ReentrantReadWriteLock();
    private final Lock rLock = rwLock.readLock();
    private final Lock wLock = rwLock.writeLock();
    public LRULinkedHashMap(int maxCapacity) {
        super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
        this.maxCapacity = maxCapacity;
    }
    /** LRU 核心 */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        rLock.lock();
        try {
            return size() > maxCapacity;
        } finally {
            rLock.unlock();
        }
    }
    @Override
    public boolean containsKey(Object key) {
        rLock.lock();
        try {
            return super.containsKey(key);
        } finally {
            rLock.unlock();
        }
    }
    @Override
    public V get(Object key) {
        rLock.lock();
        try {
            return super.get(key);
        } finally {
            rLock.unlock();
        }
    }
    @Override
    public V put(K key, V value) {
        wLock.lock();
        try {
            return super.put(key, value);
        } finally {
            wLock.unlock();
        }
    }
    @Override
    public int size() {
        rLock.lock();
        try {
            return super.size();
        } finally {
            rLock.unlock();
        }
    }
    @Override
    public void clear() {
        rLock.lock();
        try {
            super.clear();
        } finally {
            rLock.unlock();
        }
    }
    public ArrayList<Map.Entry<K, V>> getAll() {
        rLock.lock();
        try {
            return new ArrayList<>(super.entrySet());
        } finally {
            rLock.unlock();
        }
    }
}

class LruCache<T> implements Serializable {
    private static final long serialVersionUID = 1L;
    // Although the internal implementation uses a Map, this cache
    // implementation is only concerned with the keys.
    private final Map<T,T> cache;
    public LruCache(final int cacheSize) {
        cache = new LinkedHashMap<T,T>() {
            private static final long serialVersionUID = 1L;
            @Override
            protected boolean removeEldestEntry(Map.Entry<T,T> eldest) {
                if (size() > cacheSize) {
                    return true;
                }
                return false;
            }
        };
    }
    public void add(T key) {
        synchronized (cache) {
            cache.put(key, null);
        }
    }
    public boolean contains(T key) {
        synchronized (cache) {
            return cache.containsKey(key);
        }
    }
}

基于双向链表的 LRU 算法实现

public class LRUCache<K, V> {
    class CacheNode {
        K key;
        V value;
        CacheNode prev;
        CacheNode next;
    }
    private final int maxCapacity;
    private final Hashtable<K, CacheNode> nodes;
    private int curSize;
    private CacheNode head;
    private CacheNode tail;
    public LRUCache(int maxCapacity) {
        this.maxCapacity = maxCapacity;
        nodes = new Hashtable<>(maxCapacity);
    }
    /**
     * 新增缓存
     *
     * @param k 缓存key
     * @param v 缓存value
     */
    public void put(K k, V v) {
        CacheNode node = nodes.get(k);
        if (Objects.isNull(node)) {
            if (curSize >= maxCapacity) {
                if (Objects.nonNull(tail)) {
                    nodes.remove(tail.key);
                }
                removeLast();
            }
            node = new CacheNode();
        }
        node.key = k;
        node.value = v;
        move2Head(node);
        curSize++;
    }
    /**
     * 获取缓存
     */
    public V get(K k) {
        if (Objects.isNull(k)) {
            return null;
        }
        final CacheNode node = nodes.get(k);
        if (Objects.isNull(node)) {
            return null;
        }
        move2Head(node);
        return node.value;
    }
    /**
     * 将缓存删除
     *
     * @param key 缓存节点 key
     */
    public V remove(K key) {
        if (key == null) {
            return null;
        }
        final CacheNode node = nodes.get(key);
        if (node != null) {
            if (node.prev != null) {
                node.prev.next = node.next;
            }
            if (node.next != null) {
                node.next.prev = node.prev;
            }
            if (head == node) {
                head = node.next;
            }
            if (tail == node) {
                tail = node.prev;
            }
        }
        curSize--;
        return node == null ? null : node.value;
    }
    /**
     * 清空容器
     */
    public void clear() {
        nodes.clear();
        curSize = 0;
        head = null;
        tail = null;
    }
    /**
     * 移动到链表头, 表示该节点最新使用过
     *
     * @param node 节点
     */
    private void move2Head(CacheNode node) {
        if (node == null || node == head) {
            return;
        }
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        if (head != null) {
            node.next = head;
            head.prev = node;
        }
        head = node;
        node.prev = null;
        if (tail == null) {
            tail = head;
        }
    }
    /**
     * 删除链表最后一个节点, 表示最近最少使用的缓存
     */
    private void removeLast() {
        if (tail != null) {
            if (tail.prev != null) {
                tail.prev.next = null;
            } else {
                head = null;
            }
            tail = tail.prev;
        }
    }
}

参考：

• 简书 ▪ LRU算法实现
• ITEYE ▪ 缓存淘汰算法：LRU算法