LRU-Cache und Implementierungsprinzipien von Java und Android
- 黄舟Original
- 2017-02-20 10:29:001541Durchsuche
1. Übersicht
Android stellt die LRUCache-Klasse bereit, mit der sich bequem das Caching des LRU-Algorithmus implementieren lässt. Java bietet LinkedHashMap, mit dem sich der LRU-Algorithmus einfach implementieren lässt. Javas LRULinkedHashMap erbt LinkedHashMap direkt und der LRU-Algorithmus kann mit sehr wenigen Änderungen implementiert werden.
2. Der LRU-Algorithmus von Java ist LinkedHashMap und führt bestimmte Änderungen basierend auf HashMap durch.
1. HashMap
Das erste, was zu beachten ist, ist, dass HashMap alle Knoteninformationen in der Entryb77a8d9c3c319e50d4b02a976b347910-Struktur speichert. Eintragb77a8d9c3c319e50d4b02a976b347910 speichert die Schlüssel-, Wert- und Hash-Informationen, die dem Knoten entsprechen, und speichert auch den Verweis auf den nächsten Knoten des aktuellen Knotens. Daher ist Eintragb77a8d9c3c319e50d4b02a976b347910 eine einseitig verknüpfte Liste. Die Speicherstruktur von HashMap besteht aus einem Array und einer einseitig verknüpften Liste. Der jedem Schlüssel entsprechende HashCode befindet sich an einer Position im HashMap-Array. Wenn mehrere Schlüssel demselben HashCode entsprechen, entsprechen sie derselben Position im Array. Zu diesem Zeitpunkt speichert die HashMap die entsprechenden Informationen. Fügen Sie es in Eintragb77a8d9c3c319e50d4b02a976b347910 ein und verwenden Sie eine verknüpfte Liste, um diese Einträgeb77a8d9c3c319e50d4b02a976b347910 zu verbinden.
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'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) {
}
}
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;
}<1> int i = indexFor(hash, table.length);
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);
}Dabei gibt es jedoch ein Problem. Wenn die Länge 9 beträgt, beträgt die erhaltene Länge-1-Information 8 (1000). gelöscht werden, aber das erhaltene Ergebnis ist definitiv falsch. Die Größe des Arrays muss also etwas Besonderes sein. Wenn Sie sich den Quellcode ansehen, können Sie feststellen, dass HashMap sicherstellt, dass die Anzahl der entsprechenden Arrays jederzeit 2 hoch n-tel beträgt.
Rufen Sie beim Putten zunächst die Methode inflateTable auf. Der Schwerpunkt liegt auf der Methode „roundUpToPowerOf2“, obwohl ihr Inhalt eine große Anzahl bitbezogener Operationen und Verarbeitungen enthält, was nicht sehr klar ist. Aus den Kommentaren geht jedoch hervor, dass dadurch sichergestellt wird, dass die Anzahl der Arrays auf 2 erhöht wird Leistung.
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);
}<2> for (Entry<K,V> e = table[i]; e != null; e = e.next)
<3> addEntry(hash, key, value, i);
/**
* 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++;
}LinkedHashMap wird basierend auf HashMap modifiziert. Ändern Sie zunächst den Eintrag von einer einfach verknüpften Liste in eine doppelt verknüpfte Liste. Verweise auf vor und nach dem Teameintritt hinzugefügt.
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();
}
}LinkedHashMap stellt keine Put-Methode bereit, aber LinkedHashMap schreibt die Methoden addEntry und createEntry wie folgt um:
/**
* 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'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++;
}
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）！