使用 get 时 LRUCache 条目重新排序

Question

我查看了 LRUCache 的官方 Android 文档，其中说：每次访问一个值时，它都会被移到队列的头部。当一个值被添加到一个完整的缓存中时，该队列末尾的值被逐出并且可能有资格进行垃圾收集。我想这是由缓存使用的 linkedhashmap 维护的双向链表。为了检查这种行为，我检查了 LruCache 的源代码，并检查了 get(K key) 方法。它进一步调用 map 的 get 方法，该方法从底层 hashmap 获取值并调用 recordAccess 方法。

public V get(Object key) {
    LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);
    return e.value;
}

recordAccess 方法依次将访问的条目移动到列表的末尾，以防 accessOrder 设置为 true（对于我的问题，让我们假设它是），否则它什么都不做。

/**
     * This method is invoked by the superclass whenever the value
     * of a pre-existing entry is read by Map.get or modified by Map.set.
     * If the enclosing Map is access-ordered, it moves the entry
     * to the end of the list; otherwise, it does nothing.
     */
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }

这听起来与上面所说的元素被移动到队列头部的说法矛盾。相反，它被移动到列表的最后一个元素（使用 head.before）。当然，我在这里遗漏了一些东西，有什么帮助吗？

Answer 1

来自 LinkedHashMap 的 javadoc:

If the three argument constructor is used, and accessOrder is specified as true, the iteration will be in the order that entries were accessed. The access order is affected by put, get, and putAll operations, but not by operations on the collection views.

Exactly the case，即LruCache有。

public LruCache(int maxSize) {
    if (maxSize <= 0) {
        throw new IllegalArgumentException("maxSize <= 0");
    }
    this.maxSize = maxSize;
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}

让我们看看 recordAccess() 做了什么：

    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) { // true, because `LruCache` instantiated this 
                              // map with `accessOrder = true`
            lm.modCount++;
            remove(); // remove this `LinkedHashMapEntry` from the map
            addBefore(lm.header); // adds this entry before the current header of
                                  // the map, thus this entry becomes the header
        }
    }

Instead it's moved to the last element of the list (using head.before).

我看不出，你的说法是如何有效的。

Answer 2

您没有遗漏任何内容，只是您正在阅读 LinkedHashMap 的 LruCache 文档。 LinkedHashMap 有自己的文档，特别是关于它的 accessOrder. (Same on Java docs).

[...when accessOrder=true...] order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order)

因此LinkedHashMap将最近使用的条目放在最后，并记录在案。

实际上 LruCache 描述了这种缓存在理论上是如何工作的，但是 LinkedHashMap 展示了如何在不添加单独的向后移动迭代器的情况下实现它：通过将最近的元素放在最后，trimming 可以使用已经可用的（向前移动的）迭代器来有效地访问（和删除）旧元素。

尽管此时此地我无法判断 removeEldestEntry 出了什么问题。也许过去不存在。

使用 get 时 LRUCache 条目重新排序

LRUCache entry reordering when using get

java

android

linkedhashmap

android-lru-cache