java - LRU 和 MRU 缓存驱逐策略的排序键数据结构

Question

我正在研究一个简单的数据结构，它将实现缓存驱逐策略。我想实现的两种可能的场景是LRU 和 MRU

我正在寻找一种类似地图的数据结构，其中键可能是时间（或者可能只是自动递增的整数），以了解最近使用或最近使用最少的缓存块。值是块的 ID。

是否存在现有的数据结构，可以通过插入键对数据进行排序，并在 O(1) 时间内检索某个键的值？

例如，Java 的 HashMap 具有恒定时间查找，但我需要获取所有键，对它们进行排序并根据我正在实现的算法选择最后一个或第一个。SortedMap是我应该去的吗？您是否建议任何其他适用于 LRU 和 MRU 实现的数据结构？

谢谢

Answer 1

你是对的，SortedMap根据插入的键对条目进行排序。最著名的实现SortedMap是TreeMap，它将条目存储为平衡二叉树。

从他们的javadoc：

一个 {@link Map} 进一步提供了对其键的总排序。该映射根据其键的 {@linkplain Comparable natural ordering} 或通常在排序映射创建时提供的 {@link Comparator} 进行排序。此顺序在遍历已排序地图的集合视图（由 entrySet、keySet 和 values 方法返回）时反映出来。提供了几个额外的操作来利用排序。

尽管条目和键是从 以升序返回的SortedMap，但它也有方法firstKey()和lastKey()，这也可能会有所帮助。

特别是对于 LRU：Java 中最常见的方法是使用LinkedHashMap，它有方法removeEldestEntry(Map.Entry)。默认情况下它什么都不做，但您可以轻松地扩展类并实现该方法。您可以在此处找到更多信息。