LRUCache 詳解

LRU的基本概念：

    LRU是Least Recently Used的縮寫，近期最少使用算法。

Java 實作LRUCache

  1、基于LRU的基本概念，為了達到按近期最少使用排序，可以選擇HashMap的子類

 LinkedHashMap來作為LRUCache的存儲容器。

  2、LinkedHashMap的原理：

  a、 對于LinkedHashMap而言，它繼承與HashMap、底層使用哈希表與雙向連結清單來儲存所有元素。其基本操作與父類HashMap相似，它通過重寫父類相關的方法，來實作自己的連結清單特性。HashMap是單連結清單，LinkedHashMap是雙向連結清單

  b、存儲：LinkedHashMap并未重寫父類HashMap的put方法，而是重寫了父類HashMap的put方法調用的子方法void recordAccess(HashMap m)   ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的雙向連結清單的實作。

  c、讀取：LinkedHashMap重寫了父類HashMap的get方法，實際在調用父類getEntry()方法取得查找的元素後，再判斷當排序模式accessOrder為true時，記錄通路順序，将最新通路的元素添加到雙向連結清單的表頭，并從原來的位置删除。由于的連結清單的增加、删除操作是常量級的，故并不會帶來性能的損失。

LRUCache的簡單實作

package com.knowledgeStudy.lrucache;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
/**
 * 固定大小 的LRUCache<br>
 * 線程安全
 **/
public class LRUCache<K, V> {
    private static final float factor = 0.75f;//擴容因子
    private Map<K, V> map; //資料存儲容器
    private int cacheSize;//緩存大小
    public LRUCache(int cacheSize) {
        this.cacheSize = cacheSize;
        int capacity = (int) Math.ceil(cacheSize / factor) + 1;
        map = new LinkedHashMap<K, V>(capacity, factor, true) {
            private static final long serialVersionUID = 1L;
            /**
             * 重寫LinkedHashMap的removeEldestEntry()固定table中連結清單的長度
             **/
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                boolean todel = size() > LRUCache.this.cacheSize;
                return todel;
            }
        };
    }
    /**
     * 根據key擷取value
     *
     * @param key
     * @return value
     **/
    public synchronized V get(K key) {
        return map.get(key);
    }
    /**
     * put一個key-value
     *
     * @param key
     *            value
     **/
    public synchronized void put(K key, V value) {
        map.put(key, value);
    }
    /**
     * 根據key來删除一個緩存
     *
     * @param key
     **/
    public synchronized void remove(K key) {
        map.remove(key);
    }
    /**
     * 清空緩存
     **/
    public synchronized void clear() {
        map.clear();
    }
    /**
     * 已經使用緩存的大小
     **/
    public synchronized int cacheSize() {
        return map.size();
    }
    /**
     * 擷取緩存中所有的鍵值對
     **/
    public synchronized Collection<Map.Entry<K, V>> getAll() {
        return new ArrayList<Map.Entry<K, V>>(map.entrySet());
    }
}