轻松扩展LinkedHashMap类实现LRU算法

    今天偶然看到某框架源码自带的简单缓存策略算法LRU的实现，不想就几行代码即实现，原来只是简单的扩展了 jdk自带的LinkedHashMap类，如此简单，故分享之。

     具体关于LinkedHashMap 的描述 不懂的自己去看 jdk api 文档，这里只说说怎么实现，翻开LinkedHashMap 源码 我们可以看到一段描述：

/**
* Returns <tt>true</tt> if this map should remove its eldest entry.
* This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
* inserting a new entry into the map. It provides the implementor
* with the opportunity to remove the eldest entry each time a new one
* is added. This is useful if the map represents a cache: it allows
* the map to reduce memory consumption by deleting stale entries.
*
* <p>Sample use: this override will allow the map to grow up to 100
* entries and then delete the eldest entry each time a new entry is
* added, maintaining a steady state of 100 entries.
* <pre>
* private static final int MAX_ENTRIES = 100;
*
* protected boolean removeEldestEntry(Map.Entry eldest) {
* return size() > MAX_ENTRIES;
* }
**/

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

 

    意思就是说 在 put() 或者 putAll() 操作后会调用此方法判断 是否需要 清除最旧的那个元素，默认是返回 false，即不做操作。注意此 方法 是 protected ，即用于子类覆盖的，可以说这是 jdk的开发者特意留下来为我们实现LRU提供的，注释也说了，我们可以简单的覆盖此方法实现 LRU ，如：

public class LruCache implements Cache {

private final Map<Object, Object> store;
private int initialCapacity = 16;
private float loadFactor = 0.75f;
private boolean accessOrder = true;

public LruCache(URL url) {
final int max = 1000; // 缓存中最多1000个元素
this.store = new LinkedHashMap<Object, Object>(initialCapacity,loadFactor,accessOrder){
private static final long serialVersionUID = -3834209229668463829L;
@Override
protected boolean removeEldestEntry(Entry<Object, Object> eldest) {
return size() > max;
}
};
}
}

 

    这样当 stroe 中的元素超过 max=1000个时，将从 map 中删除 最旧的那个元素，即实现了 LRU。
需要注意的是，LinkedHashMap 并未覆盖 父类 HashMap中的 put() 和 putAll() ，而是覆盖了 会被 put() 调用的addEntry() 方法，我们来看下LinkedHashMap中的addEntry() ：

void addEntry(int hash, K key, V value, int bucketIndex) {
createEntry(hash, key, value, bucketIndex);

// Remove eldest entry if instructed, else grow capacity if appropriate
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}else {
if (size >= threshold)
resize(2 * table.length);
}
}

 

    看到了吧，如果返回为 true，则会删除最旧的那个元素，so simple

 

   ps: 如果在多线程环境下使用，由于其父类 HashMap不支持同步，所以需要重写 get put 方法，无非就是加个同步：

 

    

 public void put(Object key, Object value) {
        synchronized (store) {
            store.put(key, value);
        }
    }

    public Object get(Object key) {
        synchronized (store) {
            return store.get(key);
        }
    }