6

我对如何使用 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]

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]

只是想澄清一下。

4

1 回答 1

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

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

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

    话虽如此，LinkedHashMap也支持access-order；

    提供了一个特殊constructor的方法来创建链接哈希映射，其迭代顺序是其条目最后一次访问的顺序，从最近最少访问到最近访问（访问顺序）。这种映射非常适合构建 LRU 缓存。调用putorget方法会导致访问相应的条目（假设它在调用完成后存在）。

    因此，如果您使用的是插入顺序，则顺序不会从get("b");更改。如果您使用的是访问顺序（通常是 LRU 缓存；-） ，那么顺序将会改变。

还有其他问题吗？:-)

于 2012-08-19T21:49:37.490 回答