自己实现本地缓存

发表于 更新于 分类于 ， ，

前言

在扩展框架中的缓存组件相关功能时浏览了本地缓存的实现，其核心是LUR算法，记录下LUR的相关内容加深记忆和理解

环境

  • windows 10
  • jdk7

LUR

LRU全称是Least Recently Used，即最近最久未使用的意思。 LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

思路分析

对cache的基本操作有：插入(insert)、替换(replace)、查找(lookup)
为了能够快速删除最久没有访问的数据项和插入最新的数据项，我们使用双向链表连接Cache中的数据项，并且保证链表维持数据项从最近访问到最旧访问的顺序。

  • 插入：当Cache未满时，新的数据项只需插到双链表头部即可。时间复杂度为O(1).
  • 替换：当Cache已满时，将新的数据项插到双链表头部，并删除双链表的尾结点即可。时间复杂度为O(1).
  • 查找：每次数据项被查询到时，都将此数据项移动到链表头部。

经过分析，我们知道使用双向链表可以保证插入和替换的时间复杂度是O(1)，但查询的时间复杂度是O(n)，因为需要对双链表进行遍历。为了让查找效率也达到O(1)，很自然的会想到使用 hash table 。

代码实现

从上述分析可知，我们需要使用两种数据结构：

  1. 双向链表(Doubly Linked List)
  2. 哈希表(Hash Table)

Java中的LinkedHashMap正好满足这两种数据结构，直接用LinkedHashMap来实现(框架代码就是基于LinkedHashMap实现的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private static final long serialVersionUID = -1456882507664137630L;

    //缓存的最大容量
    private final int MAX_CACHE_SIZE;

    public LRUCache(int cacheSize) {
        // true:按访问排序
        // 初始值必须是2 的N次方，最大容量2 的30次方
        // 初始值16
        super(1 << 4, 0.75F, true);
        MAX_CACHE_SIZE = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        return size() > MAX_CACHE_SIZE;
    }

}

核心实现只需要继承LinkedHashMap，扩展它的removeEldestEntry方法即可，在多线程环境使用时使用 Collections.synchronizedMap()方法实现线程安全操作。框架中的细节代码就很多了。

简单测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void main(String[] args) {
    LRUCache<Object, Object> cache = new LRUCache<Object, Object>(8);
    cache.put("0", "0");
    cache.put("1", "1");
    cache.put("2", "2");
    cache.put("3", "3");
    cache.put("4", "4");
    cache.put("5", "5");
    cache.put("6", "6");
    cache.put("7", "7");

    cache.get("6");
    cache.get("5");
    cache.put("8", "8");

    for (Entry<Object, Object> entry : cache.entrySet()) {
        System.out.println(entry.getKey() + ":" + entry.getValue());
    }

}

输出结果：

1
2
3
4
5
6
7
8
1:1
2:2
3:3
4:4
7:7
6:6
5:5
8:8

观察结果当超出最大容量自动删除了最久未使用的数据，访问过的数据排到了链表前端，符合预期

结语

了解原理后不管是解决问题还是重复造轮子都会得心应手。但不推荐重复造轮子，google guava cache 就是基于LUR算法实现的一个基础类库。

参考资料

1.设计并实现一个LRU Cache