微信号:javams

介绍:Java面试指南;最全最专业的面试题

LRU缓存就像你装破鞋的鞋柜,附实现攻略

2016-04-07 23:05 it面试宝典

更多请关注 >>http://java.jr-jr.com

  1. 1. 问题

  2. 2. 概念

  3. 3. 实现

  4. 4. 注意点

问题

今天我们讲一下怎么实现一个简单的最近最少使用(LRU)的缓存。

概念

LRU是Least Recently Used 的缩写,意为“最近最少使用”。
LRU缓存简单的说就是缓存一定量的数据,当超过设定的阈值时就把一些过期的数据删除掉。
举个生活中的例子,你有一堆鞋子,肯定是最新买的最喜欢穿的放在身边,鞋柜满了的话,如果你不是壕,扔鞋子也会先扔破鞋。

如图,把格子想想成你的鞋柜。一个格子只能放一双鞋子哦。

  • 新数据插入到链表头部;(新鞋子放在最外边)

  • 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;(刚穿过的鞋子放在最外面)

  • 当链表满的时候,将链表尾部的数据丢弃。(鞋柜满了,就需要忍痛扔破鞋)


当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。

实现

Java里面实现LRU缓存通常有多种选择,一种是使用LinkedHashMap,一种是自己设计数据结构,使用链表+HashMap,灵活度更高的可以自定义使用方式。
搞Java的同学真是幸福,因为LinkedHashMap就是一个天生的LRU。

先来看一下LinkedHashMap的构造方法。


public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder)
{

super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}



  • 注意accessOrder这个参数,为true使用访问顺序排序,false使用插入顺序排序。使用访问顺序排序,就是LRU。

  • 当需要添加元素时,会调用removeEldestEntry方法,这里就是实现LRU元素过期机制的地方,默认的情况下removeEldestEntry方法只返回false表示元素永远不过期。

根据以上介绍,可以使用继承方式实现一个最简单的LRU.只需要覆盖removeEldestEntry方法。


public static class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
       private static final int  LRU_MAX_CAPACITY = 1024;
       public LRULinkedHashMap(int initialCapacity, float loadFactor) {
           super(initialCapacity, loadFactor, true);
       }
       /**
        * @see java.util.LinkedHashMap#removeEldestEntry(java.util.Map.Entry)
        */

       @Override
       protected boolean removeEldestEntry(Entry<K, V> eldest) {
           if(size() > LRU_MAX_CAPACITY) {
               return true;
           }
           return false;
       }
   }



注意点

使用LRU要注意以下几点:

  • 缓存的数据是否真正有热点数据

  • 缓存的大小一定要限制,否则会有内存撑爆的危险

  • 老生常谈,高并发下一定要注意LRU操作的同步



版权声明(by lycying@gmail.com):

复制文章的时候,把这一段也复制上吧。这里是Java面试指南,最全最前沿的面试题。大部分信息来自网络和书籍,整理加工而成,也有不少部分是作者自己的观点,一字一字打的,总之,可随意转载。要是能保留链接,感激不尽。如果你不希望被转载的文章不幸出现在这里,请留言告诉我,我换种说法 :)

扫描下面的二维码,加入微信公众号,得到最新的资料:


 
it面试宝典 更多文章 设计模式(Design Pattern) JAVA-CAS简介以及ABA问题 调度系统,Crontab的格式 java的long,天生的陷阱专家 作为高级Java,你应该了解的Linux知识
猜您喜欢 为什么人人都讨厌她,但她偏偏还是这么红? 【干货下载】国内最全面App渠道(Android版完整版) 母亲教我的道理 比特币P2P网络简介(上) 安全从业者需要学会自我驱动