编程语言Glide都在用的LruCache

 

前言

说到Glide就有点尴尬，我本来想出一篇《手撕Glide》，但是很遗憾，源码实在太多了。写着写着就3000多字了，甚至还没写完，实在不合适，因为我写文的原则是短小精悍，所以就暂时不出这篇文章了，这次就先讲讲Glide都在用的LruCache有什么神奇之处。另外我抖音的面试在即，也不知道自己水平到了没有，现在出一篇算一篇先。

思维导图

使用方法及结果

在项目中直接导入Glide的库，调用内部的LruCache来看看效果。

1. LruCache lruCache = new LruCacheInteger>(2); 
2. lruCache.put("1", 1); 
3. lruCache.put("2", 2); 
4. lruCache.put("1", 1); 
5. lruCache.put("3", 3); 
6. System.out.println(lruCache.get("1")); 
7. System.out.println(lruCache.get("2")); 
8. System.out.println(lruCache.get("3")); 

简要说明代码内容，创建一个空间为2的存储空间(这里先不透漏内部结构)，用put()方法对数据进行存储，再通过get()对每个数据进行一次获取操作，然后我们再来看看结果。

我的天!!2没了? 这是怎么一回事??为了知道答案，那我们只好进入Glide的库中看看原因了。

LruCache源码导读

先看看LruCache的变量家庭里有哪些小家伙把。

1. public class LruCache { 
2.   // 容量为100的双向链表 
3.   private final Map cache = new LinkedHashMap<>(100, 0.75f, true);  
4.   private final long initialMaxSize; // 初始化最大容量 
5.   private long maxSize; // 最大容量 
6.   private long currentSize; // 已存在容量 
7. } 

同样对于LruCache来说不也和HashMap一样只有三步骤要走嘛，那我就从这三个步骤入手探索一下LruCache好了，但是我们要带上一个问题出发，initialMaxSize的作用是什么?

new LruCache

1. public LruCache(long size) { 
2.   this.initialMaxSize = size; 
3.   this.maxSize = size; 
4. } 

到这里想来读者都已经知道套路了，也就初始化了初始化最大容量和最大容量，那就直接下一步。

put(key, value)

1. public synchronized Y put(@NonNull T key, @Nullable Y item) { 
2.     // 返回值就是一个1 
3.     final int itemSize = getSize(item); 
4.     // 如果1大于等于最大值就无操作 
5.     // 也就说明整个初始化的时候并不能将size设置成1 
6.     if (itemSize >= maxSize) { 
7.       //用于重写的保留方法 
8.       onItemEvicted(key, item); 
9.       return null; 
10.     } 
11.     // 对当前存在数据容量加一 
12.     if (item != null) { 
13.       currentSize += itemSize; 
14.     } 
15.     @Nullable final Y old = cache.put(key, item); 
16.     if (old != null) { 
17.       currentSize -= getSize(old); 
18.      
19.       if (!old.equals(item)) { 
20.         onItemEvicted(key, old); 
21.       } 
22.     } 
23.     evict(); // 1 --> 
24.  
25.     return old; 
26.   } 
27. // 由注释1直接调用的方法 
28. private void evict() { 
29.     trimToSize(maxSize); // 2 --> 
30.   } 
31. // 由注释2直接调用的方法  
32. protected synchronized void trimToSize(long size) { 
33.     Map.Entry last; 
34.     Iterator> cacheIterator; 
35.     // 说明当前的容量大于了最大容量 
36.     // 需要对最后的数据进行一个清理 
37.     while (currentSize > size) { 
38.       cacheIterator = cache.entrySet().iterator(); 
39.       last = cacheIterator.next(); 
40.       final Y toRemove = last.getValue(); 
41.       currentSize -= getSize(toRemove); 
42.       final T key = last.getKey(); 
43.       cacheIterator.remove(); 
44.       onItemEvicted(key, toRemove); 
45.     } 
46.   } 

这是一个带锁机制的方法，通过对当前容量和最大容量的判断，来抉择是否需要把我们的数据进行一个删除。但是问题依旧存在，initialMaxSize的作用是什么?，我们能够知道的是maxSize是一个用于控制容量大小的值。

get()

1. public synchronized Y get(@NonNull T key) { 
2.     return cache.get(key); 
3. } 

那这就是调用了LinkedHashMap中的数据，但是终究还是没有说出initialMaxSize的作用。

关于initialMaxSize

这里就不买关子了，因为其实就我的视角来看这个initialMaxSize确实是没啥用处的。哈哈哈哈哈!!!但是，又一个地方用到了它。

1. public synchronized void setSizeMultiplier(float multiplier) { 
2.     if (multiplier < 0) { 
3.       throw new IllegalArgumentException("Multiplier must be >= 0"); 
4.     } 
5.     maxSize = Math.round(initialMaxSize * multiplier); 
6.     evict(); 
7.   } 

也就是用于调控我们的最大容量大小，但是我觉得还是没啥用，可是是我太菜了吧，这个方法没有其他调用它的方法，是一个我们直接在使用过程中使用的，可能和数据多次使用的一个保存之类的问题相关联把，场景的话也就类似Glide的图片缓存加载把。也希望知道的读者能给我一个解答。

LinkedHashMap

因为操作方式和HashMap一致就不再复述，就看看他的节点长相。

1. static class LinkedHashMapEntry extends HashMap.Node { 
2.         // 存在前后节点，也就是我们所说的双向链表 
3.         LinkedHashMapEntry before, after; 
4.         LinkedHashMapEntry(int hash, K key, V value, Node next) { 
5.             super(hash, key, value, next); 
6.         } 
7. } 

但是到这里，我又出现了一个问题，为什么我没有看到整个数据的移动?也就是最近使用的数据应该调换到最后开始的位置，他到底实在哪里进行处理的呢?做一个猜想好了，既然是使用了put()才会造成双向链表中数据的变换，那我们就应该是需要进入对LinkedHashMap.put()方法中进行查询。

当然有兴趣探索的读者们，我需要提一个醒，就是这次的调用不可以直接进行对put()进行查询，那样只会调用到一个接口函数，或者是抽象类函数，最适合的方法还是使用我们的断点来进行探索查询。

但是经过一段努力后，不断深度调用探索发现这样的问题，他最后会调用到这样的问题。

1. // Callbacks to allow LinkedHashMap post-actions 
2. void afterNodeAccess(Node p) { } // 把数据移动到最后一位 
3. void afterNodeInsertion(boolean evict) { } 
4. void afterNodeRemoval(Node p) { } 

这是之前我们在了解HashMap是并没有发现几个方法，上面也明确写着为LinkedHashMap保留。哇哦!!那我们的操作肯定实在这些里面了。

1. // --> HashMap源码第656行附近调用到下方方法 
2. // 在putVal()方法内部存在这个出现 
3. afterNodeAccess(e); 
4. // --> LinkedHashMap对其具体实现 
5. // 就是将当前数据直接推到最后一个位置 
6. // 也就是成为了最近刚使用过的数据 
7. void afterNodeAccess(Node e) { // move node to last 
8.         LinkedHashMapEntry last; 
9.         if (accessOrder && (last = tail) != e) { 
10.             LinkedHashMapEntry p = 
11.                 (LinkedHashMapEntry)e, b = p.before, a = p.after; 
12.             p.after = null; 
13.             if (b == null) 
14.                 head = a; 
15.             else 
16.                 b.after = a; 
17.             if (a != null) 
18.                 a.before = b; 
19.             else 
20.                 last = b; 
21.             if (last == null) 
22.                 head = p; 
23.             else { 
24.                 p.before = last; 
25.                 last.after = p; 
26.             } 
27.             tail = p; 
28.             ++modCount; 
29.         } 
30.     } 

好了，自此我们也就清楚了整个链表的变换过程了。

实战：手撸LruCache

这是一个非常紧张刺激的环节了，撸代码前，我们来找找思路好了。

(1)存储容器用什么? 因为LinkedHashMap的思路太过冗长，我们用数组来重新完成整个代码的构建

(2)关键调用方法put()、get()以及put()涉及的已存在变量移位。

哇哦!看来要做的事情也并没有这么多,那我们就先来看看第一次构造出来的框架好了。

1. public class LruCache { 
2.  
3.     private Object objects[]; 
4.     private int maxSize; 
5.     private int currentSize; 
6.  
7.     public LruCache(int size){ 
8.         objects = new Object[size]; 
9.         maxSize = size; 
10.     } 
11.  
12.     /** 
13.      * 插入item 
14.      * @param item 
15.      */ 
16.     public void put(Object item){ 
17.          
18.     } 
19.  
20.     /** 
21.      * 获取item 
22.      * @param item 
23.      */ 
24.     public Object get(Object item){ 
25.         return null; 
26.     } 
27.  
28.     /** 
29.      * 根据下标对应，将后续数组移位 
30.      * @param index 
31.      */ 
32.     public void move(int index){ 
33.          
34.     } 
35. } 

因为只要是数组变换就存在移位，所以移位操作是必不可少的。那我们现在的工作也就是把数据填好了，对应的移位是怎么样的操作的思路了。

1. public class LruCache { 
2.  
3.     public Object objects[]; 
4.     private int maxSize; 
5.     public int currentSize; 
6.  
7.     public LruCache(int size) { 
8.         objects = new Object[size]; 
9.         maxSize = size; 
10.     } 
11.  
12.     /** 
13.      * 插入item 
14.      * 
15.      * @param item 
16.      */ 
17.     public void put(Object item) { 
18.         // 容量未满时分成两种情况 
19.         // 1。 容器内存在 
20.         // 2。 容器内不存在 
21.         int index = search(item); 
22.         if (index == -1) { 
23.             if (currentSize < maxSize) { //容器未满，直接插入 
24.                 objects[currentSize] = item; 
25.                 currentSize++; 
26.             } else { // 容器已满，删去头部插入 
27.                 move(0); 
28.                 objects[currentSize - 1] = item; 
29.             } 
30.         }else { 
31.             move(index); 
32.         } 
33.     } 
34.  
35.     /** 
36.      * 获取item 
37.      * 
38.      * @param item 
39.      */ 
40.     public Object get(Object item) { 
41.         int index = search(item); 
42.         return index == -1 ? null : objects[index]; 
43.     } 
44.  
45.     /** 
46.      * 根据下标对应，将后续数组移位 
47.      * 
48.      * @param index 
49.      */ 
50.     public void move(int index) { 
51.         Object temp = objects[index]; 
52.         // 将后续数组移位 
53.         for (int i = index; i < currentSize - 1; i++) { 
54.             objects[i] = objects[i + 1]; 
55.         } 
56.         objects[currentSize - 1] = temp; 
57.     } 
58.  
59.     /** 
60.      * 搜寻数组中的数组 
61.      * 存在则返回下标 
62.      * 不存在则返回 -1 
63.      * @param item 
64.      * @return 
65.      */ 
66.     private int search(Object item) { 
67.         for (int i = 0; i < currentSize; i++) { 
68.             if (item.equals(objects[i])) return i; 
69.         } 
70.         return -1; 
71.     } 

因为已经真的写的比较详细了，也没什么难度的撸了我的20分钟，希望读者们能够快入入门，下面给出我的一份测试样例，结束这个话题。

总结

想来我们都知道在操作系统中有这样的问题需要思考，具体题型的话就是缺页中断。用一个例题来彻底了解LruCache的算法。

例： 存入内存的数据序列为：(1，2，1，3，2)，内存容量为2。

最近使用	最久未使用	动作
1		1入内存
2	1	2入内存
1	2	1入内存，交换1和2的使用频率
3	1	3入内存，内存不足，排出2
2	3	2入内存，内存不足，排出1

LruCache 主要用于缓存的处理,这里的缓存主要指的是内存缓存和磁盘缓存。

以上就是我的学习成果，如果有什么我没有思考到的地方或是文章内存在错误，欢迎与我分享。

 编程语言（programming language）是一种被标准化的交流技巧，用来向计算机发出指令，定义计算机程序，让程序员能够准确地定义计算机所需要使用的数据，并精确地定义在不同情况下所应当采取的行动的一种计算机语言。 编程语言可以分成机器语言、汇编语言、高级语言三大类。计算机领域已发明了上千不同的编程语言，而且每年仍有新的编程语言诞生。