java中怎樣實(shí)現(xiàn)LRU緩存

java中怎樣實(shí)現(xiàn)LRU緩存？針對這個(gè)問題，這篇文章給出了相對應(yīng)的分析和解答，希望能幫助更多想解決這個(gè)問題的朋友找到更加簡單易行的辦法。

LRU是Least Recently Used 的縮寫，翻譯過來就是“最近最少使用”，最近最少使用算法（LRU）是大部分操作系統(tǒng)為最大化頁面命中率而廣泛采用的一種頁面置換算法。該算法的思路是，發(fā)生缺頁中斷時(shí)，選擇未使用時(shí)間最長的頁面置換出去。[1]從程序運(yùn)行的原理來看，最近最少使用算法是比較接近理想的一種頁面置換算法，這種算法既充分利用了內(nèi)存中頁面調(diào)用的歷史信息，又正確反映了程序的局部問題。

比如我們緩存10000條數(shù)據(jù)，當(dāng)數(shù)據(jù)小于10000時(shí)可以隨意添加，當(dāng)超過10000時(shí)就需要把新的數(shù)據(jù)添加進(jìn)來，同時(shí)要把過期數(shù)據(jù)刪除，以確保我們最大緩存10000條，那怎么確定刪除哪條過期數(shù)據(jù)呢，采用LRU算法實(shí)現(xiàn)的話就是將最老的數(shù)據(jù)刪掉。

下面來說下Java版的LRU緩存實(shí)現(xiàn)：

Java里面實(shí)現(xiàn)LRU緩存通常有兩種選擇，一種是使用LinkedHashMap，一種是自己設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，使用鏈表+HashMap

LRU Cache的LinkedHashMap實(shí)現(xiàn)

LinkedHashMap自身已經(jīng)實(shí)現(xiàn)了順序存儲，默認(rèn)情況下是按照元素的添加順序存儲，也可以啟用按照訪問順序存儲，即最近讀取的數(shù)據(jù)放在最前面，最早讀取的數(shù)據(jù)放在最后面，然后它還有一個(gè)判斷是否刪除最老數(shù)據(jù)的方法，默認(rèn)是返回false，即不刪除數(shù)據(jù)。

我們使用LinkedHashMap實(shí)現(xiàn)LRU緩存的方法就是對LinkedHashMap實(shí)現(xiàn)簡單的擴(kuò)展，擴(kuò)展方式有兩種，一種是inheritance，一種是delegation。

//LinkedHashMap的一個(gè)構(gòu)造函數(shù)，當(dāng)參數(shù)accessOrder為true時(shí)，即會按照訪問順序排序，最近訪問的放在最前，最早訪問的放在后面
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
}

//LinkedHashMap自帶的判斷是否刪除最老的元素方法，默認(rèn)返回false，即不刪除老數(shù)據(jù)
//我們要做的就是重寫這個(gè)方法，當(dāng)滿足一定條件時(shí)刪除老數(shù)據(jù)
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
}

LRU緩存LinkedHashMap(delegation)實(shí)現(xiàn)

delegation方式實(shí)現(xiàn)更加優(yōu)雅一些，但是由于沒有實(shí)現(xiàn)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;
        //根據(jù)cacheSize和加載因子計(jì)算hashmap的capactiy，+1確保當(dāng)達(dá)到cacheSize上限時(shí)不會觸發(fā)hashmap的擴(kuò)容，
        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緩存LinkedHashMap(inheritance)實(shí)現(xiàn)

采用inheritance方式實(shí)現(xiàn)比較簡單，而且實(shí)現(xiàn)了Map接口，在多線程環(huán)境使用時(shí)可以使用 Collections.synchronizedMap()方法實(shí)現(xiàn)線程安全操作

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();
    }
}

這樣算是比較標(biāo)準(zhǔn)的實(shí)現(xiàn)吧，實(shí)際使用中這樣寫還是有些繁瑣，更實(shí)用的方法時(shí)像下面這樣寫，省去了單獨(dú)見一個(gè)類的麻煩

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 Cache的鏈表+HashMap實(shí)現(xiàn)

注：此實(shí)現(xiàn)為非線程安全，若在多線程環(huán)境下使用需要在相關(guān)方法上添加synchronized以實(shí)現(xiàn)線程安全操作

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實(shí)現(xiàn)

FIFO是First Input First Output的縮寫，也就是常說的先入先出，默認(rèn)情況下LinkedHashMap就是按照添加順序保存，我們只需重寫下removeEldestEntry方法即可輕松實(shí)現(xiàn)一個(gè)FIFO緩存，簡化版的實(shí)現(xiàn)代碼如下

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

調(diào)用示例

測試代碼

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 鏈表實(shí)現(xiàn)===========================");
        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)實(shí)現(xiàn)===========================");
        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)實(shí)現(xiàn)===========================");
        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默認(rèn)實(shí)現(xiàn)===========================");
        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();
    }

}

運(yùn)行結(jié)果

"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
start...

===========================LRU 鏈表實(shí)現(xiàn)===========================
5:11 4:11 3:11 2:11 1:11 
4:11 7:77 2:11 6:66 5:11 


===========================LRU LinkedHashMap(inheritance)實(shí)現(xiàn)===========================
1:11 2:11 3:11 4:11 5:11 
5:11 6:66 2:11 7:77 4:11 


===========================LRU LinkedHashMap(delegation)實(shí)現(xiàn)===========================
1:11 2:11 3:11 4:11 5:11 
5:11 6:66 2:11 7:77 4:11 


===========================FIFO LinkedHashMap默認(rèn)實(shí)現(xiàn)===========================
{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

關(guān)于java中怎樣實(shí)現(xiàn)LRU緩存就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。