Android caching mechanism lrucache

1.Android Cache policy in

Generally speaking , Cache policy mainly includes the addition of cache 、 Get and delete these three types of operations . Adding and getting caches is easy to understand , Why delete the cache ？ This is because whether it is memory cache or hard disk cache , Their cache size is limited . When the cache is full , If you want to add a cache, you need to delete some old cache to add a new cache .

therefore LRU(Least Recently Used) The caching algorithm came into being ,LRU Is the least recently used algorithm , Its core idea is when the cache is full , Will give priority to those cache objects that have been used least recently . About Android Third level cache of , The main ones are memory cache and hard disk cache . The implementation of these two caching mechanisms is applied to LruCache Algorithm .

 

2.LruCache

LruCache yes Android 3.1 Provides a cache class , So in Android Can be used directly in LruCache Implement memory cache . Hard disk cache DisLruCache Currently in Android Is not Android SDK Part of , but Android Official documents recommend using this algorithm to realize hard disk caching .

LruCache It's a generic class , The main principle of the algorithm is to store the recently used objects in LinkedHashMap in . When the cache is full , Remove the least recently used object from memory , And provides get and put Method to get and add the cache .

LruCache Is very simple to use , Take the picture cache as an example ：

// Get the maximum memory allocated by the system to each application

int maxMemory=(int)(Runtime.getRuntime().ma xMemory()/1024);

int cacheSize=maxMemory/8; 

private LruCache<String, Bitmap> mMemoryCache;

// to LruCache Distribute 1/8  Maximum memory

mMemoryCache = new LruCache<String, Bitmap>(mCacheSize){  

    // Override the method , To measure Bitmap Size   

    @Override  

    protected int sizeOf(String key, Bitmap value){  

        return value.getRowBytes() * value.getHeight()/1024;  

    }  

};

① Set up LruCache Cache size , Generally, it is... Of the available capacity of the current process 1/8.

② rewrite sizeOf Method , Calculate the size of each picture to be cached .

Be careful ： The total capacity of the cache should be consistent with the size of each cache object .

 

3.LruCache Realization principle

LruCache The core idea of , To maintain a list of cached objects , The arrangement of the object list is implemented according to the access order , That is, objects that have not been accessed , Will be at the end of the team , About to be eliminated , Recently accessed objects will be placed at the head of the team , To be eliminated .

As shown in the figure below ：

This queue is made up of LinkedHashMap Maintenance of .LinkedHashMap By an array of + Two way linked list data structure implementation . The structure of two-way linked list can realize the access order and insertion order , bring LinkedHashMap Medium <key,value> Yes, in a certain order .

Specify... Through the following constructor LinkedHashMap Is the structure of bidirectional linked list in access order or insertion order .

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {

    super(initialCapacity, loadFactor);

    this.accessOrder = accessOrder;

}

among accessOrder Set to true The order of access , by false, Is the insertion order .

Explain with specific examples ：

① When set to true when

public static final void main(String[] args) {

    LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(0, 0.75f, true);

    map.put(0, 0);

    map.put(1, 1);

    map.put(2, 2);

    map.put(3, 3);

    map.put(4, 4);

    map.put(5, 5);

    map.put(6, 6);

    map.get(1);

    map.get(2);

    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

        System.out.println(entry.getKey() + ":" + entry.getValue());

    }

}

Output results ：

0:0

3:3

4:4

5:5

6:6

1:1

2:2

That is, the last output of the most recent access , This is just enough LRU The idea of caching algorithm . so LruCache Clever implementation , Is to make use of LinkedHashMap This data structure .

 

The following is LruCache Look at the source code , How to apply LinkedHashMap To add cache , Get and delete .

 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);

}

from LruCache As you can see in the constructor of LinkedHashMap Access order .

 

(1)put() Method

public final V put(K key, V value) {

    if (key == null || value == null) {

        throw new NullPointerException("key == null || value == null");

    }

    V previous;

    synchronized (this) {

        putCount++; // The value of the inserted cache object plus 1

        // Increase the size of the existing cache

        size += safeSizeOf(key, value);

       // towards map Add cache object to

        previous = map.put(key, value);

        // If there are already cached objects , Then the cache size is restored to the previous

        if (previous != null) {

            size -= safeSizeOf(key, previous);

        }

    }

    //entryRemoved() It's an empty method , It can be realized by itself

    if (previous != null) {

        entryRemoved(false, key, previous, value);

    }

    // Resize cache ( Key methods )

    trimToSize(maxSize);

    return previous;

}

put() The method is not difficult , The important thing is to add cache objects , call trimToSize() Method to determine whether the cache is full , If full, delete the least recently used algorithm .

trimToSize() Method ：

public void trimToSize(int maxSize) {

    while (true) { // Dead cycle

        K key;

        V value;

        synchronized (this) {

            // If map Empty and cache size It's not equal to 0 Or cache size Less than 0, Throw an exception

            if (size < 0 || (map.isEmpty() && size != 0)){

                throw new IllegalStateException( getClass().getName() + ".sizeOf() is reporting inconsistent results!");

            }

            // If the cache size size Less than maximum cache , perhaps map It's empty , There is no need to delete the cache object , Out of the loop

            if (size <= maxSize || map.isEmpty()) {

                break;

            }

            // The iterator gets the first object , That is, the element at the end of the team , The least recently accessed element

            Map.Entry<K, V> toEvict = map.entrySet().iterator().next();

            key = toEvict.getKey();

            value = toEvict.getValue();

            // Delete the object , And update the cache size

            map.remove(key);

            size -= safeSizeOf(key, value);

            evictionCount++;

        }

        entryRemoved(true, key, value, null);

    }

}

trimToSize() Method to delete LinkedHashMap The element at the end of the squadron , That is, the least recently visited , Until the cache size is less than the maximum .

When calling LruCache Of get() Method to get the cached objects in the collection , On behalf of a visit to the element , The queue will be updated , Keep the entire queue in order of access . This update process is in LinkedHashMap Medium get() Method .

 

(2)get() Method

public final V get(K key) {

    if (key == null) {

        throw new NullPointerException("key == null");

    }

    V mapValue;

    synchronized (this) {

        // Get the corresponding cache object .get() Method will implement the function of updating the accessed element to the queue header

        mapValue = map.get(key);

        if (mapValue != null) {

            hitCount++;

            return mapValue;

        }

        missCount++;

    }

}

among LinkedHashMap Of get() The method is as follows ：

public V get(Object key) {

    LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);

    if (e == null)

        return null;

    // The key method to realize sorting

    e.recordAccess(this);

    return e.value;

}

call recordAccess() The method is as follows ：

 void recordAccess(HashMap<K,V> m) {

    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;

    // Determine whether it is access sorting

    if (lm.accessOrder) {

        lm.modCount++;

        remove();  // Delete this element

        // Move this element to the head of the queue

        addBefore(lm.header);

    }

}

so LruCache A collection is maintained in LinkedHashMap , The LinkedHashMap It is sorted in access order . When calling put() When the method is used , Will add elements to the combination , And call trimToSize() Determine whether the cache is full , If it's full, use LinkedHashMap Deletes the tail of the queue element using the iterator , That is, the least recently accessed element . When calling get() Method to access the cache object , Will call LinkedHashMap Of get() Method to obtain the corresponding set element , At the same time, the element will be updated to the team head .