java LRU(Least Recently Used )詳解及實例代碼

java LRU(Least Recently Used )詳解

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; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_CACHE_SIZE; } @Override public 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) { @Override protected 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) { @Override protected 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(); } @Override public 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); } @Override public 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>() { @Override protected 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>() { @Override protected 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

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！