java实现极简的LRU算法

import java.util.LinkedHashMap;

import java.util.Map;

/**

* LRU (Least Recently Used)

public class LRUCache<K, V> extends LinkedHashMap<K, V> {

/**

private static final long serialVersionUID = 1L;

//缓存大小

private int cacheSize;

public LRUCache(int cacheSize) {

//第三个参数true是关键

super(10, 0.75f, true);

this.cacheSize = cacheSize;

}

/**

* 缓存是否已满

@Override

protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {

boolean r = size() > cacheSize;

if(r){

System.out.println("清除缓存key："+eldest.getKey());

}

return r;

}

//测试

public static void main(String[] args) {

LRUCache<String, String> cache = new LRUCache<String, String>(5);

cache.put("1", "1");

cache.put("2", "2");

cache.put("3", "3");

cache.put("4", "4");

cache.put("5", "5");

System.out.println("初始：");

System.out.println(cache.keySet());

System.out.println("访问3：");

cache.get("3");

System.out.println(cache.keySet());

System.out.println("访问2：");

cache.get("2");

System.out.println(cache.keySet());

System.out.println("增加数据6,7：");

cache.put("6", "6");

cache.put("7", "7");

System.out.println(cache.keySet());

}

运行结果如下：

初始化：

[1, 2, 3, 4, 5]

访问3：

[1, 2, 4, 5, 3]

访问2：

[1, 4, 5, 3, 2]

增加数据6,7：

清除缓存key：1

清除缓存key：4

[5, 3, 2, 6, 7]

缓存淘汰算法--LRU算法(java代码实现)

LRU

原理

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

实现1

最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：

1. 新数据插入到链表头部；

2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；

3. 当链表满的时候，将链表尾部的数据丢弃。

分析

【命中率】

当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。

【复杂度】

实现简单。

【代价】

命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。

import java.util.ArrayList; import java.util.Collection; import java.util.LinkedHashMap; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; import java.util.Map; /** * 类说明：利用LinkedHashMap实现简单的缓存，必须实现removeEldestEntry方法，具体参见JDK文档 * * @author dennis * * @param <K> * @param <V> */ public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> { private final int maxCapacity; private static final float DEFAULT_LOAD_FACTOR = 0.75f; private final Lock lock = new ReentrantLock(); public LRULinkedHashMap(int maxCapacity) { super(maxCapacity, DEFAULT_LOAD_FACTOR, true); this.maxCapacity = maxCapacity; } @Override protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) { return size() > maxCapacity; } @Override public boolean containsKey(Object key) { try { lock.lock(); return super.containsKey(key); } finally { lock.unlock(); } } @Override public V get(Object key) { try { lock.lock(); return super.get(key); } finally { lock.unlock(); } } @Override public V put(K key, V value) { try { lock.lock(); return super.put(key, value); } finally { lock.unlock(); } } public int size() { try { lock.lock(); return super.size(); } finally { lock.unlock(); } } public void clear() { try { lock.lock(); super.clear(); } finally { lock.unlock(); } } public Collection<Map.Entry<K, V>> getAll() { try { lock.lock(); return new ArrayList<Map.Entry<K, V>>(super.entrySet()); } finally { lock.unlock(); } } }

实现2

LRUCache的链表+HashMap实现

传统意义的LRU算法是为每一个Cache对象设置一个计数器，每次Cache命中则给计数器+1，而Cache用完，需要淘汰旧内容，放置新内容时，就查看所有的计数器，并将最少使用的内容替换掉。

它的弊端很明显，如果Cache的数量少，问题不会很大，但是如果Cache的空间过大，达到10W或者100W以上，一旦需要淘汰，则需要遍历所有计算器，其性能与资源消耗是巨大的。效率也就非常的慢了。

它的原理：将Cache的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。

这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache。

当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。

上面说了这么多的理论，下面用代码来实现一个LRU策略的缓存。

非线程安全，若实现安全，则在响应的方法加锁。

import java.util.HashMap;import java.util.Map.Entry;import java.util.Set;public class LRUCache<K, V> {private int currentCacheSize;private int CacheCapcity; private HashMap<K,CacheNode> caches; private CacheNode first; private CacheNode last; public LRUCache(int size){ currentCacheSize = 0; this.CacheCapcity = size; caches = new HashMap<K,CacheNode>(size); } public void put(K k,V v){ CacheNode node = caches.get(k); if(node == null){ if(caches.size() >= CacheCapcity){ caches.remove(last.key); removeLast(); } node = new CacheNode(); node.key = k; } node.value = v; moveToFirst(node); caches.put(k, node); } public Object get(K k){ CacheNode node = caches.get(k); if(node == null){ return null; } moveToFirst(node); return node.value; } public Object remove(K k){ CacheNode node = caches.get(k); if(node != null){ if(node.pre != null){ node.pre.next=node.next; } if(node.next != null){ node.next.pre=node.pre; } if(node == first){ first = node.next; } if(node == last){ last = node.pre; } } return caches.remove(k); } public void clear(){ first = null; last = null; caches.clear(); } private void moveToFirst(CacheNode node){ if(first == node){ return; } if(node.next != null){ node.next.pre = node.pre; } if(node.pre != null){ node.pre.next = node.next; } if(node == last){ last= last.pre; } if(first == null || last == null){ first = last = node; return; } node.next=first; first.pre = node; first = node; first.pre=null; } private void removeLast(){ if(last != null){ last = last.pre; if(last == null){ first = null; }else{ last.next = null; } } } @Override public String toString(){ StringBuilder sb = new StringBuilder(); CacheNode node = first; while(node != null){ sb.append(String.format("%s:%s ", node.key,node.value)); node = node.next; } return sb.toString(); } class CacheNode{ CacheNode pre; CacheNode next; Object key; Object value; public CacheNode(){ } } public static void main(String[] args) { LRUCache<Integer,String> lru = new LRUCache<Integer,String>(3); lru.put(1, "a"); // 1:a System.out.println(lru.toString()); lru.put(2, "b"); // 2:b 1:a System.out.println(lru.toString()); lru.put(3, "c"); // 3:c 2:b 1:a System.out.println(lru.toString()); lru.put(4, "d"); // 4:d 3:c 2:b System.out.println(lru.toString()); lru.put(1, "aa"); // 1:aa 4:d 3:c System.out.println(lru.toString()); lru.put(2, "bb"); // 2:bb 1:aa 4:d System.out.println(lru.toString()); lru.put(5, "e"); // 5:e 2:bb 1:aa System.out.println(lru.toString()); lru.get(1); // 1:aa 5:e 2:bb System.out.println(lru.toString()); lru.remove(11); // 1:aa 5:e 2:bb System.out.println(lru.toString()); lru.remove(1); //5:e 2:bb System.out.println(lru.toString()); lru.put(1, "aaa"); //1:aaa 5:e 2:bb System.out.println(lru.toString()); } }

LRU缓存实现(Java)

LRU Cache的LinkedHashMap实现LRU Cache的链表+HashMap实现LinkedHashMap的FIFO实现调用示例

LRU是Least Recently Used 的缩写，翻译过来就是“最近最少使用”，LRU缓存就是使用这种原理实现，简单的说就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉，比如我们缓存10000条数据，当数据小于10000时可以随意添加，当超过10000时就需要把新的数据添加进来，同时要把过期数据删除，以确保我们最大缓存10000条，那怎么确定删除哪条过期数据呢，采用LRU算法实现的话就是将最老的数据删掉，废话不多说，下面来说下Java版的LRU缓存实现

Java里面实现LRU缓存通常有两种选择，一种是使用LinkedHashMap，一种是自己设计数据结构，使用链表+HashMap

LRU Cache的LinkedHashMap实现

LinkedHashMap自身已经实现了顺序存储，默认情况下是按照元素的添加顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面，然后它还有一个判断是否删除最老数据的方法，默认是返回false，即不删除数据，我们使用LinkedHashMap实现LRU缓存的方法就是对LinkedHashMap实现简单的扩展，扩展方式有两种，一种是inheritance，一种是delegation，具体使用什么方式看个人喜好

//LinkedHashMap的一个构造函数，当参数accessOrder为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}//LinkedHashMap自带的判断是否删除最老的元素方法，默认返回false，即不删除老数据//我们要做的就是重写这个方法，当满足一定条件时删除老数据protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;}

LRU缓存LinkedHashMap(inheritance)实现

采用inheritance方式实现比较简单，而且实现了Map接口，在多线程环境使用时可以使用Collections.synchronizedMap()方法实现线程安全操作

package cn.lzrabbit.structure.lru;import java.util.LinkedHashMap;import java.util.Map;/*** Created by liuzhao on 14-5-15.*/public class LRUCache2<K, V> extends LinkedHashMap<K, V> {private final int MAX_CACHE_SIZE;public LRUCache2(int cacheSize) {super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);MAX_CACHE_SIZE = cacheSize;}@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {return size() > MAX_CACHE_SIZE;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();for (Map.Entry<K, V> entry : entrySet()) {sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));}return sb.toString();}}

这样算是比较标准的实现吧，实际使用中这样写还是有些繁琐，更实用的方法时像下面这样写，省去了单独见一个类的麻烦

final int cacheSize = 100;Map<String, String> map = new LinkedHashMap<String, String>((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry<String, String> eldest) {return size() > cacheSize;}};

LRU缓存LinkedHashMap(delegation)实现

delegation方式实现更加优雅一些，但是由于没有实现Map接口，所以线程同步就需要自己搞定了

package cn.lzrabbit.structure.lru;import java.util.LinkedHashMap;import java.util.Map;import java.util.Set;/*** Created by liuzhao on 14-5-13.*/public class LRUCache3<K, V> {private final int MAX_CACHE_SIZE;private final float DEFAULT_LOAD_FACTOR = 0.75f;LinkedHashMap<K, V> map;public LRUCache3(int cacheSize) {MAX_CACHE_SIZE = cacheSize;//根据cacheSize和加载因子计算hashmap的capactiy，+1确保当达到cacheSize上限时不会触发hashmap的扩容，int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1;map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry 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();}public synchronized int size() {return map.size();}public synchronized void clear() {map.clear();}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();for (Map.Entry entry : map.entrySet()) {sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));}return sb.toString();}}

LRU Cache的链表+HashMap实现

注：此实现为非线程安全，若在多线程环境下使用需要在相关方法上添加synchronized以实现线程安全操作

package cn.lzrabbit.structure.lru;import java.util.HashMap;/*** Created by liuzhao on 14-5-12.*/public class LRUCache1<K, V> {private final int MAX_CACHE_SIZE;private Entry first;private Entry last;private HashMap<K, Entry<K, V>> hashMap;public LRUCache1(int cacheSize) {MAX_CACHE_SIZE = cacheSize;hashMap = new HashMap<K, Entry<K, V>>();}public void put(K key, V value) {Entry entry = getEntry(key);if (entry == null) {if (hashMap.size() >= MAX_CACHE_SIZE) {hashMap.remove(last.key);removeLast();}entry = new Entry();entry.key = key;}entry.value = value;moveToFirst(entry);hashMap.put(key, entry);}public V get(K key) {Entry<K, V> entry = getEntry(key);if (entry == null) return null;moveToFirst(entry);return entry.value;}public void remove(K key) {Entry entry = getEntry(key);if (entry != null) {if (entry.pre != null) entry.pre.next = entry.next;if (entry.next != null) entry.next.pre = entry.pre;if (entry == first) first = entry.next;if (entry == last) last = entry.pre;}hashMap.remove(key);}private void moveToFirst(Entry entry) {if (entry == first) return;if (entry.pre != null) entry.pre.next = entry.next;if (entry.next != null) entry.next.pre = entry.pre;if (entry == last) last = last.pre;if (first == null || last == null) {first = last = entry;return;}entry.next = first;first.pre = entry;first = entry;entry.pre = null;}private void removeLast() {if (last != null) {last = last.pre;if (last == null) first = null;else last.next = null;}}private Entry<K, V> getEntry(K key) {return hashMap.get(key);}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();Entry entry = first;while (entry != null) {sb.append(String.format("%s:%s ", entry.key, entry.value));entry = entry.next;}return sb.toString();}class Entry<K, V> {public Entry pre;public Entry next;public K key;public V value;}}

LinkedHashMap的FIFO实现

FIFO是First Input First Output的缩写，也就是常说的先入先出，默认情况下LinkedHashMap就是按照添加顺序保存，我们只需重写下removeEldestEntry方法即可轻松实现一个FIFO缓存，简化版的实现代码如下

final int cacheSize = 5;LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() {@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {return size() > cacheSize;}};

调用示例

测试代码

package cn.lzrabbit.structure.lru;import cn.lzrabbit.ITest;import java.util.LinkedHashMap;import java.util.Map;/*** Created by liuzhao on 14-5-15.*/public class LRUCacheTest {public static void main(String[] args) throws Exception {System.out.println("start...");lruCache1();lruCache2();lruCache3();lruCache4();System.out.println("over...");}static void lruCache1() {System.out.println();System.out.println("===========================LRU 链表实现===========================");LRUCache1<Integer, String> lru = new LRUCache1(5);lru.put(1, "11");lru.put(2, "11");lru.put(3, "11");lru.put(4, "11");lru.put(5, "11");System.out.println(lru.toString());lru.put(6, "66");lru.get(2);lru.put(7, "77");lru.get(4);System.out.println(lru.toString());System.out.println();}static <T> void lruCache2() {System.out.println();System.out.println("===========================LRU LinkedHashMap(inheritance)实现===========================");LRUCache2<Integer, String> lru = new LRUCache2(5);lru.put(1, "11");lru.put(2, "11");lru.put(3, "11");lru.put(4, "11");lru.put(5, "11");System.out.println(lru.toString());lru.put(6, "66");lru.get(2);lru.put(7, "77");lru.get(4);System.out.println(lru.toString());System.out.println();}static void lruCache3() {System.out.println();System.out.println("===========================LRU LinkedHashMap(delegation)实现===========================");LRUCache3<Integer, String> lru = new LRUCache3(5);lru.put(1, "11");lru.put(2, "11");lru.put(3, "11");lru.put(4, "11");lru.put(5, "11");System.out.println(lru.toString());lru.put(6, "66");lru.get(2);lru.put(7, "77");lru.get(4);System.out.println(lru.toString());System.out.println();}static void lruCache4() {System.out.println();System.out.println("===========================FIFO LinkedHashMap默认实现===========================");final int cacheSize = 5;LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() {@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {return size() > cacheSize;}};lru.put(1, "11");lru.put(2, "11");lru.put(3, "11");lru.put(4, "11");lru.put(5, "11");System.out.println(lru.toString());lru.put(6, "66");lru.get(2);lru.put(7, "77");lru.get(4);System.out.println(lru.toString());System.out.println();}}

运行结果

"C:\Program Files (x86)\Java\jdk1.6.0_10\bin\java" -Didea.launcher.port=7535 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.0.2\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\charsets.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\deploy.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\javaws.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\jce.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\jsse.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\management-agent.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\plugin.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\resources.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\rt.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\dnsns.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\localedata.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunjce_provider.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunmscapi.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunpkcs11.jar;D:\SVN\projects\Java\Java.Algorithm\target\test-classes;D:\SVN\projects\Java\Java.Algorithm\target\classes;C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.0.2\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain Mainstart...===========================LRU 链表实现===========================5:11 4:11 3:11 2:11 1:11 4:11 7:77 2:11 6:66 5:11 ===========================LRU LinkedHashMap(inheritance)实现===========================1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 ===========================LRU LinkedHashMap(delegation)实现===========================1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 ===========================FIFO LinkedHashMap默认实现==========================={1=11, 2=11, 3=11, 4=11, 5=11}{3=11, 4=11, 5=11, 6=66, 7=77}over...Process finished with exit code 0