简单的 LRU 缓存（带过期）

引言

缓存是一种非常有用的概念，可以提高性能。Java 中有许多商业和开源缓存包可用。这些包通常涉及安装 jar 文件、编辑配置文件以及与框架（JNDI、日志、JDBC）集成等。这很好，但有时我们只需要一个快速而简单的解决方案——一种只需要几个类，我们可以直接插入到我们自己的代码中的解决方案；你可以直接从网页上复制粘贴的代码。这就是我们在这里提供的。

首先，我们定义一个缓存接口，以便以后，如果我们改变主意，可以使用不同的缓存策略或连接到更复杂的缓存包。

public interface Cache<K extends Comparable, V> {
   V get(K obj);
   void put(K key, V obj);
   void put(K key, V obj, long validTime);
   void remove(K key);
   Pair[] getAll();
   int size();
}

这个缓存接口使我们能够为缓存的对象分配一个过期时间。这对于我们知道缓存的数据会随着时间变化，但人们始终看到绝对最新的数据并非至关重要，并且可以接受一些延迟的情况非常有用。例如，如果我们从数据库中检索内容以在网页中显示，通常没有必要让用户每次都看到绝对最新的数据。如果我们每秒收到 100 个查询，即使我们只缓存一秒钟，我们也可以减少 100 个查询的数量。通常缓存 5 到 15 分钟就足够了。我们实现了最近最少使用 (LRU) 算法进行缓存，该算法首先丢弃最近最少使用的数据项。这需要跟踪何时使用。

我们只有一个 public 支持对象，允许我们从缓存中检索所有缓存的对象。

public class Pair<K extends Comparable, V> implements Comparable<Pair> {
   public Pair(K key1, V value1) {
      this.key = key1;
      this.value = value1;
   }
   public K key;
   public V value;
   public boolean equals(Object obj) {
      if(obj instanceof Pair) {
         Pair p = (Pair)obj;
         return key.equals(p.key)&&value.equals(p.value);
      }
      return false;
   }
   @SuppressWarnings("unchecked")
   public int compareTo(Pair p) {
      int v = key.compareTo(p.key);
      if(v==0) {
         if(p.value instanceof Comparable) {
            return ((Comparable)value).compareTo(p.value);
         }
      }
      return v;
   }
   @Override
   public int hashCode() {
      return key.hashCode()^value.hashCode();
   }
   @Override
   public String toString() {
      return key+": "+value;
   }
}

最后，缓存实现的的代码是

public class LRUCache<K extends Comparable, V> implements Cache<K, V>,
      Serializable {
   private static final long serialVersionUID = 3674312987828041877L;
   Map<K, Item> m_map = Collections.synchronizedMap(new HashMap<K, Item>());
   Item m_start = new Item();
   Item m_end = new Item();
   int m_maxSize;
   Object m_listLock = new Object();
   static class Item {
      public Item(Comparable k, Object v, long e) {
         key = k;
         value = v;
         expires = e;
      }
      public Item() {}
      public Comparable key;
      public Object value;
      public long expires;
      public Item previous;
      public Item next;
   }
   void removeItem(Item item) {
      synchronized(m_listLock) {
         item.previous.next = item.next;
         item.next.previous = item.previous;
      }
   }
   void insertHead(Item item) {
      synchronized(m_listLock) {
         item.previous = m_start;
         item.next = m_start.next;
         m_start.next.previous = item;
         m_start.next = item;
      }
   }
   void moveToHead(Item item) {
      synchronized(m_listLock) {
         item.previous.next = item.next;
         item.next.previous = item.previous;
         item.previous = m_start;
         item.next = m_start.next;
         m_start.next.previous = item;
         m_start.next = item;
      }
   }
   public LRUCache(int maxObjects) {
      m_maxSize = maxObjects;
      m_start.next = m_end;
      m_end.previous = m_start;
   }
   @SuppressWarnings("unchecked")
   public Pair[] getAll() {
      Pair p[] = new Pair[m_maxSize];
      int count = 0;
      synchronized(m_listLock) {
         Item cur = m_start.next;
         while(cur!=m_end) {
            p[count] = new Pair(cur.key, cur.value);
            ++count;
            cur = cur.next;
         }
      }
      Pair np[] = new Pair[count];
      System.arraycopy(p, 0, np, 0, count);
      return np;
   }
   @SuppressWarnings("unchecked")
   public V get(K key) {
      Item cur = m_map.get(key);
      if(cur==null) {
         return null;
      }
      if(System.currentTimeMillis()>cur.expires) {
         m_map.remove(cur.key);
         removeItem(cur);
         return null;
      }
      if(cur!=m_start.next) {
         moveToHead(cur);
      }
      return (V)cur.value;
   }
   public void put(K key, V obj) {
      put(key, obj, -1);
   }
   public void put(K key, V value, long validTime) {
      Item cur = m_map.get(key);
      if(cur!=null) {
         cur.value = value;
         if(validTime>0) {
            cur.expires = System.currentTimeMillis()+validTime;
         }
         else {
            cur.expires = Long.MAX_VALUE;
         }
         moveToHead(cur);
         return;
      }
      if(m_map.size()>=m_maxSize) {
         cur = m_end.previous;
         m_map.remove(cur.key);
         removeItem(cur);
      }
      long expires=0;
      if(validTime>0) {
         expires = System.currentTimeMillis()+validTime;
      }
      else {
         expires = Long.MAX_VALUE;
      }
      Item item = new Item(key, value, expires);
      insertHead(item);
      m_map.put(key, item);
   }
   public void remove(K key) {
      Item cur = m_map.get(key);
      if(cur==null) {
         return;
      }
      m_map.remove(key);
      removeItem(cur);
   }
   public int size() {
      return m_map.size();
   }
}

缓存的工作原理基本上就像一个映射，只是你可以传递一个可选的过期时间。创建、存储、使用——简单。

历史

• 2005 年 10 月 30 日：初始发布