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

Question

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

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

所以对于地图，我使用 HashMap。我现在面临的问题是，我希望 HashMap 中的一个项目将指向 到 DLL 中的相应项目，但我无权访问内部节点LinkedList.

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

Answer 1

我会尽量劝阻您重新发明一个具有大量现有优秀实现的轮子。例如。 Google番石榴的caches are great. They provide several ways to evict cached elements. Also, Caffeine (written by a developer who worked on Guava's cache), and EhCache历史悠久

如果出于某种原因您必须自己动手，请查看此 question and the answers。

Answer 2

可以使用JavaLinkedHashMap并覆盖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); }
    }
}

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

Implementing an LRU cache with built in data structures

java

lru

data-structures