閱讀179 返回首頁    go 阿裏雲 go 技術社區[雲棲]

簡單LRU算法實現緩存-update2

update1:第二個實現，讀操作不必要采用獨占鎖，緩存顯然是讀多於寫，讀的時候一開始用獨占鎖是考慮到要遞增計數和更新時間戳要加鎖，不過這兩個變量都是采用原子變量，因此也不必采用獨占鎖，修改為讀寫鎖。
update2:一個錯誤，老是寫錯關鍵字啊，LRUCache的maxCapacity應該聲明為volatile，而不是transient。
  
   最簡單的LRU算法實現，就是利用jdk的LinkedHashMap，覆寫其中的removeEldestEntry(Map.Entry)方法即可，如下所示：
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();
        }
    }
}
    如果你去看LinkedHashMap的源碼可知，LRU算法是通過雙向鏈表來實現，當某個位置被命中，通過調整鏈表的指向將該位置調整到頭位置，新加入的內容直接放在鏈表頭，如此一來，最近被命中的內容就向鏈表頭移動，需要替換時，鏈表最後的位置就是最近最少使用的位置。
    LRU算法還可以通過計數來實現，緩存存儲的位置附帶一個計數器，當命中時將計數器加1，替換時就查找計數最小的位置並替換，結合訪問時間戳來實現。這種算法比較適合緩存數據量較小的場景，顯然，遍曆查找計數最小位置的時間複雜度為O(n)。我實現了一個，結合了訪問時間戳，當最小計數大於MINI_ACESS時(這個參數的調整對命中率有較大影響），就移除最久沒有被訪問的項：
package net.rubyeye.codelib.util.concurrency.cache;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 
 * @author dennis 類說明：當緩存數目不多時，才用緩存計數的傳統LRU算法
 * @param <K>
 * @param <V>
 */
public class LRUCache<K, V> implements Serializable {

    private static final int DEFAULT_CAPACITY = 100;

    protected Map<K, ValueEntry> map;

    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    private final Lock readLock = lock.readLock();

    private final Lock writeLock = lock.writeLock();

    private final volatile int maxCapacity;  //保持可見性

    public static int MINI_ACCESS = 5;

    public LRUCache() {
        this(DEFAULT_CAPACITY);
    }

    public LRUCache(int capacity) {
        if (capacity <= 0)
            throw new RuntimeException("緩存容量不得小於0");
        this.maxCapacity = capacity;
        this.map = new HashMap<K, ValueEntry>(maxCapacity);
    }

    public boolean ContainsKey(K key) {
        try {
            readLock.lock();
            return this.map.containsKey(key);
        } finally {
            readLock.unlock();
        }
    }

    public V put(K key, V value) {
        try {
            writeLock.lock();
            if ((map.size() > maxCapacity - 1) && !map.containsKey(key)) {
                // System.out.println("開始");
                Set<Map.Entry<K, ValueEntry>> entries = this.map.entrySet();
                removeRencentlyLeastAccess(entries);
            }
            ValueEntry new_value = new ValueEntry(value);
            ValueEntry old_value = map.put(key, new_value);
            if (old_value != null) {
                new_value.count = old_value.count;
                return old_value.value;
            } else
                return null;
        } finally {
            writeLock.unlock();
        }
    }

    /**
     * 移除最近最少訪問
     */
    protected void removeRencentlyLeastAccess(
            Set<Map.Entry<K, ValueEntry>> entries) {
        // 最小使用次數
        long least = 0;
        // 訪問時間最早
        long earliest = 0;
        K toBeRemovedByCount = null;
        K toBeRemovedByTime = null;
        Iterator<Map.Entry<K, ValueEntry>> it = entries.iterator();
        if (it.hasNext()) {
            Map.Entry<K, ValueEntry> valueEntry = it.next();
            least = valueEntry.getValue().count.get();
            toBeRemovedByCount = valueEntry.getKey();
            earliest = valueEntry.getValue().lastAccess.get();
            toBeRemovedByTime = valueEntry.getKey();
        }
        while (it.hasNext()) {
            Map.Entry<K, ValueEntry> valueEntry = it.next();
            if (valueEntry.getValue().count.get() < least) {
                least = valueEntry.getValue().count.get();
                toBeRemovedByCount = valueEntry.getKey();
            }
            if (valueEntry.getValue().lastAccess.get() < earliest) {
                earliest = valueEntry.getValue().count.get();
                toBeRemovedByTime = valueEntry.getKey();
            }
        }
        // System.out.println("remove:" + toBeRemoved);
        // 如果最少使用次數大於MINI_ACCESS，那麼移除訪問時間最早的項(也就是最久沒有被訪問的項）
        if (least > MINI_ACCESS) {
            map.remove(toBeRemovedByTime);
        } else {
            map.remove(toBeRemovedByCount);
        }
    }

    public V get(K key) {
        try {
            readLock.lock();
            V value = null;
            ValueEntry valueEntry = map.get(key);
            if (valueEntry != null) {
                // 更新訪問時間戳
                valueEntry.updateLastAccess();
                // 更新訪問次數
                valueEntry.count.incrementAndGet();
                value = valueEntry.value;
            }
            return value;
        } finally {
            readLock.unlock();
        }
    }

    public void clear() {
        try {
            writeLock.lock();
            map.clear();
        } finally {
            writeLock.unlock();
        }
    }

    public int size() {
        try {
            readLock.lock();
            return map.size();
        } finally {
            readLock.unlock();
        }
    }

    public long getCount(K key) {
        try {
            readLock.lock();
            ValueEntry valueEntry = map.get(key);
            if (valueEntry != null) {
                return valueEntry.count.get();
            }
            return 0;
        } finally {
            readLock.unlock();
        }
    }

    public Collection<Map.Entry<K, V>> getAll() {
        try {
            readLock.lock();
            Set<K> keys = map.keySet();
            Map<K, V> tmp = new HashMap<K, V>();
            for (K key : keys) {
                tmp.put(key, map.get(key).value);
            }
            return new ArrayList<Map.Entry<K, V>>(tmp.entrySet());
        } finally {
            readLock.unlock();
        }
    }

    class ValueEntry implements Serializable {
        private V value;

        private AtomicLong count;

        private AtomicLong lastAccess;

        public ValueEntry(V value) {
            this.value = value;
            this.count = new AtomicLong(0);
            lastAccess = new AtomicLong(System.nanoTime());
        }

        public void updateLastAccess() {
            this.lastAccess.set(System.nanoTime());
        }

    }
}
文章轉自莊周夢蝶  ，原文發布時間2007-09-29

最後更新：2017-05-17 16:33:08

  上一篇：go  數字化醫療滲入行業各個分支 器械廠商正趕上這一波熱點
  下一篇：go  Ruby的對象模型