Cache LRU et principes de mise en œuvre de Java et Android

1. Présentation

Android fournit la classe LRUCache, qui peut être facilement utilisée pour implémenter la mise en cache de l'algorithme LRU. Java fournit LinkedHashMap, qui peut être utilisé pour implémenter facilement l'algorithme LRU. Le LRULinkedHashMap de Java hérite directement de LinkedHashMap, et l'algorithme LRU peut être implémenté avec très peu de modifications.

2. L'algorithme LRU de Java

La base de l'algorithme LRU de Java est LinkedHashMap hérite de HashMap et apporte certaines modifications basées sur HashMap pour implémenter l'algorithme LRU.

1. HashMap

La première chose à noter est que HashMap stocke les informations de chaque nœud dans la structure Entryb77a8d9c3c319e50d4b02a976b347910 Entryb77a8d9c3c319e50d4b02a976b347910 stocke les informations de clé, de valeur et de hachage correspondant au nœud, ainsi que la référence au nœud suivant du nœud actuel. Par conséquent, Entryb77a8d9c3c319e50d4b02a976b347910 est une liste chaînée unidirectionnelle. La structure de stockage de HashMap se présente sous la forme d'un tableau plus une liste chaînée unidirectionnelle. Le hashCode correspondant à chaque clé peut être trouvé à une position dans le tableau HashMap ; et si plusieurs clés correspondent au même hashCode, alors elles correspondent à la même position dans le tableau. À ce moment, le HashMap stockera les informations correspondantes. Placez-le dans Entryb77a8d9c3c319e50d4b02a976b347910 et utilisez une liste chaînée pour connecter ces Entryb77a8d9c3c319e50d4b02a976b347910.

 static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        public final K getKey() {
            return key;
        }
        public final V getValue() {
            return value;
        }
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }
        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }
        public final String toString() {
            return getKey() + "=" + getValue();
        }
        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that&#39;s already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }
        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    }

Publiez le code de la méthode put de HashMap ci-dessous et analysez-le

　

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
　　　　　//以上信息不关心，下面是正常的插入逻辑。
　　　　　//首先计算hashCode
        int hash = hash(key);
　　　　　//通过计算得到的hashCode，计算出hashCode在数组中的位置
        int i = indexFor(hash, table.length);
　　　　　//for循环，找到在HashMap中是否存在一个节点，对应的key与传入的key完全一致。如果存在，说明用户想要替换该key对应的value值，因此直接替换value即可返回。
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
　　　　 //逻辑执行到此处，说明HashMap中不存在完全一致的kye.调用addEntry，新建一个节点保存key、value信息，并增加到HashMap中
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

Ajouté dans le code ci-dessus Quelques notes à donner une idée d'ensemble. Certains points dignes d’analyse sont expliqués en détail ci-dessous.

<1> int i = indexFor(hash, table.length);

Vous pouvez jeter un œil au code source :

　

static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

Pourquoi le hashCode (h) obtenu doit-il être comparé à (longueur-1) l'opération ET au niveau du bit ? Cela permet de garantir que les informations d'ordre supérieur de h sont supprimées. Si la taille du tableau est de 8 (1 000) et la valeur calculée de h est de 10 (1 010), si vous obtenez directement les données avec un indice de tableau de 10, une exception hors limites du tableau sera définitivement levée. Par conséquent, en utilisant AND au niveau du bit (0111&1010), les informations d'ordre supérieur sont effacées avec succès et 2 (0010) est obtenu, qui représente les données d'index 2 dans le tableau correspondant. L'effet est le même que pour le reste, mais le fonctionnement au niveau du bit est nettement plus efficace.

Mais il y a un problème avec cela. Si la longueur est de 9, l'information de longueur-1 obtenue est de 8 (1000). Si l'opération sur les bits est effectuée de cette manière, non seulement les données de bits élevés ne le peuvent pas. être effacé, mais le résultat obtenu est définitivement faux. Il doit donc y avoir quelque chose de spécial dans la taille du tableau. En examinant le code source, vous constaterez que HashMap garantit que le nombre de tableaux correspondants est de 2 à la puissance n à tout moment.

Tout d'abord, appelez la méthode inflateTable lors de la mise. L'accent est mis sur la méthode roundUpToPowerOf2, bien que son contenu contienne un grand nombre d'opérations et de traitements liés aux bits, ce qui n'est pas très clair, mais les commentaires ont clairement indiqué qu'elle garantirait que le nombre de tableaux soit de 2 au nième. pouvoir.

private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}

Deuxièmement, dans d'autres emplacements tels que addEntry, (2 * table.length), table.length << le nombre de tableaux est de 2 à la puissance n.

<2> for (Entry<K,V> e = table[i]; e != null; e = e.next)

Étant donné que HashMap utilise la forme d'un tableau plus une liste chaînée, après avoir obtenu la position dans le tableau via hashCode, ce que vous obtenez n'est pas une entréeb77a8d9c3c319e50d4b02a976b347910, mais Il s'agit d'une liste chaînée d'Entréeb77a8d9c3c319e50d4b02a976b347910. La liste chaînée doit être bouclée pour obtenir la valeur correspondant à la clé.

<3> addEntry(hash, key, value, i);

Déterminez d'abord si le nombre de tableaux dépasse le seuil. Si tel est le cas, vous devez augmenter le nombre de tableaux. Ensuite, une nouvelle entrée sera créée et ajoutée au tableau.

/**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }
    /**
     * Like addEntry except that this version is used when creating entries
     * as part of Map construction or "pseudo-construction" (cloning,
     * deserialization).  This version needn't worry about resizing the table.
     *
     * Subclass overrides this to alter the behavior of HashMap(Map),
     * clone, and readObject.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

2. LinkedHashMap

LinkedHashMap est modifié en fonction de HashMap. Tout d’abord, modifiez l’entrée d’une liste chaînée unidirectionnelle en une liste doublement chaînée. Ajout de références à l'entrée de l'équipe avant et après.

  private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }
        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
        /**
         * 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);
            }
        }
        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

En même temps, LinkedHashMap fournit un en-tête de référence à Entry (en-tête Private Transient Entryb77a8d9c3c319e50d4b02a976b347910). La fonction de header est toujours uniquement la tête (header.after) et la queue (header.before) de tous les membres de HashMap. De cette façon, le format du tableau et de la liste chaînée du HashMap lui-même est modifié. Dans LinkedHashMap, le format de stockage des données du tableau de HashMap plus la liste chaînée est conservé, et un ensemble de listes doublement liées avec des en-têtes comme marqueurs de début (nous les appelons temporairement listes doublement liées d'en-tête) sont ajoutées. LinkedHashMap implémente l'algorithme LRU via la liste doublement chaînée de l'en-tête. header.after pointe toujours vers le nœud le moins fréquemment utilisé récemment. S'il est supprimé, le nœud correspondant à header.after sera supprimé. En revanche, header.before pointe vers le nœud qui vient d'être utilisé.

LinkedHashMap ne fournit pas de méthode put, mais LinkedHashMap réécrit les méthodes addEntry et createEntry, comme suit :

 /**
     * This override alters behavior of superclass put method. It causes newly
     * allocated entry to get inserted at the end of the linked list and
     * removes the eldest entry if appropriate.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);
        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }
    /**
     * This override differs from addEntry in that it doesn&#39;t resize the
     * table or remove the eldest entry.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

La méthode put de HashMap appelle la méthode addEntry ; La méthode addEntry de HashMap appelle la méthode createEntry. Par conséquent, les deux méthodes ci-dessus peuvent être combinées avec le contenu de HashMap pour faciliter l'analyse, formant la méthode suivante :

　

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

同样，先判断是否超出阈值，超出则增加数组的个数。然后创建Entry对象，并加入到HashMap对应的数组和链表中。与HashMap不同的是LinkedHashMap增加了e.addBefore(header);和removeEntryForKey(eldest.key);这样两个操作。

首先分析一下e.addBefore(header)。其中e是LinkedHashMap.Entry对象，addBefore代码如下，作用就是讲header与当前对象相关联，使当前对象增加到header的双向链表的尾部

（header.before）：
　　　　private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

其次是另一个重点，代码如下：

     

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

其中，removeEldestEntry判断是否需要删除最近最不常使用的那个节点。LinkedHashMap中的removeEldestEntry(eldest)方法永远返回false，如果我们要实现LRU算法，就需要重写这个方法，判断在什么情况下，删除最近最不常使用的节点。removeEntryForKey的作用就是将key对应的节点在HashMap的数组加链表结构中删除，源码如下：

　　

final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }

removeEntryForKey是HashMap的方法，对LinkedHashMap中header的双向链表无能为力，而LinkedHashMap又没有重写这个方法，那header的双向链表要如何处理呢。

仔细看一下代码，可以看到在成功删除了HashMap中的节点后，调用了e.recordRemoval(this);方法。这个方法在HashMap中为空，LinkedHashMap的Entry则实现了这个方法。其中remove()方法中的两行代码为双向链表中删除当前节点的标准代码，不解释。

       

/**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }void recordRemoval(HashMap<K,V> m) {
            remove();
        }

以上，LinkedHashMap增加节点的代码分析完毕，可以看到完美的将新增的节点放在了header双向链表的末尾。

但是，这样显然是先进先出的算法，而不是最近最不常使用算法。需要在get的时候，更新header双向链表，把刚刚get的节点放到header双向链表的末尾。我们来看看get的源码：

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

代码很短，第一行的getEntry调用的是HashMap的getEntry方法，不需要解释。真正处理header双向链表的代码是e.recordAccess(this)。看一下代码：

　　　　

 /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }
        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
        /**
         * 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);
            }
        }

首先在header双向链表中删除当前节点，再将当前节点添加到header双向链表的末尾。当然，在调用LinkedHashMap的时候，需要将accessOrder设置为true，否则就是FIFO算法。

三、Android的LRU算法

Android同样提供了HashMap和LinkedHashMap，而且总体思路有些类似，但是实现的细节明显不同。而且Android提供的LruCache虽然使用了LinkedHashMap，但是实现的思路并不一样。Java需要重写removeEldestEntry来判断是否删除节点；而Android需要重写LruCache的sizeOf，返回当前节点的大小，Android会根据这个大小判断是否超出了限制，进行调用trimToSize方法清除多余的节点。

Android的sizeOf方法默认返回1，默认的方式是判断HashMap中的数据个数是否超出了设置的阈值。也可以重写sizeOf方法，返回当前节点的大小。Android的safeSizeOf会调用sizeOf方法，其他判断阈值的方法会调用safeSizeOf方法，进行加减操作并判断阈值。进而判断是否需要清除节点。

Java的removeEldestEntry方法，也可以达到同样的效果。Java需要使用者自己提供整个判断的过程，两者思路还是有些区别的。

sizeOf，safeSizeOf不需要说明，而put和get方法，虽然和Java的实现方式不完全一样，但是思路是相同的，也不需要分析。在LruCache中put方法的最后，会调用trimToSize方法，这个方法用于清除超出的节点。它的代码如下：

　

　public void trimToSize(int maxSize)
  {
    while (true)
    {
      Object key;
      Object value;
      synchronized (this) {
        if ((this.size < 0) || ((this.map.isEmpty()) && (this.size != 0))) {
          throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!");
        }
　　　　　　if (size <= maxSize) {
　　　　　　　　break;
　　　　　　}
        Map.Entry toEvict = (Map.Entry)this.map.entrySet().iterator().next();
        key = toEvict.getKey();
        value = toEvict.getValue();
        this.map.remove(key);
        this.size -= safeSizeOf(key, value);
        this.evictionCount += 1;
      }
      entryRemoved(true, key, value, null);
    }
  }

重点需要说明的是Map.Entry toEvict = (Map.Entry)this.map.entrySet().iterator().next();这行代码。它前面的代码判断是否需要删除最近最不常使用的节点，后面的代码用于删除具体的节点。这行代码用于获取最近最不常使用的节点。

首先需要说明的问题是，Android的LinkedHashMap和Java的LinkedHashMap在思路上一样，也是使用header保存双向链表。在put和get的时候，会更新对应的节点，保存header.after指向最久没有使用的节点；header.before用于指向刚刚使用过的节点。所以Map.Entry toEvict = (Map.Entry)this.map.entrySet().iterator().next();这行最终肯定是获取header.after节点。下面逐步分析代码，就可以看到是如何实现的了。

首先，map.entrySet()，HashMap定义了这个方法，LinkedHashMap没有重写这个方法。因此调用的是HashMap对应的方法：

　　

public Set<Entry<K, V>> entrySet() {
        Set<Entry<K, V>> es = entrySet;
        return (es != null) ? es : (entrySet = new EntrySet());
    }

上面代码不需要细说，new一个EntrySet类的实例。而EntrySet也是在HashMap中定义，LinkedHashMap中没有。

　　

private final class EntrySet extends AbstractSet<Entry<K, V>> {
        public Iterator<Entry<K, V>> iterator() {
            return newEntryIterator();
        }
        public boolean contains(Object o) {
            if (!(o instanceof Entry))
                return false;
            Entry<?, ?> e = (Entry<?, ?>) o;
            return containsMapping(e.getKey(), e.getValue());
        }
        public boolean remove(Object o) {
            if (!(o instanceof Entry))
                return false;
            Entry<?, ?> e = (Entry<?, ?>)o;
            return removeMapping(e.getKey(), e.getValue());
        }
        public int size() {
            return size;
        }
        public boolean isEmpty() {
            return size == 0;
        }
        public void clear() {
            HashMap.this.clear();
        }
    }

　　Iterator9b2a63934c68105d154136c231fa3653> newEntryIterator() { return new EntryIterator(); }
代码中很明显的可以看出，Map.Entry toEvict = (Map.Entry)this.map.entrySet().iterator().next()，就是要调用newEntryIterator().next()，就是调用(new EntryIterator()).next()。而EntryIterator类在LinkedHashMap中是有定义的。

　　

private final class EntryIterator
            extends LinkedHashIterator<Map.Entry<K, V>> {
        public final Map.Entry<K, V> next() { return nextEntry(); }
    }
    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        LinkedEntry<K, V> next = header.nxt;
        LinkedEntry<K, V> lastReturned = null;
        int expectedModCount = modCount;
        public final boolean hasNext() {
            return next != header;
        }
        final LinkedEntry<K, V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            LinkedEntry<K, V> e = next;
            if (e == header)
                throw new NoSuchElementException();
            next = e.nxt;
            return lastReturned = e;
        }
        public final void remove() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (lastReturned == null)
                throw new IllegalStateException();
            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }
    }

现在可以得到结论，trimToSize中的那行代码得到的就是header.next对应的节点，也就是最近最不常使用的那个节点。

 以上就是Java和Android的LRU缓存及实现原理 的内容，更多相关内容请关注PHP中文网（www.php.cn）！