在手机应用开发中，为了保存数据访问的流畅性和降低网络流量的消耗，缓存是我们经常需要使用到的。而缓存的实现有多种方式，如LFU（最少的使用）、LRU（最不经常的使用）等。LRU算法是我们开发中经常使用的一种方式，本篇主要分许Android官方提供的LruCache的实现方式 。

Lru介绍

  • Lru是一种常见的缓存算法，其实现原理是当缓存数据量超过规定的范围时，就把最早存入的数据删除，确保缓存数量在规定的范围内。
  • 在Java语言中Lru缓存算法的实现一般有两种，一种是使用LinkedHashMap实现，一种是自己设计使用链表+HashMap实现。

Androiod中LruChche的实现

在Android中已经对LruCache添加了实现类，可以方便的实现Lru缓存。这里就不介绍关于LruCahe的使用，主要是对Android官方的LruCache实现的分析。

  1. Android官方提供的LruCache的底层实现是基于LinkedHashMap来实现的。LinkedHashMap是继承自HashMap类，所以都是存储键值对的结构，同时LinkedHashMap加入了双向循环链表，可以保存节点的插入顺序，这提供了Lru实现的基础。

  2. LruCache的构造，LruCache只提供了一个传入容量值的的构造函数，函数中初始化LinkedHashMap指定元素按照访问顺序排序。

    1
    2
    3
    4
    5
    6
    7
    8
    //构造函数中传入缓存容量值
    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);//指定按照访问顺序排序
       }

  3. LruCache的put操作，调用map的put方法存入数据，同时执行缓存清理方法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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);//执行map的put操作获取
         	 if (previous != null) {
          	  size -= safeSizeOf(key, value);
         	 }
       	}
       	if (previous != null) {
         	  entryRemoved(false, key, previous, value);
       	}
       	trimToSize(maxSize);//清理超出容器的数据项
       	return previous;
     	}

  4. LruCache的get操作，根据key取值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    public final V get(K key) {
       	if (key == null) {
         		throw new NullPointerException("key == null");
       	}
    	/**
           * 执行map.get()方法，如果获取到值直接返回。
           * /
       	V mapValue;
       	synchronized (this) {
         		mapValue = map.get(key);
         		if (mapValue != null) {
           		hitCount++;
           		return mapValue;
         		}
         	missCount++;
       	}
       	/**
        	* 在没有获取到值时，会尝试创建一个值，但可能需要较长的时间，而且当创建完成后map可能发生变化。
        	* 如果当create()正在执行时，一个冲突的值添加进map，我们将该值留在map中并释放所创建的值。
        	*/
       	V createdValue = create(key);//创建操作
       	if (createdValue == null) {
         		return null;
       	}
       	synchronized (this) {
         		createCount++;
         		mapValue = map.put(key, createdValue);
         		if (mapValue != null) {
           		//冲突，不做最后的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;
       	}
     	}

  5. remove操作。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    /**
       *根据key移除数据项
       *@return 通过key得到的先前的value值
       */
    public final V remove(K key) {
       	if (key == null) {
         		throw new NullPointerException("key == null");
       	}
       	V previous;
       	synchronized (this) {
         		previous = map.remove(key);//remove操作
         		if (previous != null) {
           		size -= safeSizeOf(key, previous);
         		}
       	}
       	if (previous != null) {
         		entryRemoved(false, key, previous, null);
       	}
       	return previous;
     	}

  6. 缓存清理方法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    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!");
           	}
           	if (size <= maxSize || map.isEmpty()) {
             		break;//在当前存储数据项小于规定容量或者map为空时，停止循环。
           	}
               //删除元素
           	Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
           	key = toEvict.getKey();
           	value = toEvict.getValue();
           	map.remove(key);
           	size -= safeSizeOf(key, value);
           	evictionCount++;
         	 }
         	 entryRemoved(true, key, value, null);
       	}
     	}

Android官方提供在android.util包中的LruCache的实现非常简单，其在底层建立LinkedHashMap，并通过制定accessOrder为true，即按照访问顺序来排序。这样进行put和get操作时将会把最近操作的数据项Entry放入双向链表的后面，从而保证了在清除超出规定范围的数据项时，删除的最前面的的就是当前最少使用的数据项。