关于lruCache（最近最少使用）的算法，这是一个比较重要的算法，它的应用非常广泛，不仅仅在Android中使用，Linux系统等其他地方中也有使用；今天就来看一看这其中的奥秘；

讲到LruCache，就不得不讲一讲LinkedHashMap，而对于LinkedHashMap，它继承的是HashMap，那么我们就先从HashMap开始看起吧；

注：此篇博客所讲的所有知识都是在jdk1.8环境下的，java8的hashmap相比之前的版本又做了一层优化，当链表过长时（默认超过8），会改为采用红黑树这种自平衡的数据结构去进行存储优化

HashMap
我们知道，数据结构中的存在两种常见的存储结构，一个是数组，一个是链表；两者各有优劣，首先数组的存储空间在内存中是连续的，这就就导致占用内存严重，连续的大内存进入老年代的可能性也会变大，但是正因为如此，寻址就显得简单，也就是说查询某个arr会有指定的下标，但是插入和删除比较困难，因为每次插入和删除时，如果数组在插入这个地方后面还有很多数据，那就要后面的数据整体往前或者往后移动。对于链表来说存储空间是不连续的，占用内存比较宽松，它的基本结构是一个节点（node）都会包含下一个节点的信息（如果是双向链表会存在两个信息一个指向上一个一个指向下一个），正因为如此寻址就会变得比较困难，插入和删除就显得容易，链表插入和删除的时候只需要修改节点指向信息就可以了。

那么两者各有优劣，将它们两者结合起来会有什么效果呢？自然早就有大神尝试过了，并且尝试的很成功，它的产物就是HashMap哈希表，也叫散列表；

HashMap的主干是一个数组，里面存储的是一个个的Node，Node中包含了哈希值，key，value和下一个Node的引用；

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
存储在HashMap中的每一个值都需要一个key，这是为什么呢？这个问题可以再问细一点，hashmap是如何存放数据的？
我们先来看看他的一些基本属性：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
这个属性表示HashMap的初始容量大小是16；

static final int MAXIMUM_CAPACITY = 1 << 30;
最大容量为2^30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;
这个表示加载因子默认为0.75，代表hashmap的填充程度，加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。

反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏（很多空间还没用，就开始扩容了）

冲突的机会越大,则查找的成本越高.

因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.

如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让它默认为0.75就可以了；

/**

• The bin count threshold for using a tree rather than list for a
• bin. Bins are converted to trees when adding an element to a
• bin with at least this many nodes. The value must be greater
• than 2 and should be at least 8 to mesh with assumptions in
• tree removal about conversion back to plain bins upon
• shrinkage.
  */
  static final int TREEIFY_THRESHOLD = 8;

/**

• The bin count threshold for untreeifying a (split) bin during a
• resize operation. Should be less than TREEIFY_THRESHOLD, and at
• most 6 to mesh with shrinkage detection under removal.
  */
  static final int UNTREEIFY_THRESHOLD = 6;
  临界值，这个字段主要是用于当HashMap的size大于它的时候，需要触发resize()方法进行扩容
  构造方法：

public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
可以清晰的看到当new一个HashMap时，并没有为数组分配内存空间（有一个传入map参数的构造方法除外）；

几个核心方法：

put方法实际调用的就是putVal方法，所以我们先看putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
这里的逻辑由于是java8，所以会复杂一点，里面有几个关键点，记录下来，对比着源码看：

（1）putVal方法其实就可以理解为put方法，我们使用hashmap的时候，什么时候才会使用put方法呢，当你想要存储数据的时候会调用，那么putVal方法的逻辑就是为了把你需要存储的数据按位置存放好就可以了；

（2）具体的存放逻辑是通过复杂的if判断来完成的，首先会判断当前通过key和hash函数计算出的数组下标位置的是否为null，如果是空，直接将Node对象存进去；如果不为空，那么就将key值与桶中的Node的key一一比较，在比较的过程中，如果桶中的对象是由红黑树构造而来，那么就使用红黑树的方法去进行存储，如果不是，那么就继续判断当前桶中的元素是否大于8，大于8的话就使用红黑树处理（调用treeifybin方法），如果小于8，那么进行最后的判断是否key值相同，如果相同，就直接将旧的node对象替换为新的node对象；这样就保证了存储的正确性；

（3）在putVal中有这么一句

++modCount;
这里的modCount的作用是用来判断当前HashMap是否在由一个线程操作，因为hashmap本身是线程不安全的，多线程操作会造成其中数据不安全等多种问题，modcount记录的是put的次数，如果modcount不等于put的node的个数的话，就代表有多个线程同时操作，就会报ConcurrentModificationException异常；

再来看看get方法，get方法其实调用的是getNode方法

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
这里也有几个点：

bucket里的第一个节点，直接命中；
如果有冲突，则通过key.equals(k)去查找对应的entry
若为树，则在树中通过key.equals(k)查找，O(logn)；
若为链表，则在链表中通过key.equals(k)查找，O(n)。
接下来看看hashmap中逻辑最复杂但是也最为经典的扩容机制，他主要是由resize方法实现的：

final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
说到扩容，就不得不提到上述的几个属性

（1）Capacity：hashmap的容量，其实就是hashmap数组的长度，也就是capacity=array.length

（2）threshold：扩容的临界值，当数组中元素的个数达到这个值的时候，就会进行扩容

（3）loadFactor：加载因子，表示数组的填充程度，默认为0.75（不要轻易修改）

这三者的关系是threshold/loadFactor=Capacity；

resize方法中主要是做了如何去扩容的逻辑判断，其中包括

（1）如果此时hashmap的容量大于2^{30，那么就不扩容，不扩容的方法是将threshold的值赋值为2}30-1，就不会扩容了

（2）一次扩容的大小是扩容一倍，如果初始大小为16，那么扩容后为32

（3）Java8的hashmap由于引入了红黑树，所以如果采用桶内的存储结构为红黑树的话，那么会调用相应红黑树的算法，如果是链表，那么就会将链表拆分为两个链表，再将两个链表重新放入相对应的的位置中，这里是需要重新计算每个元素的hash值的，因为要保证，旧的数组和新的数组的元素的索引要保证相同；

到这里，有几个问题要回答：

什么时候会使用HashMap？他有什么特点？

是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。

你知道HashMap的工作原理吗？

通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

你知道get和put的原理吗？equals()和hashCode()的都有什么作用？

通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点

你知道hash的实现吗？为什么要这样实现？

在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。
关于Java集合的小抄中是这样描述的：
以Entry[]数组实现的哈希桶数组，用Key的哈希值取模桶数组的大小可得到数组下标。
插入元素时，如果两条Key落在同一个桶(比如哈希值1和17取模16后都属于第一个哈希桶)，Entry用一个next属性实现多个Entry以单向链表存放，后入桶的Entry将next指向桶当前的Entry。
查找哈希值为17的key时，先定位到第一个哈希桶，然后以链表遍历桶里所有元素，逐个比较其key值。
当Entry数量达到桶数量的75%时(很多文章说使用的桶数量达到了75%，但看代码不是)，会成倍扩容桶数组，并重新分配所有原来的Entry，所以这里也最好有个预估值。
取模用位运算(hash & (arrayLength-1))会比较快，所以数组的大小永远是2的N次方， 你随便给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。
iterator()时顺着哈希桶数组来遍历，看起来是个乱序。

当两个对象的hashcode相同会发生什么？

因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。

如果两个键的hashcode相同，你如何获取值对象？

找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。因此，设计HashMap的key类型时，如果使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择

如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置

你了解重新调整HashMap大小存在什么问题吗？

当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。因此在并发环境下，我们使用CurrentHashMap来替代HashMap

为什么String, Interger这样的wrapper类适合作为键？

因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能

这就是关于HashMap的解析，下面看看LinkedHashMap的源码解析，LinkedHashMap继承自HashMap，所以理解了HashMap，LinkedHashMap就很简单了；

LinkedHashMap
首先看一下他的继承关系：

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
继承HashMap，实现了Map接口

再看看他的成员变量

transient LinkedHashMapEntry<K,V> head;
用于指向双向链表的头部

transient LinkedHashMapEntry<K,V> tail;
用于指向双向链表的尾部

final boolean accessOrder;
用于LinkedHashMap的迭代顺序，true表示基于访问的顺序来排列，也就是说，最近访问的Node放置在链表的尾部，false表示按照插入的顺序来排列；

构造方法：

跟HashMap类似的构造方法这里就不一一赘述了，里面唯一的区别就是添加了前面提到的accessOrder，默认赋值为false——按照插入顺序来排列，这里主要说明一下不同的构造方法。

public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
get（）方法：

public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
这里的afterNodeAccess方法是按照访问顺序排列的关键：

void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
这里的get方法比hashmap就复杂了一些，因为他在得到值的同时，还需要将得到的元素放在链表的尾部，至于是怎么放置的，无非就是数据结构中的双向循环链表的知识，分四种情况：

正常情况下：查询的p在链表中间，那么将p设置到末尾后，它原先的前节点b和后节点a就变成了前后节点。

情况一：p为头部，前一个节点b不存在，那么考虑到p要放到最后面，则设置p的后一个节点a为head
情况二：p为尾部，后一个节点a不存在，那么考虑到统一操作，设置last为b
情况三：p为链表里的第一个节点，head=p

put方法：

在LinkedHashMap中是找不到put方法的，因为，它使用的是父类HashMap的put方法，不过它将hashmap中的put方法中调用的相关方法去重写了，具体的就是newNode（），afterNodeAccess和afterNodeInsertion方法

先看newNode方法：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
LinkedHashMapEntry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
主要功能就是把新加的元素添加到链表的尾部；

有关LinkedHashMap，因为与HashMap相似，我只提了里面的存储顺序问题，这也是LinkedHashMap的最主要的功能；

LruCache内存缓存原理
在讲LruCache之前 ，先看看它是怎么使用的，拿它在图片缓存的应用来说，看下面的代码：

private LruCache<String,Bitmap> lruCache;

public MemoryCacheUtils(){
//获取手机最大内存的1/8
long memory=Runtime.getRuntime().maxMemory()/8;
lruCache=new LruCache<String, Bitmap>((int)memory){
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getByteCount();
}
};
}

/**

• 从内存中读图片
• @param url
• @return
  */
  public Bitmap getBitmapFromMemory(String url) {
  Bitmap bitmap = lruCache.get(url);
  return bitmap;
  }

public void setBitmapToMemory(String url, Bitmap bitmap) {
lruCache.put(url,bitmap);
}
这是最简单的图片的三级缓存中的内存缓存的写法，我们先看使用构造器new一个LruCache发生了什么：

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);
}
可以看见LruCache的构造器主要是定义了缓存的最大值，并且调用了LinkedHashMap的三个参数的构造方法，保证按照访问顺序来排列元素，生成一个LinkedHashMap对象，赋值给map；

在看它的get方法

public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}

V mapValue;
synchronized (this) {
    mapValue = map.get(key);
    if (mapValue != null) {
        hitCount++;
        return mapValue;
    }
    missCount++;
}

/*
 * 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.
 */

V createdValue = create(key);
if (createdValue == null) {
    return null;
}

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

}
这里面主要做了两件事，首先会根据key查找map中是否存在对应的Value，也就是对应key值的缓存，如果找到，直接命中，返回此份缓存，如果没有找到，会调用create（）方法去尝试创建一个Value，但是我看了create（）源码，是返回null的；

protected V create(K key) {
return null;
}
也就是说，如果你不主动重写create方法，LruCache是不会帮你创建Value的；其实，正常情况下，不需要去重写create方法的，因为一旦我们get不到缓存，就应该去网络请求了；

再看put方法：

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;

}
主要逻辑是，计算新增加的大小，加入size，然后把key-value放入map中，如果是更新旧的数据（map.put(key, value)会返回之前的value），则减去旧数据的大小，并调用entryRemoved(false, key, previous, value)方法通知旧数据被更新为新的值，最后也是调用trimToSize(maxSize)修整缓存的大小。

LruCache大致源码就是这样，它对LRU算法的实现主要是通过LinkedHashMap来完成。另外，使用LRU算法，说明我们需要设定缓存的最大大小，而缓存对象的大小在不同的缓存类型当中的计算方法是不同的，计算的方法通过protected int sizeOf(K key, V value)实现，我们要缓存Bitmap对象，则需要重写这个方法，并返回bitmap对象的所有像素点所占的内存大小之和。还有，LruCache在实现的时候考虑到了多线程的访问问题，所以在对map进行更新时，都会加上同步锁。

DiskLruCache硬盘缓存原理
讲完LruCache之后，我们趁热打铁，抓紧看一下DiskLruCache硬盘缓存的相关原理，DiskLruCache和LruCache内部都是使用了LinkedHashMap去实现缓存算法的，只不过前者针对的是将缓存存在本地，而后者是直接将缓存存在内存；

先看看它是如何使用的吧，这里和LruCache不一样，DiskLruCache不在Android API内，所以如果我们要使用它，必须将其源码下载，可以点击这里进行下载，下载完成后，导入到你自己的项目中就可以使用了；

首先你要知道，DiskLruCache是不能new出实例的，如果我们要创建一个DiskLruCache的实例，则需要调用它的open()方法，接口如下所示：

public static DiskLruCache open(File directory, int appVersion, int valueCount, long maxSize)
open()方法接收四个参数，第一个参数指定的是数据的缓存地址，第二个参数指定当前应用程序的版本号，第三个参数指定同一个key可以对应多少个缓存文件，基本都是传1，第四个参数指定最多可以缓存多少字节的数据。

其中缓存地址通常都会存放在 /sdcard/Android/data/<application package>/cache 这个路径下面，但同时我们又需要考虑如果这个手机没有SD卡，或者SD正好被移除了的情况，因此比较优秀的程序都会专门写一个方法来获取缓存地址，如下所示：

public File getDiskCacheDir(Context context, String uniqueName) {
String cachePath;
if (Environment.MEDIA_MOUNTED.equals(Environment.getExternalStorageState()) || !Environment.isExternalStorageRemovable()) {
cachePath = context.getExternalCacheDir().getPath();
} else {
cachePath = context.getCacheDir().getPath();
}
return new File(cachePath + File.separator + uniqueName);
}
可以看到，当SD卡存在或者SD卡不可被移除的时候，就调用getExternalCacheDir()方法来获取缓存路径，否则就调用getCacheDir()方法来获取缓存路径。前者获取到的就是 /sdcard/Android/data/<application package>/cache 这个路径，而后者获取到的是 /data/data/<application package>/cache 这个路径。

接着是应用程序版本号，我们可以使用如下代码简单地获取到当前应用程序的版本号：

public int getAppVersion(Context context) {
try {
PackageInfo info = context.getPackageManager().getPackageInfo(context.getPackageName(), 0);
return info.versionCode;
} catch (PackageManager.NameNotFoundException e) {
e.printStackTrace();
}
return 1;
}
后面两个参数就没什么需要解释的了，第三个参数传1，第四个参数通常传入10M的大小就够了，这个可以根据自身的情况进行调节。

因此，一个非常标准的open()方法就可以这样写：

private DiskLruCache getDiskLruCache(Context context){
try {
File cacheDir = getDiskCacheDir(context, "bitmap");
if (!cacheDir.exists()) {
cacheDir.mkdirs();
}
mDiskLruCache = DiskLruCache.open(cacheDir, getAppVersion(context), 1, 10 * 1024 * 1024);
} catch (IOException e) {
e.printStackTrace();
}
return mDiskLruCache;
}
关于写入缓存：

写入的操作是借助DiskLruCache.Editor这个类完成的。类似地，这个类也是不能new的，需要调用DiskLruCache的edit()方法来获取实例，接口如下所示：

public Editor edit(String key) throws IOException
现在就可以这样写来得到一个DiskLruCache.Editor的实例：
public void setBitmapToLocal(Context context,String url, InputStream inputStream) {
BufferedOutputStream out = null;
BufferedInputStream in = null;
try {
DiskLruCache.Editor editor = getDiskLruCache(context).edit(getMD5String(url));
if (editor != null) {
OutputStream outputStream = editor.newOutputStream(0);
in = new BufferedInputStream(inputStream, 8 * 1024);
out = new BufferedOutputStream(outputStream, 8 * 1024);
int b;
while ((b = in.read()) != -1) {
out.write(b);
}
editor.commit();
}
mDiskLruCache.flush();
} catch (IOException e) {
e.printStackTrace();
}
}
读取缓存：

读取的方法要比写入简单一些，主要是借助DiskLruCache的get()方法实现的，接口如下所示：

public synchronized Snapshot get(String key) throws IOException
所以，你可以这样读取：

public Bitmap getBitmapFromLocal(String url) {
try {
DiskLruCache.Snapshot snapShot = mDiskLruCache.get(getMD5String(url));
if (snapShot != null) {
InputStream is = snapShot.getInputStream(0);
Bitmap bitmap = BitmapFactory.decodeStream(is);
return bitmap;
}
} catch (IOException e) {
e.printStackTrace();
}
return null;
}
了解怎么使用还不够，DiskLruCache会自动生成journal文件，这个文件是日志文件，主要记录的是缓存的操作；

第一行是个固定的字符串“libcore.io.DiskLruCache”，标志着我们使用的是DiskLruCache技术。第二行是DiskLruCache的版本号，这个值是恒为1的。第三行是应用程序的版本号，我们在open()方法里传入的版本号是什么这里就会显示什么。第四行是valueCount，这个值也是在open()方法中传入的，通常情况下都为1。第五行是一个空行。前五行也被称为journal文件的头，这部分内容还是比较好理解的

第六行是以一个DIRTY前缀开始的，后面紧跟着缓存图片的key。通常我们看到DIRTY这个字样都不代表着什么好事情，意味着这是一条脏数据。没错，每当我们调用一次DiskLruCache的edit()方法时，都会向journal文件中写入一条DIRTY记录，表示我们正准备写入一条缓存数据，但不知结果如何。然后调用commit()方法表示写入缓存成功，这时会向journal中写入一条CLEAN记录，意味着这条“脏”数据被“洗干净了”，调用abort()方法表示写入缓存失败，这时会向journal中写入一条REMOVE记录。也就是说，每一行DIRTY的key，后面都应该有一行对应的CLEAN或者REMOVE的记录，否则这条数据就是“脏”的，会被自动删除掉。其中152313是图片的大小

接下来我们就开始对源码分析：

在分析之前，我们可以这样想，有了上面的LruCache缓存方式之后，DiskLruCache的原理会是怎样，LruCache将图片存到内存中，DiskLruCache存在硬盘中，那么不就相当于把内存中的图片存到本地中么，这么想会简单许多：

首先还是从open入口看：

public static DiskLruCache open(File directory, int appVersion, int valueCount, long maxSize)
throws IOException {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
if (valueCount <= 0) {
throw new IllegalArgumentException("valueCount <= 0");
}

// If a bkp file exists, use it instead.
File backupFile = new File(directory, JOURNAL_FILE_BACKUP);
if (backupFile.exists()) {
File journalFile = new File(directory, JOURNAL_FILE);
// If journal file also exists just delete backup file.
if (journalFile.exists()) {
backupFile.delete();
} else {
renameTo(backupFile, journalFile, false);
}
}

// Prefer to pick up where we left off.
DiskLruCache cache = new DiskLruCache(directory, appVersion, valueCount, maxSize);
if (cache.journalFile.exists()) {
try {
cache.readJournal();
cache.processJournal();
return cache;
} catch (IOException journalIsCorrupt) {
System.out
.println("DiskLruCache "
+ directory
+ " is corrupt: "
+ journalIsCorrupt.getMessage()
+ ", removing");
cache.delete();
}
}

// Create a new empty cache.
directory.mkdirs();
cache = new DiskLruCache(directory, appVersion, valueCount, maxSize);
cache.rebuildJournal();
return cache;
}
DiskLruCache对象初始化初始化的时候做的事情就两件事：第一通过日志文件头信息去判断之前缓存是否可用、第二解析之前缓存信息到LinkedHashMap；

首先判断是否有日志文件，如果有日志文件说明之前有缓存过信息，对上次的缓存信息做处理，关键的东西在journal文件里面，从journal文件解析到之前的缓存信息；在日志文件中，去读里面之前的缓存信息。判断缓存是否过期，同时把之前的缓存信息记录保存到lruEntries，Map里面去。对读到的上次缓存信息做处理，计算size，把没有调用Edit.commit（）的缓存剔除掉

读日志文件的方法readJournal（）

private void readJournal() throws IOException {
StrictLineReader reader = new StrictLineReader(new FileInputStream(journalFile), Util.US_ASCII);
try {
String magic = reader.readLine();
String version = reader.readLine();
String appVersionString = reader.readLine();
String valueCountString = reader.readLine();
String blank = reader.readLine();
if (!MAGIC.equals(magic)
|| !VERSION_1.equals(version)
|| !Integer.toString(appVersion).equals(appVersionString)
|| !Integer.toString(valueCount).equals(valueCountString)
|| !"".equals(blank)) {
throw new IOException("unexpected journal header: [" + magic + ", " + version + ", "
+ valueCountString + ", " + blank + "]");
}

int lineCount = 0;
while (true) {
  try {
    readJournalLine(reader.readLine());
    lineCount++;
  } catch (EOFException endOfJournal) {
    break;
  }
}
redundantOpCount = lineCount - lruEntries.size();

// If we ended on a truncated line, rebuild the journal before appending to it.
if (reader.hasUnterminatedLine()) {
  rebuildJournal();
} else {
  journalWriter = new BufferedWriter(new OutputStreamWriter(
      new FileOutputStream(journalFile, true), Util.US_ASCII));
}

} finally {
Util.closeQuietly(reader);
}
}
其中主要做两件事：

（1）读日志文件的头部信息，标记，缓存版本，应用版本，进而判断日志文件是否过期

（2）把日志文件的缓存记录读取到lruEntries，map中；

处理缓存信息的方法processJournal（）方法

private void processJournal() throws IOException {
deleteIfExists(journalFileTmp);
for (Iterator<Entry> i = lruEntries.values().iterator(); i.hasNext(); ) {
Entry entry = i.next();
if (entry.currentEditor == null) {
for (int t = 0; t < valueCount; t++) {
size += entry.lengths[t];
}
} else {
entry.currentEditor = null;
for (int t = 0; t < valueCount; t++) {
deleteIfExists(entry.getCleanFile(t));
deleteIfExists(entry.getDirtyFile(t));
}
i.remove();
}
}
}
这里主要做两件事：

（1）计算整个缓存文件的大小

（2）把正在被编辑的key（上次保存缓存的时候没有调用Edit.commit()）,可以认为是没有写成功的缓存，重置掉（相应的缓存文件删除，并且从lruEntries中删除）

保存缓存操作edit

private synchronized Editor edit(String key, long expectedSequenceNumber) throws IOException {
checkNotClosed();
validateKey(key);
Entry entry = lruEntries.get(key);
if (expectedSequenceNumber != ANY_SEQUENCE_NUMBER && (entry == null
|| entry.sequenceNumber != expectedSequenceNumber)) {
return null; // Snapshot is stale.
}
if (entry == null) {
entry = new Entry(key);
lruEntries.put(key, entry);
} else if (entry.currentEditor != null) {
return null; // Another edit is in progress.
}

Editor editor = new Editor(entry);
entry.currentEditor = editor;

// Flush the journal before creating files to prevent file leaks.
journalWriter.write(DIRTY + ' ' + key + '\n');
journalWriter.flush();
return editor;
}
要保存缓存的时候，要做两件事一是保存缓存文件，二是写缓存日志文件。为了保存缓存文件我们写的得到Edit对象，然后通过Edit对象得到OutputStream对象然后才可以写入文件，最后commit（）提交保存。总的来说五个步骤；

（1）调用edit（）得到Edit对象

（2）调用Editt.newOutputStream（）得到OutputStream

（3）调用OutputStream.write（）把缓存写入文件

（4）Edit.commit（）确定缓存写入【commit不用每次都调用，可以挑个合适的时间调用】

（5）最后调用flush（）。

读取缓存操作get

public synchronized Snapshot get(String key) throws IOException {
checkNotClosed();
validateKey(key);
Entry entry = lruEntries.get(key);
if (entry == null) {
return null;
}

if (!entry.readable) {
return null;
}

// Open all streams eagerly to guarantee that we see a single published
// snapshot. If we opened streams lazily then the streams could come
// from different edits.
InputStream[] ins = new InputStream[valueCount];
try {
for (int i = 0; i < valueCount; i++) {
ins[i] = new FileInputStream(entry.getCleanFile(i));
}
} catch (FileNotFoundException e) {
// A file must have been deleted manually!
for (int i = 0; i < valueCount; i++) {
if (ins[i] != null) {
Util.closeQuietly(ins[i]);
} else {
break;
}
}
return null;
}

redundantOpCount++;
journalWriter.append(READ + ' ' + key + '\n');
if (journalRebuildRequired()) {
executorService.submit(cleanupCallable);
}

return new Snapshot(key, entry.sequenceNumber, ins, entry.lengths);
}
读缓存记录这个就简单了，得到Snapshot，然后通过Snapshot去得到InputStream或者直接得到具体的缓存内容。都会从缓存文件中去读取信息。
总结来说：

DiskLruCache的实现两个部分：日志文件和具体的缓存文件。每次对缓存存储的时候除了对缓存文件做相应的操作，还会在日志文件做相应的记录。每条日志文件有四种情况：CLEAN（调用了edit（）之后，保存了缓存，并且调用了Edit.commit（）了）、DIRTY（缓存正在编辑，调用edit（）函数）、REMOVE（缓存写入失败）、READ（读缓存）。要想根据key从缓存文件中读取到具体的缓存信息，先得到Snapshot，然后根据Snapshot的一些方法做一些了的操作得到具体缓存信息。要保存一个缓存信息的时候写得到Editor，然后根据Editor对缓存文件做一些列的操作最后如果是保存了缓存信息记得commit下确认提交。
————————————————
原文链接：https://blog.csdn.net/pgg_cold/article/details/79457987