LRU算法的实现（Java版）

前文写到Go和Python实现LRU算法及LRU算法的相关讨论，本文讲述使用Java实现LRU算法。Java自带的集合框架非常强大，实现LRU算法可以直接使用LinkedHashMap集合框架。关于LRU算法的原理见Go实现LRU算法 ，Python实现的LRU算法见LRU算法的实现（Python版）。

实现

首先我们谈谈LinkedHashMap。它的一个构造函数如下：

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

第一第二个参数好明白，第三个参数accessOrder，如果传入false，那么它就是一个单纯的FIFO队列，映射顺序就是插入顺序。

import java.util.LinkedHashMap;
import java.util.Map.Entry;

public class LRUCache extends LinkedHashMap {
    private static final long serialVersionUID = 1L;
    private final int capacity;
    private long accessCount = 0;
    private long hitCount = 0;

    public LRUCache(int capacity) {
        super(capacity+1, 1.1f, true);
        this.capacity = capacity;
    }

    public String get(String key) {
        accessCount++;
        if (super.containsKey(key)) {
            hitCount++;
        }
        String value = (String)super.get(key);
        return value;
    }
      
      public boolean containsKey(String key) {
          accessCount++;
          if (super.containsKey(key)) {
              hitCount++;
              return true;
          } else {
              return false;
          }
      }

      protected boolean removeEldestEntry(Entry eldest) {
          return size() > capacity;
      }

      public long getAccessCount() {
          return accessCount;
      }

      public long getHitCount() {
          return hitCount;
      }
}

比起Go、Python，Java实现LRU算法代码量更少，因为直接使用JDK内置库LinkedHashMap。

完。