来聊聊缓存吧

今天咱们来一起聊聊缓存这个话题吧。

缓存是什么？

• 存储使用频繁的数据的临时地方
• 因为读取原始数据代价太大了，缓存起来可以取得快些

术语

• 命中： 一个条目通过一个标记在缓存中被找到
• Cache Miss： 如果还有空间， 那么没命中的条目会被存储到缓存中来； 如果没有空间了，又没命中， 则会按照某种策略，把缓存中的旧对象踢出，而把新对象加入缓存池
• 存储成本： 把数据放入缓存的时间、空间成本

缓存算法

前文提到的策略，也可以称之为替代策略， 既缓存算法。常用的缓存算法有：LRU, LFU, FIFO, Random Cache, 2Q, ARC, MRU等等。本文主要来介绍FIFO，LRU和LFU这三种。

其中LRU和LFU在LeetCode上可以找到题目：

• LRU Cache

• LFU Cache

FIFO Cache:

在讲LRU和LFU之前我们先来看一下FIFO算法，这是最简单的缓存算法，可以帮助我们对后续内容的理解。

FIFO大家都知道就是First In First Out，先进先出。

• 核心原则： 最新进入到缓存中的数据应最早被淘汰。

• FIFO Cache应支持的操作：

如cache中存在该key，则返回其对应的value值，否则返回-1

如cache中存在该key，则update其value值，如不存在则将其插入，若cache已满，则淘汰最早进入cache的key后再插入新key

• 实现思路： 利用双向链表保存数据，当来了新数据之后就添加到链表末尾， 如果Cache已满，则把链表头删除，然后再把数据添加到链表末尾。访问数据的时候，如果Cache中存在，则返回其value值，否则返回-1.为了提高访问效率，可以利用hashmap保存每个key在链表中对应的位置。

• FIFO代码, 请点击前面的链接。链表的结构如下图所示：

    null <==> head <==> node <==> tail <==> null
  

  其中head和tail是两个key和value都为0的dummy node，每次添加删除都是在head的后面和tail的前面

LRU Cache (Least Recently Used) 最久没被访问算法：

• 核心思想（设计原则）： 如果一个数据在最近一段时间没有被访问，那么在将来它被访问的可能性也很小。

• 实现思路： 利用链表和HashMap

插入数据时，如果数据项在链表中存在，则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部（head的后面）；若缓存满了，则删除链表最后一个节点（tail前面的）即可。访问的时候，如果数据项在链表中存在，则将其移动到头部，并返回其value；否则返回-1.

• LRU Cache应支持的操作：

如果key在HashMap中存在，则将对应的节点放在表头，并返回其value，如果不存在则返回-1.

如果key存在于HashMap中，则先重置对应的value值，然后获取当前节点，将其删除，并移动到表头。否则，将其插入到表头。

• LRU代码, 请点击前面的链接。

这里有一个小技巧，就是我们可以把addToHead()和deleteNode()两个方法提前写出来。因为这两个方法在很多地方可以被复用。

LFU Cache (Least Frequently Used) 最近最少使用算法：

• 核心思想：如果一个数据在最近一段时间内被使用的次数很少，那么在将来一段时间内它被使用的可能性也很小。

• 支持的操作：

如果cache中存在key，则返回相应的value值，否则返回-1

如果cache中存在该key，则重置value值，如果不存在则将该key插入到cache中，若cache已满，则淘汰访问最少的数据。

• 思路：

（1）用小顶堆（PriorityQueue）+HashMap

（2）用数组存储数据项， 用hashmap存储每个数据项在数组中的位置， 为每个数据项设置访问频次，如果命中，频次自增，cache满时用新数据替换频次最低的数据项

• LFU代码，请点击前面链接。该代码只实现了思路（1），这个思路时间效率并不是最优的，因为PriorityQueue的插入复杂度是O(log(n))，其实是有O(n)复杂度的方法的。但是这个思路最容易理解。