我正在研究一个将实现缓存逐出策略的简单数据结构。我想实现的两种可能情况是 LRU and MRU
我正在寻找一种类似 map 的数据结构，其中键可能是时间(或者可能只是自动递增的整数)，以了解最近使用或最近最少使用的缓存 block 。值是 block 的 ID。
是否存在一种数据结构，可以在插入时按键对数据进行排序，并在 O(1) 时间内检索某个键的值？
例如 Java 的 HashMap 具有恒定时间查找，但我需要获取所有键，对它们进行排序并根据我正在实现的算法选择最后一个或第一个。是SortedMap我应该去做什么？您是否建议任何其他适用于 LRU 和 MRU 实现的数据结构？
谢谢
最佳答案
你是对的，SortedMap 根据插入时的键对条目进行排序。 SortedMap 最著名的实现是 TreeMap，它将条目存储为平衡二叉树。
来自他们的 javadoc :
A {@link Map} that further provides a total ordering on its keys. The map is ordered according to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} typically provided at sorted map creation time. This order is reflected when iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods). Several additional operations are provided to take advantage of the ordering.
即使条目和键从 SortedMap 中按升序排序返回，它也有方法 firstKey() 和 lastKey()，这也可能有帮助。
特别是对于 LRU:Java 中最常见的方法是使用 LinkedHashMap，它有方法 removeEldestEntry(Map.Entry)。默认情况下它什么都不做，但您可以轻松地扩展类并实现该方法。您可以找到更多信息 here .
关于java - LRU 和 MRU 缓存逐出策略的排序键数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15240851/