java - 支持基于最近访问项的高效踢出策略的数据结构

Question

我需要一个数据结构来支持对最久以前请求的项目的最有效的踢出政策。例如，我有一堆不时被要求的元素。当我用完内存时，我想踢出我的数据结构( HashMap )中最旧的项目。

我在想像Queue这样的FIFO ds smth，但我不确定如何处理这种情况:

--> a b c d a -->

a 是最旧和最新的项目。如果再次添加“a”，我需要搜索整个队列以将其删除。这是非常低效的，但我想不出任何有效的方法。也许是某种树结构，将访问最少的树保持在顶部？

是否已经在 J​​ava 中实现了这种数据结构？

Answer 1

LinkedHashMap 是您所追求的结构。来自 the docs :

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.

所以你应该只使用 appropriate constructor :

Map<K, V> map = new LinkedHashMap<>(CAPACITY, LOAD_FACTOR, true);

boolean 参数确定映射是访问顺序 还是插入顺序。 true 表示访问顺序。

此外，如果您希望 map 作为 LRU 缓存工作，您可以创建自己的类来扩展 LinkedHashMap 并覆盖 removeEldestEntry方法。同样，来自文档:

The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

这意味着您可以为缓存创建自己的类:

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

    private static final int MAX_ENTRIES = 100;

    public Cache() {
        super(SOME_INITIAL_CAPACITY, SOME_LOAD_FACTOR, true);
    }

    protected boolean removeEldestEntry(Entry<K, V> entry) {
        return size() > MAX_ENTRIES;
    }
}

用法:

Map<K, V> map = new Cache<>();