java - 使用内置数据结构实现 LRU 缓存

Question

这个问题已经有答案了:

How would you implement an LRU cache in Java? (21 个回答)

已关闭 5 年前。

我想仅使用 Java 内置的数据结构在 Java 中实现一个简单的 LRU 缓存。

这个想法是使用 Map 和双向链表 (DLL)。

因此，对于 map ，我使用 HashMap 。我现在面临的问题是，我希望 HashMap 中的某个项目将指向 DLL 中的相应项目，但我无权访问 LinkedList 的内部节点。

如果不创建我自己的新数据结构，什么是合理的解决方案？

Answer 1

您可以使用Java LinkedHashMap并重写removeEldestEntry来实现LRU缓存

public class SimpleLru<K, V> extends LinkedHashMap<K, V>{

    final int cacheSize;

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

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return this.size() > this.cacheSize;
    }

    public static void main(String[] args) {
        SimpleLru<String, Integer> m = new SimpleLru<>(2); // Max 2
        m.put("k1", 1); // k1:1
        m.put("k2", 2); // k1:1, k2:2
        m.put("k3", 3); // k2:2, k3:3
    }
}

如果你想要一个线程安全的版本，你可以使用:

public class ConcurrentLru<K, V> {

    final Object mutex = new Object();
    final Map<K, V> cache;

    public ConcurrentLru(final int cacheSize) {
        this.cache = new LinkedHashMap<K, V>() {

            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return this.size() > cacheSize;
            }
        };
    }

    public void put(K k, V v) {
        synchronized (this.mutex) { this.cache.put(k, v); }
    }

    public boolean contains(K k) {
        synchronized (this.mutex) { return this.cache.containsKey(k); }
    }

    public V remove(K k) {
        synchronized (this.mutex) { return this.cache.remove(k); }
    }

    public V get(K k) {
        synchronized (this.mutex) { return this.cache.get(k); }
    }
}