详解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  # 就可以  # 第三个  # 设置为  # 满了  # 就会  # 就可  # 这是  # 最久  # 这两种  # 来实现  # 链表  # 数据结构  # 可以使用  # 可以看出  # 以满足  # 都是  # 实现了  # 这部  # 可以通过  # 会对 

相关文章： 大连 网站制作,大连天途有线官网？  如何制作公司的网站链接,公司想做一个网站，一般需要花多少钱？  图册素材网站设计制作软件,图册的导出方式有几种？  娃派WAP自助建站：免费模板+移动优化，快速打造专业网站  C++时间戳转换成日期时间的步骤和示例代码  建站之星客服服务时间及联系方式如何？  建站三合一如何选？哪家性价比更高？  七夕网站制作视频,七夕大促活动怎么报名？  如何在云主机快速搭建网站站点？  制作网站的网址是什么,请问后缀为.com和.com.cn还有.cn的这三种网站是分别是什么类型的网站？  如何快速搭建支持数据库操作的智能建站平台？  Bpmn 2.0的XML文件怎么画流程图  *服务器网站为何频现安全漏洞？  C++中引用和指针有什么区别？（代码说明）  如何选择香港主机高效搭建外贸独立站？  大型企业网站制作流程,做网站需要注册公司吗？  Avalonia如何实现跨窗口通信 Avalonia窗口间数据传递  如何选择最佳自助建站系统？快速指南解析优劣  如何在七牛云存储上搭建网站并设置自定义域名？  北京制作网站的公司排名,北京三快科技有限公司是做什么？北京三快科技？  如何快速搭建高效WAP手机网站吸引移动用户？  建站上传速度慢？如何优化加速网站加载效率？  如何在Golang中实现微服务服务拆分_Golang微服务拆分与接口管理方法  制作网站公司那家好,网络公司是做什么的？  如何选择靠谱的建站公司加盟品牌？  如何在阿里云域名上完成建站全流程？  电商网站制作多少钱一个,电子商务公司的网站制作费用计入什么科目？  如何彻底删除建站之星生成的Banner？  深圳网站制作平台,深圳市做网站好的公司有哪些？  南京网站制作费用,南京远驱官方网站？  大连网站制作公司哪家好一点,大连买房网站哪个好？  建站主机功能解析：服务器选择与快速搭建指南  c# 在高并发下使用反射发射（Reflection.Emit）的性能  网站海报制作教学视频教程,有什么免费的高清可商用图片网站，用于海报设计？  如何快速查询网址的建站时间与历史轨迹？  网站制作大概要多少钱一个,做一个平台网站大概多少钱？  高性能网站服务器部署指南：稳定运行与安全配置优化方案  如何通过IIS搭建网站并配置访问权限？  专业网站制作服务公司,有哪些网站可以免费发布招聘信息？  高防服务器租用首荐平台，企业级优惠套餐快速部署  如何在服务器上配置二级域名建站？  建站之星如何实现网站加密操作？  nginx修改上传文件大小限制的方法  正规网站制作公司有哪些,目前国内哪家网页网站制作设计公司比较专业靠谱？口碑好？  建站之星安全性能如何？防护体系能否抵御黑客入侵？  如何通过VPS建站实现广告与增值服务盈利？  网站制作和推广的区别,想自己建立一个网站做推广，有什么快捷方法马上做好一个网站？  新网站制作渠道有哪些,跪求一个无线渠道比较强的小说网站，我要发表小说？  已有域名如何免费搭建网站？  建站VPS配置与SEO优化指南：关键词排名提升策略