歡迎光臨
每天分享高質量文章

LRU 快取實現( Java )

點擊上方“Java技術驛站”,選擇“置頂公眾號”。

有內涵、有價值的文章第一時間送達!

精品專欄

 

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 ,具體使用什麼方式看個人喜好

  1. //LinkedHashMap的一個建構式,當引數accessOrder為true時,即會按照訪問順序排序,最近訪問的放在最前,最早訪問的放在後面

  2. public LinkedHashMap(

  3.    int initialCapacity, float loadFactor, boolean accessOrder) {        

  4.    super(initialCapacity, loadFactor);        

  5.    this.accessOrder = accessOrder;

  6. }

  7. //LinkedHashMap自帶的判斷是否刪除最老的元素方法,預設傳回false,即不刪除老資料

  8. //我們要做的就是重寫這個方法,當滿足一定條件時刪除老資料

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

  10.    return false;

  11. }

LRU快取 LinkedHashMap(inheritance) 實現

採用 inheritance 方式實現比較簡單,而且實現了 Map 接口,在多執行緒環境使用時可以使用 Collections.synchronizedMap() 方法實現執行緒安全操作

  1. package cn.lzrabbit.structure.lru;

  2. import java.util.LinkedHashMap;

  3. import java.util.Map;

  4. /**

  5. * Created by liuzhao on 14-5-15. */

  6. public class LRUCache2<K, V> extends LinkedHashMap<K, V> {

  7.     private final int MAX_CACHE_SIZE;

  8.     public LRUCache2(int cacheSize) {

  9.         super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);

  10.        MAX_CACHE_SIZE = cacheSize;

  11.    }

  12.    @Override

  13.     protected boolean removeEldestEntry(Map.Entry eldest) {

  14.         return size() > MAX_CACHE_SIZE;

  15.    }

  16.    @Override

  17.     public String toString() {

  18.        StringBuilder sb = new StringBuilder();

  19.         for (Map.Entry<K, V> entry : entrySet()) {

  20.            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));

  21.        }

  22.        return sb.toString();

  23.    }

  24. }

這樣算是比較標準的實現吧,實際使用中這樣寫還是有些繁瑣,更實用的方法時像下麵這樣寫,省去了單獨見一個類的麻煩

  1. final int cacheSize = 100;

  2. Map<String, String> map = new LinkedHashMap<String, String>((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true) {

  3.    @Override

  4.    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {

  5.     return size() > cacheSize;

  6.    }

  7. };

LRU快取 LinkedHashMap(delegation) 實現

delegation 方式實現更加優雅一些,但是由於沒有實現 Map 接口,所以執行緒同步就需要自己搞定了

  1. package cn.lzrabbit.structure.lru;

  2. import java.util.LinkedHashMap;

  3. import java.util.Map;

  4. import java.util.Set;/**

  5. * Created by liuzhao on 14-5-13. */

  6. public class LRUCache3<K, V> {

  7.     private final int MAX_CACHE_SIZE;

  8.     private final float DEFAULT_LOAD_FACTOR = 0.75f;

  9.    LinkedHashMap<K, V> map;

  10.     public LRUCache3(int cacheSize) {

  11.        MAX_CACHE_SIZE = cacheSize;

  12.         //根據cacheSize和加載因子計算hashmap的capactiy,+1確保當達到cacheSize上限時不會觸發hashmap的擴容,

  13.        int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1;

  14.        map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR, true) {

  15.        @Override

  16.        protected boolean removeEldestEntry(Map.Entry eldest) {                             return size() > MAX_CACHE_SIZE;

  17.        }

  18.        };

  19.    }    

  20.    public synchronized void put(K key, V value) {

  21.        map.put(key, value);

  22.    }

  23.     public synchronized V get(K key) {

  24.         return map.get(key);

  25.    }

  26.     public synchronized void remove(K key) {

  27.        map.remove(key);

  28.    }

  29.     public synchronized Set<Map.Entry<K, V>> getAll() {

  30.         return map.entrySet();

  31.    }

  32.     public synchronized int size() {

  33.         return map.size();

  34.    }

  35.     public synchronized void clear() {

  36.        map.clear();

  37.    }

  38.    @Override

  39.     public String toString() {

  40.        StringBuilder sb = new StringBuilder();

  41.         for (Map.Entry entry : map.entrySet()) {

  42.            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));

  43.        }

  44.        return sb.toString();

  45.    }

  46. }

LRU Cache的鏈表+HashMap實現

註:此實現為非執行緒安全,若在多執行緒環境下使用需要在相關方法上添加synchronized 以實現執行緒安全操作

  1. package cn.lzrabbit.structure.lru;

  2. import java.util.HashMap;/**

  3. * Created by liuzhao on 14-5-12. */

  4. public class LRUCache1<K, V> {

  5.     private final int MAX_CACHE_SIZE;

  6.     private Entry first;

  7.     private Entry last;

  8.     private HashMap<K, Entry<K, V>> hashMap;

  9.     public LRUCache1(int cacheSize) {

  10.        MAX_CACHE_SIZE = cacheSize;

  11.        hashMap = new HashMap<K, Entry<K, V>>();

  12.    }

  13.    public void put(K key, V value) {

  14.        Entry entry = getEntry(key);

  15.        if (entry == null) {

  16.            if (hashMap.size() >= MAX_CACHE_SIZE) {

  17.                hashMap.remove(last.key);

  18.                removeLast();

  19.            }

  20.            entry = new Entry();

  21.            entry.key = key;

  22.        }

  23.        entry.value = value;

  24.        moveToFirst(entry);

  25.        hashMap.put(key, entry);

  26.    }

  27.     public V get(K key) {

  28.        Entry<K, V> entry = getEntry(key);

  29.         if (entry == null) return null;

  30.        moveToFirst(entry);

  31.        return entry.value;

  32.    }

  33.     public void remove(K key) {

  34.        Entry entry = getEntry(key);

  35.         if (entry != null) {

  36.            if (entry.pre != null)

  37.                 entry.pre.next = entry.next;

  38.             if (entry.next != null)

  39.                  entry.next.pre = entry.pre;

  40.             if (entry == first) first = entry.next;

  41.             if (entry == last) last = entry.pre;

  42.        }

  43.        hashMap.remove(key);

  44.    }

  45.     private void moveToFirst(Entry entry) {

  46.        if (entry == first) return;

  47.        if (entry.pre != null) entry.pre.next = entry.next;

  48.        if (entry.next != null) entry.next.pre = entry.pre;

  49.        if (entry == last) last = last.pre;

  50.        if (first == null || last == null) {

  51.            first = last = entry;

  52.            return;

  53.        }

  54.        entry.next = first;

  55.        first.pre = entry;

  56.        first = entry;

  57.        entry.pre = null;

  58.    }

  59.    private void removeLast() {

  60.         if (last != null) {

  61.            last = last.pre;

  62.            if (last == null) first = null;

  63.            else last.next = null;

  64.        }

  65.    }

  66.    private Entry<K, V> getEntry(K key) {

  67.         return hashMap.get(key);

  68.    }

  69.    @Override

  70.     public String toString() {

  71.        StringBuilder sb = new StringBuilder();

  72.        Entry entry = first;

  73.         while (entry != null) {

  74.            sb.append(String.format("%s:%s ", entry.key, entry.value));

  75.            entry = entry.next;

  76.        }

  77.         return sb.toString();

  78.    }

  79.     class Entry<K, V> {

  80.         public Entry pre;

  81.         public Entry next;

  82.         public K key;

  83.         public V value;

  84.    }

  85. }

LinkedHashMap的FIFO實現

FIFO是First Input First Output的縮寫,也就是常說的先入先出,預設情況下LinkedHashMap就是按照添加順序儲存,我們只需重寫下removeEldestEntry方法即可輕鬆實現一個FIFO快取,簡化版的實現代碼如下

  1. final int cacheSize = 5;

  2. LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() {

  3.    @Override    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {    return size() > cacheSize;

  4.    }

  5. };

測試

  1. public class LRUCacheTest  {    

  2. public static void main(String[] args) throws Exception {

  3.        System.out.println("start...");

  4.        lruCache1();

  5.        lruCache2();

  6.        lruCache3();

  7.        lruCache4();

  8.        System.out.println("over...");

  9.    }

  10. static void lruCache1() {

  11.        System.out.println();

  12.        System.out.println("===========================LRU 鏈表實現===========================");

  13.        LRUCache1<Integer, String> lru = new LRUCache1(5);

  14.        lru.put(1, "11");

  15.        lru.put(2, "11");

  16.        lru.put(3, "11");

  17.        lru.put(4, "11");

  18.        lru.put(5, "11");

  19.        System.out.println(lru.toString());

  20.        lru.put(6, "66");

  21.        lru.get(2);

  22.        lru.put(7, "77");

  23.        lru.get(4);

  24.        System.out.println(lru.toString());

  25.        System.out.println();

  26.    }

  27.    static   <T> void lruCache2() {

  28.        System.out.println();

  29.        System.out.println("===========================LRU LinkedHashMap(inheritance)實現===========================");

  30.        LRUCache2<Integer, String> lru = new LRUCache2(5);

  31.        lru.put(1, "11");

  32.        lru.put(2, "11");

  33.        lru.put(3, "11");

  34.        lru.put(4, "11");

  35.        lru.put(5, "11");

  36.        System.out.println(lru.toString());

  37.        lru.put(6, "66");

  38.        lru.get(2);

  39.        lru.put(7, "77");

  40.        lru.get(4);

  41.        System.out.println(lru.toString());

  42.        System.out.println();

  43.    }  

  44.    static  void lruCache3() {

  45.        System.out.println();

  46.        System.out.println("===========================LRU LinkedHashMap(delegation)實現===========================");

  47.        LRUCache3<Integer, String> lru = new LRUCache3(5);

  48.        lru.put(1, "11");

  49.        lru.put(2, "11");

  50.        lru.put(3, "11");

  51.        lru.put(4, "11");

  52.        lru.put(5, "11");

  53.        System.out.println(lru.toString());

  54.        lru.put(6, "66");

  55.        lru.get(2);

  56.        lru.put(7, "77");

  57.        lru.get(4);

  58.        System.out.println(lru.toString());

  59.        System.out.println();

  60.    }  

  61.    static  void lruCache4() {

  62.        System.out.println();

  63.        System.out.println("===========================FIFO LinkedHashMap預設實現===========================");        final int cacheSize = 5;

  64.        LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() {

  65.            @Override            

  66.        protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {                return size() > cacheSize;

  67.            }

  68.        };

  69.        lru.put(1, "11");

  70.        lru.put(2, "11");

  71.        lru.put(3, "11");

  72.        lru.put(4, "11");

  73.        lru.put(5, "11");

  74.        System.out.println(lru.toString());

  75.        lru.put(6, "66");

  76.        lru.get(2);

  77.        lru.put(7, "77");

  78.        lru.get(4);

  79.        System.out.println(lru.toString());

  80.        System.out.println();

  81.    }

  82. }

運行結果

  1. "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 Main

  2. start...===========================LRU 鏈表實現===========================

  3. 5:11 4:11 3:11 2:11 1:11

  4. 4:11 7:77 2:11 6:66 5:11

  5. ===========================LRU LinkedHashMap(inheritance)實現===========================

  6. 1:11 2:11 3:11 4:11 5:11

  7. 5:11 6:66 2:11 7:77 4:11

  8. ===========================LRU LinkedHashMap(delegation)實現===========================

  9. 1:11 2:11 3:11 4:11 5:11

  10. 5:11 6:66 2:11 7:77 4:11

  11. ===========================FIFO LinkedHashMap預設實現==========================={1=11, 2=11, 3=11, 4=11, 5=11}

  12. {3=11, 4=11, 5=11, 6=66, 7=77}

  13. over...

  14. Process finished with exit code 0

MySQL事務隔離級別和Spring事務關係介紹

9個提升逼格的redis命令

你的JVM還好嗎?GC初步診斷

一個簡單java程式的運行全過程

四年努力,夢歸阿裡,和大家聊聊成長感悟

END

赞(0)

分享創造快樂

© 2021 知識星球   网站地图