详解Java实现缓存(LRU,FIFO)

现在软件或者网页的并发量越来越大了，大量请求直接操作数据库会对数据库造成很大的压力，处理大量连接和请求就会需要很长时间，但是实际中百分之80的数据是很少更改的，这样就可以引入缓存来进行读取，减少数据库的压力。

常用的缓存有Redis和memcached，但是有时候一些小场景就可以直接使用Java实现缓存，就可以满足这部分服务的需求。

缓存主要有LRU和FIFO，LRU是Least Recently Used的缩写，即最近最久未使用，FIFO就是先进先出，下面就使用Java来实现这两种缓存。

LRU

LRU缓存的思想

• 固定缓存大小，需要给缓存分配一个固定的大小。
• 每次读取缓存都会改变缓存的使用时间，将缓存的存在时间重新刷新。
• 需要在缓存满了后，将最近最久未使用的缓存删除，再添加最新的缓存。

按照如上思想，可以使用LinkedHashMap来实现LRU缓存。

这是LinkedHashMap的一个构造函数，传入的第三个参数accessOrder为true的时候，就按访问顺序对LinkedHashMap排序，为false的时候就按插入顺序，默认是为false的。

当把accessOrder设置为true后，就可以将最近访问的元素置于最前面，这样就可以满足上述的第二点。

/**
 * Constructs an empty <tt>LinkedHashMap</tt> instance with the
 * specified initial capacity, load factor and ordering mode.
 *
 * @param initialCapacity the initial capacity
 * @param loadFactor   the load factor
 * @param accessOrder   the ordering mode - <tt>true</tt> for
 *     access-order, <tt>false</tt> for insertion-order
 * @throws IllegalArgumentException if the initial capacity is negative
 *     or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity,
           float loadFactor,
           boolean accessOrder) {
  super(initialCapacity, loadFactor);
  this.accessOrder = accessOrder;
}

这是LinkedHashMap中另外一个方法，当返回true的时候，就会remove其中最久的元素，可以通过重写这个方法来控制缓存元素的删除，当缓存满了后，就可以通过返回true删除最久未被使用的元素，达到LRU的要求。这样就可以满足上述第三点要求。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  return false;
}

由于LinkedHashMap是为自动扩容的，当table数组中元素大于Capacity * loadFactor的时候，就会自动进行两倍扩容。但是为了使缓存大小固定，就需要在初始化的时候传入容量大小和负载因子。

 为了使得到达设置缓存大小不会进行自动扩容，需要将初始化的大小进行计算再传入，可以将初始化大小设置为(缓存大小 / loadFactor) + 1，这样就可以在元素数目达到缓存大小时，也不会进行扩容了。这样就解决了上述第一点问题。

通过上面分析，实现下面的代码

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class LRU1<K, V> {
  private final int MAX_CACHE_SIZE;
  private final float DEFAULT_LOAD_FACTORY = 0.75f;

  LinkedHashMap<K, V> map;

  public LRU1(int cacheSize) {
    MAX_CACHE_SIZE = cacheSize;
    int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
    /*
     * 第三个参数设置为true，代表linkedlist按访问顺序排序，可作为LRU缓存
     * 第三个参数设置为false，代表按插入顺序排序，可作为FIFO缓存
     */
    map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, true) {
      @Override
      protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_CACHE_SIZE;
      }
    };
  }

  public synchronized void put(K key, V value) {
    map.put(key, value);
  }

  public synchronized V get(K key) {
    return map.get(key);
  }

  public synchronized void remove(K key) {
    map.remove(key);
  }

  public synchronized Set<Map.Entry<K, V>> getAll() {
    return map.entrySet();
  }

  @Override
  public String toString() {
    StringBuilder stringBuilder = new StringBuilder();
    for (Map.Entry<K, V> entry : map.entrySet()) {
      stringBuilder.append(String.format("%s: %s ", entry.getKey(), entry.getValue()));
    }
    return stringBuilder.toString();
  }

  public static void main(String[] args) {
    LRU1<Integer, Integer> lru1 = new LRU1<>(5);
    lru1.put(1, 1);
    lru1.put(2, 2);
    lru1.put(3, 3);
    System.out.println(lru1);
    lru1.get(1);
    System.out.println(lru1);
    lru1.put(4, 4);
    lru1.put(5, 5);
    lru1.put(6, 6);
    System.out.println(lru1);
  }
}

运行结果：

从运行结果中可以看出，实现了LRU缓存的思想。

接着使用HashMap和链表来实现LRU缓存。

主要的思想和上述基本一致，每次添加元素或者读取元素就将元素放置在链表的头，当缓存满了之后，就可以将尾结点元素删除，这样就实现了LRU缓存。

这种方法中是通过自己编写代码移动结点和删除结点，为了防止缓存大小超过限制，每次进行put的时候都会进行检查，若缓存满了则删除尾部元素。

import java.util.HashMap;

/**
 * 使用cache和链表实现缓存
 */
public class LRU2<K, V> {
  private final int MAX_CACHE_SIZE;
  private Entry<K, V> head;
  private Entry<K, V> tail;

  private HashMap<K, Entry<K, V>> cache;

  public LRU2(int cacheSize) {
    MAX_CACHE_SIZE = cacheSize;
    cache = new HashMap<>();
  }

  public void put(K key, V value) {
    Entry<K, V> entry = getEntry(key);
    if (entry == null) {
      if (cache.size() >= MAX_CACHE_SIZE) {
        cache.remove(tail.key);
        removeTail();
      }
    }
    entry = new Entry<>();
    entry.key = key;
    entry.value = value;
    moveToHead(entry);
    cache.put(key, entry);
  }

  public V get(K key) {
    Entry<K, V> entry = getEntry(key);
    if (entry == null) {
      return null;
    }
    moveToHead(entry);
    return entry.value;
  }

  public void remove(K key) {
    Entry<K, V> entry = getEntry(key);
    if (entry != null) {
      if (entry == head) {
        Entry<K, V> next = head.next;
        head.next = null;
        head = next;
        head.pre = null;
      } else if (entry == tail) {
        Entry<K, V> prev = tail.pre;
        tail.pre = null;
        tail = prev;
        tail.next = null;
      } else {
        entry.pre.next = entry.next;
        entry.next.pre = entry.pre;
      }
      cache.remove(key);
    }
  }

  private void removeTail() {
    if (tail != null) {
      Entry<K, V> prev = tail.pre;
      if (prev == null) {
        head = null;
        tail = null;
      } else {
        tail.pre = null;
        tail = prev;
        tail.next = null;
      }
    }
  }

  private void moveToHead(Entry<K, V> entry) {
    if (entry == head) {
      return;
    }
    if (entry.pre != null) {
      entry.pre.next = entry.next;
    }
    if (entry.next != null) {
      entry.next.pre = entry.pre;
    }
    if (entry == tail) {
      Entry<K, V> prev = entry.pre;
      if (prev != null) {
        tail.pre = null;
        tail = prev;
        tail.next = null;
      }
    }

    if (head == null || tail == null) {
      head = tail = entry;
      return;
    }

    entry.next = head;
    head.pre = entry;
    entry.pre = null;
    head = entry;
  }

  private Entry<K, V> getEntry(K key) {
    return cache.get(key);
  }

  private static class Entry<K, V> {
    Entry<K, V> pre;
    Entry<K, V> next;
    K key;
    V value;
  }

  @Override
  public String toString() {
    StringBuilder stringBuilder = new StringBuilder();
    Entry<K, V> entry = head;
    while (entry != null) {
      stringBuilder.append(String.format("%s:%s ", entry.key, entry.value));
      entry = entry.next;
    }
    return stringBuilder.toString();
  }

  public static void main(String[] args) {
    LRU2<Integer, Integer> lru2 = new LRU2<>(5);
    lru2.put(1, 1);
    System.out.println(lru2);
    lru2.put(2, 2);
    System.out.println(lru2);
    lru2.put(3, 3);
    System.out.println(lru2);
    lru2.get(1);
    System.out.println(lru2);
    lru2.put(4, 4);
    lru2.put(5, 5);
    lru2.put(6, 6);
    System.out.println(lru2);
  }
}

运行结果：

FIFO

FIFO就是先进先出，可以使用LinkedHashMap进行实现。

当第三个参数传入为false或者是默认的时候，就可以实现按插入顺序排序，就可以实现FIFO缓存了。

/**
 * Constructs an empty <tt>LinkedHashMap</tt> instance with the
 * specified initial capacity, load factor and ordering mode.
 *
 * @param initialCapacity the initial capacity
 * @param loadFactor   the load factor
 * @param accessOrder   the ordering mode - <tt>true</tt> for
 *     access-order, <tt>false</tt> for insertion-order
 * @throws IllegalArgumentException if the initial capacity is negative
 *     or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity,
           float loadFactor,
           boolean accessOrder) {
  super(initialCapacity, loadFactor);
  this.accessOrder = accessOrder;
}

实现代码跟上述使用LinkedHashMap实现LRU的代码基本一致，主要就是构造函数的传值有些不同。

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class LRU1<K, V> {
  private final int MAX_CACHE_SIZE;
  private final float DEFAULT_LOAD_FACTORY = 0.75f;

  LinkedHashMap<K, V> map;

  public LRU1(int cacheSize) {
    MAX_CACHE_SIZE = cacheSize;
    int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
    /*
     * 第三个参数设置为true，代表linkedlist按访问顺序排序，可作为LRU缓存
     * 第三个参数设置为false，代表按插入顺序排序，可作为FIFO缓存
     */
    map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, false) {
      @Override
      protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_CACHE_SIZE;
      }
    };
  }

  public synchronized void put(K key, V value) {
    map.put(key, value);
  }

  public synchronized V get(K key) {
    return map.get(key);
  }

  public synchronized void remove(K key) {
    map.remove(key);
  }

  public synchronized Set<Map.Entry<K, V>> getAll() {
    return map.entrySet();
  }

  @Override
  public String toString() {
    StringBuilder stringBuilder = new StringBuilder();
    for (Map.Entry<K, V> entry : map.entrySet()) {
      stringBuilder.append(String.format("%s: %s ", entry.getKey(), entry.getValue()));
    }
    return stringBuilder.toString();
  }

  public static void main(String[] args) {
    LRU1<Integer, Integer> lru1 = new LRU1<>(5);
    lru1.put(1, 1);
    lru1.put(2, 2);
    lru1.put(3, 3);
    System.out.println(lru1);
    lru1.get(1);
    System.out.println(lru1);
    lru1.put(4, 4);
    lru1.put(5, 5);
    lru1.put(6, 6);
    System.out.println(lru1);
  }
}

运行结果：

以上就是使用Java实现这两种缓存的方式，从中可以看出，LinkedHashMap实现缓存较为容易，因为底层函数对此已经有了支持，自己编写链表实现LRU缓存也是借鉴了LinkedHashMap中实现的思想。在Java中不只是这两种数据结构可以实现缓存，比如ConcurrentHashMap、WeakHashMap在某些场景下也是可以作为缓存的，到底用哪一种数据结构主要是看场景再进行选择，但是很多思想都是可以通用的。

# lru  # java实现  # fifo  # java实现缓存  # java实现LRU缓存淘汰算法的方法  # Java 手写LRU缓存淘汰算法  # JAVA实现LRU算法的参考示例  # 详解Java实现LRU缓存  # java LRU(Least Recently Used )详解及实例代码  # Java实现常用缓存淘汰算法:FIFO、LRU、LFU  # 就可以  # 第三个  # 设置为  # 满了  # 就会  # 就可  # 这是  # 最久  # 这两种  # 来实现  # 链表  # 数据结构  # 可以使用  # 可以看出  # 以满足  # 都是  # 实现了  # 这部  # 可以通过  # 会对 

相关文章： 建站之星展会模版如何一键下载生成？  淘宝制作网站有哪些,淘宝网官网主页？  免费视频制作网站,更新又快又好的免费电影网站？  企业微网站怎么做,公司网站和公众号有什么区别？  如何快速上传自定义模板至建站之星？  官网建站费用明细查询_企业建站套餐价格及收费标准指南  如何在阿里云通过域名搭建网站？  香港服务器网站测试全流程：性能评估、SEO加载与移动适配优化  建站之星安装后如何配置SEO及设计样式？  如何用手机制作网站和网页,手机移动端的网站能制作成中英双语的吗？  如何破解联通资金短缺导致的基站建设难题？  建站之星导航菜单设置与功能模块配置全攻略  香港服务器网站生成指南：免费资源整合与高速稳定配置方案  手机钓鱼网站怎么制作视频,怎样拦截钓鱼网站。怎么办？  制作网站的过程怎么写,用凡科建站如何制作自己的网站？  非常酷的网站设计制作软件,酷培ai教育官方网站？  制作公司内部网站有哪些,内网如何建网站？  上海网站制作网站建设公司,建筑电工证网上查询系统入口？  品牌网站制作公司有哪些,买正品品牌一般去哪个网站买？  如何在云虚拟主机上快速搭建个人网站？  建站之星免费模板：自助建站系统与智能响应式一键生成  我的世界制作壁纸网站下载,手机怎么换我的世界壁纸？  建站之星会员如何解锁更多建站功能？  微信网站制作公司有哪些,民生银行办理公司开户怎么在微信网页上查询进度？  怎么制作网站设计模板图片,有电商商品详情页面的免费模板素材网站推荐吗？  建站主机选哪家性价比最高？  齐河建站公司：营销型网站建设与SEO优化双核驱动策略  简单实现Android验证码  在线制作视频的网站有哪些,电脑如何制作视频短片？  制作网站公司那家好,网络公司是做什么的？  Avalonia如何实现跨窗口通信 Avalonia窗口间数据传递  临沂网站制作公司有哪些,临沂第四中学官网？  如何选择可靠的免备案建站服务器？  建站之星如何助力企业快速打造五合一网站？  如何用PHP快速搭建CMS系统？  如何快速搭建高效WAP手机网站？  小捣蛋自助建站系统：数据分析与安全设置双核驱动网站优化  网站视频怎么制作,哪个网站可以免费收看好莱坞经典大片？  建站上传速度慢？如何优化加速网站加载效率？  网站制作服务平台,有什么网站可以发布本地服务信息？  建站之星如何一键生成手机站？  如何在云服务器上快速搭建个人网站？  如何在宝塔面板中修改默认建站目录？  建站之星手机一键生成：多端自适应+小程序开发快速建站指南  制作营销网站公司,淘特是干什么用的？  如何在IIS服务器上快速部署高效网站？  ,网站推广常用方法？  h5网站制作工具有哪些,h5页面制作工具有哪些？  测试制作网站有哪些,测试性取向的权威测试或者网站？  如何用好域名打造高点击率的自主建站？