LRU Cache的LinkedHashMap结构

Question

我对如何使用LinkedHashMap构建LRU缓存感到有点困惑(如何在Java 6中实现LRU缓存？),我想确保我理解它在幕后的内部工作原理.

假设我定义了一个类LRUMap,它扩展了LinkedHashMap并覆盖了removeEldestEntry(final Map.Entry<A, B> eldest)它的方式.

然后我构建数据结构并在地图中插入4个项目

    LRUMap<String,String> map = new LRUMap<String,String>(3); //capacity 3
    map.put("a", "a");
    map.put("b", "b");
    map.put("c", "c");
    map.put("d", "d");

并且通常LinkedHashMap使用被Entry object调用header的起始节点来链接您添加到地图中的所有项目.所以在这种情况下它会

   [header] ->  ["a"] -> ["b"] -> ["c"] -> ["d"] -> [header]

头文件Entry对象既是header.before = header.after = header,也是最初构造时双向链表的开头和结尾.

并且假设地图达到了我想要的最大条目(3项),并且来自

    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
         removeEntryForKey(eldest.key);
    }
    .....

那么这是否意味着它首先会删除["a"]？
当我们调用get(Object key)它时,重新排列列表顺序,它将该键放在标题节点之前(比如说"b"),所以它变成了

     [header] ->  ["c"] -> ["d"] -> ["b"] -> [header]

只是想澄清一下.

Answer 1

1. 是; 该条目<"a", "a">将首先删除:-)

2. 也许; LinkedHashMap默认情况下,使用insert-order,而不是access-order ......直接来自规范:

   接口的哈希表和链表实现Map,具有可预测的迭代顺序.这种实现的不同之处HashMap在于它维护了一个贯穿其所有条目的双向链表.此链接列表定义迭代排序,通常是键插入映射的顺序(插入顺序).

   话虽如此,LinkedHashMap也支持访问顺序 ;

   constructor提供了一个特殊的用于创建链接的哈希映射,其迭代顺序是其条目上次访问的顺序,从最近访问到最近访问(访问顺序).这种地图非常适合构建LRU缓存.调用putor get方法会导致访问相应的条目(假设它在调用完成后存在).

   因此,如果您使用的是插入订单,那么订单将不会改变get("b"); 如果你使用的访问顺序(通常的LRU缓存会 ;-)那么该命令会改变.

还有其他问题吗？:-)