详解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在某些场景下也是可以作为缓存的，到底用哪一种数据结构主要是看场景再进行选择，但是很多思想都是可以通用的。