面试题：手写LRU(今日头条面试题) 面试题：手撕LFU，要求get和put都为O(1)
一、Guava Cache适用场景 1、你愿意消耗一部分内存来提升速度； 2、你已经预料某些值会被多次调用； 3、缓存数据不会超过内存总量； Guava Cache是一个全内存的本地缓存实现，它提供了线程安全的实现机制。整体上来说Guava cache 是本地缓存的不二之选，简单易用，性能好。 二、Guava Cache有以下两种创建方式 Guava提供两种不同的方法来加载数据： CacheLoader：在build cache的时候定义一个CacheLoader来获取数据，适用的情况：有固定的方式可以根据key来加载或计算value的值，比如从数据库中获取数据 Callable：在get的时候传入一个Callable对象，适用的情况：如果从缓存中获取不到数据，则另外计算一个出来，并把计算结果加入到缓存中 本项目采用的是第一种方式：
public class TokenCache { private static Logger logger = LoggerFactory.getLogger(TokenCache.class); public static final String TOKEN_PREFIX = "token_"; //生成本地缓存，初始化为1000，最大为10000，当超过10000时就会使用LRU算法（最小使用算法）进行清除，有效期是12小时 private static LoadingCache<String,String> localCache = CacheBuilder.newBuilder().initialCapacity(1000).maximumSize(10000).expireAfterAccess(12, TimeUnit.HOURS) //缓存有效期12小时 .build(new CacheLoader<String, String>() { //默认的数据加载实现,当调用get取值的时候,如果key没有对应的值,就调用这个方法进行加载. @Override public String load(String s) throws Exception { return "null"; } }); public static void setKey(String key,String value){ localCache.put(key,value); } public static String getKey(String key){ String value = null; try { value = localCache.get(key); if("null".equals(value)) return null; return value; }catch (Exception e){ logger.error("localCache get error",e); } return null; } }三、缓存回收方式 1、基于容量的回收（size-based eviction），有两种方式，接近最大的size或weight时回收： 基于maximumSize(long)：一个数据项占用一个size单位，适用于value是固定大小的情况 基于maximumWeight(long)：对不同的数据项计算weight，适用于value不定大小的情况，比如value为Map类型时，可以把map.size()作为weight 回收算法采用的是LRU算法。 2、定时回收（Timed Eviction）： expireAfterAccess(long, TimeUnit)：缓存项在给定时间内没有被读/写，则回收。 expireAfterWrite(long, TimeUnit)：缓存项在给定时间内没有被写访问（创建或覆盖），则回收。 3、基于引用的回收（Reference-based Eviction），通过使用弱引用的键或值、或软引用的值，把缓存设置为允许垃圾回收器回收： CacheBuilder.weakKeys()：使用弱引用存储键。当键没有其它（强或软）引用时，缓存项可以被GC回收 CacheBuilder.weakValues()：使用弱引用存储值。当值没有其它（强或软）引用时，缓存项可以被GC回收 CacheBuilder.softValues()：使用软引用存储值。软引用只有在响应内存需要时，才按照全局最近最少使用的顺序回收。影响性能，不推荐使用。 4、显式清除（invalidate） 个别清除：Cache.invalidate(key) 批量清除：Cache.invalidateAll(keys) 清除所有缓存项：Cache.invalidateAll() 四、什么时候发生缓存清理： 也许这个问题有点奇怪，如果设置的存活时间为一分钟，难道不是一分钟后这个key就会立即清除掉吗？我们来分析一下如果要实现这个功能，那Cache中就必须存在线程来进行周期性地检查、清除等工作，很多cache如redis、ehcache都是这样实现的。 但在GuavaCache中，并不存在任何线程！它实现机制是在写操作时顺带做少量的维护工作（如清除），偶尔在读操作时做（如果写操作实在太少的话），也就是说在使用的是调用线程，参考如下示例： 这在GuavaCache被称为“延迟删除”，即删除总是发生得比较“晚”，这也是GuavaCache不同于其他Cache的地方！这种实现方式的问题：缓存会可能会存活比较长的时间，一直占用着内存。如果使用了复杂的清除策略如基于容量的清除，还可能会占用着线程而导致响应时间变长。但优点也是显而易见的，没有启动线程，不管是实现，还是使用起来都让人觉得简单（轻量）。 如果你还是希望尽可能的降低延迟，可以创建自己的维护线程，以固定的时间间隔调用Cache.cleanUp()，ScheduledExecutorService可以帮助你很好地实现这样的定时调度。不过这种方式依然没办法百分百的确定一定是自己的维护线程“命中”了维护的工作。 总结： 请一定要记住GuavaCache的实现代码中没有启动任何线程！！Cache中的所有维护操作，包括清除缓存、写入缓存等，都是通过调用线程来操作的。这在需要低延迟服务场景中使用时尤其需要关注，可能会在某个调用的响应时间突然变大。 GuavaCache毕竟是一款面向本地缓存的，轻量级的Cache，适合缓存少量数据。如果你想缓存上千万数据，可以为每个key设置不同的存活时间，并且高性能，那并不适合使用GuavaCache。 五、缓存失效策略 当缓存需要被清理时（比如空间占用已经接近临界值了），需要使用某种淘汰算法来决定清理掉哪些数据。常用的淘汰算法有下面几种： FIFO：First In First Out，先进先出。判断被存储的时间，离目前最远的数据优先被淘汰。 LRU：Least Recently Used，最近最少使用。判断最近被使用的时间，目前最远的数据优先被淘汰。 LFU：Least Frequently Used，最不经常使用。在一段时间内，数据被使用次数最少的，优先被淘汰。 FIFO FIFO按照“先进先出（First In，First Out）”的原理淘汰数据，正好符合队列的特性，数据结构上使用队列Queue来实现。 1、新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动； 2、淘汰FIFO队列头部的数据； LRU 算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。 最常见的实现是使用一个链表保存缓存数据，详细算法实现如下： 1、新数据插入到链表头部； 2、每当缓存命中（即缓存数据被访问），则将数据移到链表头部； 3、当链表满的时候，将链表尾部的数据丢弃。 LFU 算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。 LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。 具体实现如下： 1、新加入数据插入到队列尾部（因为引用计数为1）； 2、队列中的数据被访问后，引用计数增加，队列重新排序； 3、当需要淘汰数据时，将已经排序的列表最后的数据块删除。 六、LRU和LFU实现 利用LinkedHashMap。 用这个类有两大好处：一是它本身已经实现了按照访问顺序的存储，也就是说，最近读取的会放在最前面，最最不常读取的会放在最后（当然，它也可以实现按照插入顺序存储）。 第二，LinkedHashMap本身有一个方法用于判断是否需要移除最不常读取的数，但是，原始方法默认不需要移除（这是，LinkedHashMap相当于一个linkedlist），所以，我们需要override这样一个方法，使得当缓存里存放的数据个数超过规定个数后，就把最不常用的移除掉。
import java.util.LinkedHashMap; import java.util.Map; public class LRUCache<K, V> extends LinkedHashMap<K, V> { private static final long serialVersionUID = 1L; private int cacheSize; //缓存大小 public LRUCache(int cacheSize) { super(10, 0.75f, true); //第三个参数true是关键 this.cacheSize = cacheSize; } //缓存是否已满 @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { boolean r = size() > cacheSize; if(r) System.out.println("清除缓存key："+eldest.getKey()); return r; } //测试 public static void main(String[] args) { LRUCache<String, String> cache = new LRUCache<String, String>(5); cache.put("1", "1"); cache.put("2", "2"); cache.put("3", "3"); cache.put("4", "4"); cache.put("5", "5"); System.out.println("初始化："); System.out.println(cache.keySet()); System.out.println("访问3："); cache.get("3"); System.out.println(cache.keySet()); System.out.println("访问2："); cache.get("2"); System.out.println(cache.keySet()); System.out.println("增加数据6,7："); cache.put("6", "6"); cache.put("7", "7"); System.out.println(cache.keySet()); } } //运行结果 初始化： [1, 2, 3, 4, 5] 访问3： [1, 2, 4, 5, 3] 访问2： [1, 4, 5, 3, 2] 增加数据6,7： 清除缓存key：1 清除缓存key：4 [5, 3, 2, 6, 7]手撕LFU，要求get和put都为O(1) LeetCode算法题解：LFU Cache O(1)
Java面试的完整博客目录如下：Java笔试面试目录
转载请标明出处，原文地址：https://blog.csdn.net/weixin_41835916 如果觉得本文对您有帮助，请点击顶支持一下，您的支持是我写作最大的动力，谢谢。
