排序键数据结构用于LRU和MRU缓存驱逐策略

Question

排序键数据结构用于LRU和MRU缓存驱逐策略

javacachingdata-structureslrumru

3

我正在设计一种简单的数据结构，用于实现缓存淘汰策略。我想要实现的两种可能情况是LRU和MRU。

我正在寻找一种类似于映射的数据结构，其中键可能是时间（或者只是自增的整数），以便知道哪个缓存块最近使用或最近未使用。值是块的ID。

是否存在一种数据结构，在插入时按键对数据进行排序，并在O(1)时间内检索特定键的值？

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

谢谢

- Saher Ahwal

2

如果并发性很重要，ConcurrentSkipListMap可能非常有用，或者使用Guava Cache或MapMaker的配置。 - Perception

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- n1ckolas · Accepted Answer

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

从它们的 javadoc 中可以看到：

一个{@link Map}接口，为其键提供了总排序。地图按其键的{@linkplain Comparable自然顺序}或通常在有序映射创建时提供的{@link Comparator}排序。当遍历排序映射的集合视图(由entrySet、keySet和values方法返回)时，这个顺序会反映出来。提供了几个额外的操作以利用排序。

即使从 SortedMap 中返回的条目和键按升序排列，它也有一些可能有用的方法，如 firstKey() 和 lastKey()。

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