Android advanced thorough understanding of the LruCache cache mechanism principle

[[421640]]

Preface

Android has three levels of cache, the main ones are memory cache and hard disk cache. The implementation of these two cache mechanisms applies the LruCache algorithm. Today we will thoroughly understand the cache mechanism in Android from usage to source code analysis;

1. Introduction to LruCache Concept

1. What is LruCache?

LruCache is a cache class provided by Android 3.1, so you can directly use LruCache to implement memory cache in Android. DisLruCache is not yet part of the Android SDK, but the official Android documentation recommends using this algorithm to implement hard disk cache;

LruCache is a generic class. Its main algorithm principle is to store the most recently used objects in LinkedHashMap with strong references (the object reference method we usually use). When the cache is full, the least recently used object is removed from the memory, and get and put methods are provided to complete the cache acquisition and addition operations;

2. Use of LruCache

The use of LruCache is very simple. Let's take image cache as an example.

 int maxMemory = ( int ) (Runtime.getRuntime().totalMemory()/1024);
 int cacheSize = maxMemory/8;
        mMemoryCache = new LruCache<String,Bitmap>(cacheSize){
 @Override
            protected int sizeOf(String key , Bitmap value) {
 return value.getRowBytes()*value.getHeight()/1024;
 }
 };

① Set the size of the LruCache cache, which is generally 1/8 of the available capacity of the current process;

②Rewrite the sizeOf method to calculate the size of each picture to be cached;

Note: The total cache capacity and the size of each cache object must be in the same unit;

2. Implementation principle of LruCache

The core idea of ​​LruCache is easy to understand. It is to maintain a cache object list, where the object list is arranged in the order of access. That is, the object that has not been accessed will be placed at the end of the queue and will be eliminated. The object that has been accessed recently will be placed at the head of the queue and will be eliminated last.

1. Constructor

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

When creating an LruCache object, it does the following internally:

• Record the maximum capacity maxSize;
• Create a LinkedHashMap with an initial capacity of 0 to store objects;
• Therefore, when creating an LruCache object, we need to specify a maximum capacity value maxSize, which can be a specific value or memory space, and the corresponding method is sizeOf:

 protected int sizeOf(K key , V value) {
 return 1;
 }

If we want to control the cache by quantity, we can see that the default sizeOf method returns 1, which means that each time a piece of data is added, the space it occupies is 1, until the number of added contents reaches maxSize. At this time, if we add more data, the system will select the least frequently used values ​​and remove them;

If the cache limit is memory space, you need to rewrite size to return the size of the space occupied by the object:

 int maxMemory = ( int ) (Runtime.getRuntime().maxMemory())/1024; //Get available memory and convert it to KB
 int maxCache = maxMemory/10; //The cache size is 1/10 of the available memory
      LruCache mMemoryCache = new LruCache<String,Bitmap>(maxCache){
 @Override//Override the sizeOf method to return the memory occupied by each piece of data
          protected int sizeOf(String key , Bitmap value) {
 return value.getRowBytes()*value.getHeight() / 1024;
              // return value.getByteCount() / 1024;
 }
 };

2. Read content

Reading content corresponds to the get method, the source code is as follows:

 public final V get(K key ) {
 if ( key == null ) { //If key is null , throw an exception directly
            throw new NullPointerException( "key == null" );
 }
 V mapValue;
 synchronized (this) {
 mapValue = map.get( key ); //Read the value corresponding to key
            if (mapValue != null ) {
 hitCount++;
 return mapValue; //If the content is obtained, return
 }
 missCount++; //If no content is read, the missCount count increases and execution continues
 }
 /* Trying to create a value may take some time. When the creation is completed, the map may have changed
 If the key used for creation already exists, causing a conflict, the value created by create is discarded.
 * Attempt to   create a value. This may take a long time , and the map
         * may be different when   create () returns . If a conflicting value was
         * added to the map while create () was working, we leave that value in  
         * the map and release the created value.
 */
 //If the value is not obtained, call the create method to try to create an object
 // The create method returns null by default . You can override this method to decide how to add a value when no value is obtained.
        V createdValue = create ( key );
        if (createdValue == null ) {
 return   null ;
 }
 //The following part is the modification actions on the map after creation, including storing objects, adjusting size , etc.
 synchronized (this) {
 createCount++;
            mapValue = map.put( key , createdValue);
            if (mapValue != null ) {
                // There was a conflict so undo that last put
                map.put( key , mapValue);
 } else {
 size += safeSizeOf( key , createdValue);
 }
 }
        if (mapValue != null ) {
            entryRemoved( false , key , createdValue, mapValue);
 return mapValue;
 } else {
            trimToSize(maxSize);
 return createdValue;
 }
 }

The get method tries to read the content according to the passed key. If it cannot be read, you can choose whether to create an object. If you choose to create an object, you need to override the create method to return the object to be created. It is also very simple to use;

3. Storage content

The put method is used to store content:

 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++;
 size += safeSizeOf( key , value);
            previous = map.put( key , value);
            if (previous != null ) {
 size -= safeSizeOf( key , previous);
 }
 }
        if (previous != null ) {
            entryRemoved( false , key , previous, value);
 }
 trimToSize(maxSize);
 return previous;
 }

When storing content, you can see how the cache size is controlled: after storing the content, size += safeSizeOf(key, value); will be executed. The default implementation of safeSizeOf is the sizeOf method. Each time an object is stored, the size will be increased by the corresponding value. If the stored key already has data, the size will remain unchanged;

It also provides an entryRemoved method, which is called when the data is removed (remove is called, the new value is overwritten, and the data that exceeds the cache is deleted). The default implementation is empty.

At the end of put, trimToSize is called, which is a method to control the cache size. This method will be called every time new data is stored. When the current size exceeds the maximum value of the cache, the least recently used data will be deleted through this method;

In addition to normal storage and reading, LruCache also provides a method to read all cached objects at once:

 public synchronized final Map<K, V> snapshot() {
 return new LinkedHashMap<K, V>(map);
 }

4. trimToSize() method

 public void trimToSize( int maxSize) {
 //Dead loop
 while ( true ) {
 K key ;
 V value;
            synchronized (this) {
 //If the map is empty and the cache size is not equal to 0 or the cache size is 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 is smaller than the maximum cache, or the map is empty, there is no need to delete the cache object and exit the loop
                if ( size <= maxSize || map.isEmpty()) {
 break;
 }
 //The iterator gets the first object, which is the element at the end of the queue and the element least recently accessed
                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 );
 }
 }

Summarize

LruCache maintains a collection LinkedHashMap, which is sorted in access order. When the put() method is called, elements are added to the collection, and trimToSize() is called to determine whether the cache is full. If it is full, the LinkedHashMap iterator is used to delete the tail element, that is, the element least recently accessed. When the get() method is called to access the cache object, the LinkedHashMap get() method is called to obtain the corresponding collection element, and the element is updated to the head of the queue;