LruCache is a caching mechanism that we often use, also known as the “least recently used” caching strategy. Its essential principle is to eliminate data ** in reverse order through historical access records. It believes that the newly accessed data is more likely to be accessed in the future, so this kind of data is maintained in a relatively safe area to prevent it from being eliminated. If the memory bottleneck is exceeded, the oldest data will be eliminated first.
For example
- Let’s say you’re playing a game and there’s a warehouse with 20 places to store your equipment.
- 1-20 pieces of equipment can be stored normally, and sorted according to the time order, the latest storage equipment is ranked last.
- When you use one of these items, it becomes the last item in the order.
- One day you get another piece of equipment, but your warehouse is full, and you can only throw one item to store what you just got. The order is to throw it from the beginning. After new equipment is stored, the order is last. And so on.
Next, we analyze the logic of the source code through normal use, all of which are derived from API 28
- For a one-to-one analysis of each method provided by LruCache, let’s first look at a piece of code that normally uses LruCache
private void lruTest(a) {
LruCache<Integer, Integer> lruCache = new LruCache<>(5);
lruCache.put(1.1);
lruCache.put(2.2);
lruCache.put(3.3);
lruCache.put(4.4);
lruCache.put(5.5);
for (Map.Entry<Integer, Integer> entry : lruCache.snapshot().entrySet()) {
Log.e("LRU", entry.getKey() + ":" + entry.getValue());
}
Log.e("LRU"."After the set storage capacity is exceeded");
lruCache.put(6.6);
for (Map.Entry<Integer, Integer> entry : lruCache.snapshot().entrySet()) {
Log.e("LRU", entry.getKey() + ":"+ entry.getValue()); }} -- Log output --2019-11-18 18:21:03.624 24293-24293/com.we.we E/LRU: 1:1
2019-11-18 18:21:03.624 24293-24293/com.we.we E/LRU: 2:2
2019-11-18 18:21:03.624 24293-24293/com.we.we E/LRU: 3:3
2019-11-18 18:21:03.624 24293-24293/com.we.we E/LRU: 4:4
2019-11-18 18:21:03.624 24293-24293/com.we.we E/LRU: 5:5
2019-11-18 18:21:03.624 24293-24293/com.we.we E/LRU: after the specified storage capacity is exceeded2019-11-18 18:21:03.624 24293-24293/com.we.we E/LRU: 2:2
2019-11-18 18:21:03.624 24293-24293/com.we.we E/LRU: 3:3
2019-11-18 18:21:03.624 24293-24293/com.we.we E/LRU: 4:4
2019-11-18 18:21:03.625 24293-24293/com.we.we E/LRU: 5:5
2019-11-18 18:21:03.625 24293-24293/com.we.we E/LRU: 6:6
Copy the code- The above example is simple: initialize a LruCache with a capacity of 5.
- The put method is called to add the data, and then the Map is obtained through the snapshot() method and then the print is traversed.
- However, putting data beyond the set capacity will replace the data that was put first. We will keep this feature in mind as we look below.
The LruCache constructor
- If you have special needs, you can override sizeOf () to set the sizeOf each piece of cached data
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
// Initialize a LinkedHashMap object with a load factor of 0.75 to start the access sequence. As for what a LinkedHashMap is, we will analyze it later.
this.map = new LinkedHashMap<K, V>(0.0.75 f.true);
}
Copy the codePut () method source parsing
/** * For key, cache its corresponding value, key-value entry placed at the end of the queue **@returnReturns the value of the previous key */
public final V put(K key, V value) {
// If one of the keys is null, throw null pointer exception.
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
putCount++;
SafeSizeOf () returns a value of 1 by default
size += safeSizeOf(key, value);
// The map.put() method returns the value that was replaced, or null if it was not. (The store will only be replaced if the current key already has data before put.)
previous = map.put(key, value);
if(previous ! =null) {
// If the data is replaced, the size needs to be -1, because there is no new data.size -= safeSizeOf(key, previous); }}if(previous ! =null) {
// When one thread calls create and another thread calls put, a key may generate two values, so override this method. This method defaults to an empty method.
entryRemoved(false, key, previous, value);
}
// Determine whether the capacity is exceeded. If so, delete the earliest data until the capacity <= the set value.
trimToSize(maxSize);
return previous;
}
Copy the codeSummary of the put() method
-
- K/V is null, and an exception is thrown if null.
-
- Add K/V to the LinkedHashMap object by locking and incrementing the element entry counter. Add K/V to the LinkedHashMap object by using the LinkedhashMap. put method. If the put method does not return null, then there is data under the key. So size needs to be minus 1.
-
- If the previous! =null, indicating that the current put operation replaces a previous value. If the entryRemoved() method is overridden, it is called back to that method for processing, and if it is not overridden, the method defaults to no processing.
-
- Call trimToSize(maxSize) for capacity detection and processing.
TrimToSize () method source code parsing, and bug discovery
/** * Delete the oldest element until the total number of remaining data is <= maxSize. * /
private void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
if (size < 0|| (map.isEmpty() && size ! =0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
// Break the loop if the current number of elements <= the maximum value.
if (size <= maxSize) {
break;
}
// BEGIN LAYOUTLIB CHANGE
// get the last item in the linked list.
// This is not efficient, the goal here is to minimize the changes
// compared to the platform version.
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
// Get the least used data element. This is a bug in the source code, which I will explain later.
toEvict = entry;
}
// END LAYOUTLIB CHANGE
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
// Remove the element
map.remove(key);
// Count length size -1;
size -= safeSizeOf(key, value);
// Number of cache removals +1
evictionCount++;
}
entryRemoved(true, key, value, null); }}Copy the codeSummary of the trimToSize() method
-
- This method is mainly used for capacity detection and element removal after capacity exceeds.
-
- First, open the sequence, and lock, judge the current data volume <= set the threshold maxSize break out of the loop.
-
- Gets the oldest (and least commonly used) data in the current LinkedHashMap object, but the source code loops through the for loop to get the most recent data.
3.1. For example, the following example and log output can be used to determine the final value of the for loop.
LruCache<Integer, Integer> lruCache = new LruCache<>(5);
lruCache.put(1.1);
lruCache.put(2.2);
lruCache.put(3.3);
lruCache.put(4.4);
lruCache.put(5.5);
for (Map.Entry<Integer, Integer> entry : lruCache.snapshot().entrySet()) {
Log.e("LRU", entry.getKey() + ":" + entry.getValue());
}
2019-11-19 16:22:54.299 31747-31747/com.we.we E/LRU: 1:1
2019-11-19 16:22:54.299 31747-31747/com.we.we E/LRU: 2:2
2019-11-19 16:22:54.300 31747-31747/com.we.we E/LRU: 3:3
2019-11-19 16:22:54.300 31747-31747/com.we.we E/LRU: 4:4
2019-11-19 16:22:54.300 31747-31747/com.we.we E/LRU: 5:5
Copy the code3.2. According to the log print in the above example, we can see that the last printed data is 5, and 5 is the latest inserted data. Is this logic not the latest inserted data? Isn’t that a problem for LRU? I went back to the source code of the previous SDK version, and now let’s compare the logic in API 27 and API 28.
API 27 Map.Entry<K, V> toEvict = map.eldest(); / /... // Eldest is labelled labelled hidden. Public Entry<K, V> eldest() {LinkedEntry<K, V> eldest = ender.nxt; return eldest ! = header ? eldest : null; } API 28 Map.Entry<K, V> toEvict = null; for (Map.Entry<K, V> entry : map.entrySet()) { toEvict = entry; }Copy the code-
3.3. By comparison, this logic is a bug in the source code, but we use the process does not affect the normal function, why is this? In fact, the Framework implementation and SDK source code is inconsistent, and the SDK is a bug version of LruCache.
-
- Remove data and size -1, cache removal times +1
Get () method source parsing
/** * returns if the value corresponding to the specified key exists. Otherwise, create the key-value pair using the create method. * If the corresponding value is returned, the key-value pair is moved to the end of the queue. * When null is returned, there is no corresponding value and it cannot be created */
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
// Get the value of the current key from the LinkedHashMap object
mapValue = map.get(key);
if(mapValue ! =null) {
// Count of cache hits +1
hitCount++;
// and return the end
return mapValue;
}
// Count of cache misses +1
missCount++;
}
/* * Try to create a value, but it can take a long time, and when the create method returns, there is a chance that the hash table will change * * If a conflicting value is added to the hash table, the original value will be retained and the newly generated value will be replaced */
// Create () is the method that needs to be overridden, and returns null if not overridden
V creaweValue = create(key);
if (creaweValue == null) {
return null;
}
synchronized (this) {
// The number of times the value corresponding to the key is created +1
createCount++;
// The map.put method returns the original value for the key, or null if there is no original value for the key
mapValue = map.put(key, creaweValue);
if(mapValue ! =null) {
// If mapValue is not null, it indicates that the key originally has a corresponding value. Therefore, use the original value instead of the newly generated value.
map.put(key, mapValue);
} else {
// If the original key has no corresponding value, a new key pair is added, so size+1 is requiredsize += safeSizeOf(key, creaweValue); }}if(mapValue ! =null) {
entryRemoved(false, key, creaweValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
returncreaweValue; }}Copy the codeSummary of get() method
-
- Linkedhashmap.get (key) ¶ Get () ¶ Get () ¶ Get ();
-
- If linkedhashMap.get (key) does not obtain a value, create() will create the corresponding value, but create() returns null by default, so you need to override the creation process.
-
- If the create() method is overwritten and a value is generated, the lock is inserted through linkedhashmap.put () and determines whether the key had a previous value based on the value returned by the PUT method. If so, put replaces the newly generated value with the original value.
note
- The create(key) method in the above logic is unlocked. If this method is used, multiple threads may call the same key and generate multiple values. Or when one thread calls PUT and another thread calls the create method to create a value for it, in which case the entryRemoved() method is called in the subsequent logic. The entryRemoved() method also needs to be overridden. The value of the argument to the entryRemoved() method determines whether the current call was caused by put or remove or by trimToSize() to vacate space.
@param evicwe true indicates that the entry is being deleted to make room, false indicates that the deletion was caused by put or remove (not to make room). @param newValue newValue of the key. If it is not NULL, the delete is caused by A PUT. Otherwise it is caused by remove
Remove () Source code parsing
/** * Delete the value of the key ** Return the value of the key */
public final V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
previous = map.remove(key);
if(previous ! =null) {
// After deleting data, you need to set the data counter to size-1size -= safeSizeOf(key, previous); }}if(previous ! =null) {
entryRemoved(false, key, previous, null);
}
return previous;
}
Copy the codeSummary of the remove() method
- Call linkedhashMap.remove () to remove the value corresponding to this key, and judge siz-1 by the returned value;
- 2. Call the entryRemoved() method
##### In summary, LruCache has the following characteristics.
-
- There are not many methods in the LruCache class. Most of them rely on the LinkedHashMap method, and LruCache only maintains an internal LinkedHashMap object.
-
- LruCache usage is not thread-safe, so an entryRemoved() method is provided to override the exception case.
-
- LruCache does not support null K and null V because most of its methods are nulled by K/V.
-
Due to space reasons, this article only analyzes the LruCache source code, in the next articleUnderstand LruCache? You have to know LinkedHashMap first, and a word of advice for LruCacheTo parse LinkedHashMap, please browse