LRU緩存

1.LRU 緩存機(jī)制可以通過(guò)哈希表輔以雙向鏈表實(shí)現(xiàn)，用一個(gè)哈希表和一個(gè)雙向鏈表維護(hù)所有在緩存中的鍵值對(duì)


public class SingleLRU {

    public class DlinkNode{
        private int key;
        private int value;
        private DlinkNode pre;
        private DlinkNode next;
        public DlinkNode(){};
        public DlinkNode(int key, int value){
            this.key= key;
            this.value = value;
        }
    }

    private Map<Integer,DlinkNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DlinkNode head,tail;

    public SingleLRU(int capacity){
        this.size = 0;
        this.capacity = capacity;
        head = new DlinkNode();
        tail = new DlinkNode();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key){
        DlinkNode node = cache.get(key);
        if(node == null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key,int value){
        DlinkNode node = cache.get(key);
        if(node != null){
            node.value = value;
            moveToHead(node);
        }else{
            node = new DlinkNode(key,value);
            cache.put(key,node);
            addToHead(node);
            size++;
            if(size > capacity){
                DlinkNode dTail = removeTail();
                cache.remove(dTail.key);
                --size;
            }
        }
    }


    private void moveToHead(DlinkNode node){
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(DlinkNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void addToHead(DlinkNode node){
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    private DlinkNode removeTail(){
        DlinkNode node = tail.pre;
        removeNode(node);
        return node;
    }

    public static void main(String[] args) {
        SingleLRU lRUCache = new SingleLRU(2);
        lRUCache.put(1, 1); // 緩存是 {1=1}
        lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
        int a = lRUCache.get(1);    // 返回 1
        lRUCache.put(3, 3); // 該操作會(huì)使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
        int b = lRUCache.get(2);    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 該操作會(huì)使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3}
        int c = lRUCache.get(1);    // 返回 -1 (未找到)
        int d =lRUCache.get(3);    // 返回 3
        int e =lRUCache.get(4);    // 返回 4
    }
}

2.使用 ConcurrentHashMap+雙向鏈表+ReadWriteLock實(shí)現(xiàn)線程安全的 LRU 緩存

public class ConcurrentCache<K,V> {

    class DLinkNode<K,V>{
        private K key;
        private V value;
        private DLinkNode<K,V> pre;
        private DLinkNode<K,V> next;
        public DLinkNode(){};
        public DLinkNode(K key, V value){
            this.key = key;
            this.value = value;
        }
    }

    private ConcurrentHashMap<K, DLinkNode<K,V>> cache = new ConcurrentHashMap<>();

    private ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    private Lock readLock = readWriteLock.readLock();
    private Lock writeLock = readWriteLock.writeLock();

    private int capacity;
    private int size;
    private DLinkNode<K,V> head,tail;

    public ConcurrentCache(int capacity) {
        this.capacity = capacity;
        size = 0;
        head = new DLinkNode();
        tail = new DLinkNode();
        head.next = tail;
        tail.pre = head;
    }

    public <V> V get(K key) {
        readLock.lock();
        try {
            DLinkNode<K,V> node = (DLinkNode<K,V>)cache.get(key);
            if(node != null){
                moveToHead(node);
                return node.value;
            }
        }finally {
            readLock.unlock();
        }
        return null;
    }

    public void put(K key, V value) {
        writeLock.lock();
        try{
            DLinkNode<K,V> node = (DLinkNode<K,V>)cache.get(key);
            if(node == null){
                node = new DLinkNode(key,value);
                addToHead(node);
                cache.put(key,node);
                size++;
                if(size > capacity){
                    DLinkNode rNode = removeTail();
                    cache.remove(rNode.key);
                    size--;
                }
            }else{
                node.value = value;
                moveToHead(node);
            }
        }finally {
            writeLock.unlock();
        }
    }

    private void moveToHead(DLinkNode node){
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(DLinkNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void addToHead(DLinkNode node){
        node.pre = this.head;
        node.next = this.head.next;
        this.head.next.pre = node;
        this.head.next = node;
    }

    private DLinkNode removeTail(){
        DLinkNode rNode = this.tail.pre;
        removeNode(rNode);
        return rNode;
    }

}
  1. 實(shí)現(xiàn)一個(gè)線程安全并且?guī)в羞^(guò)期時(shí)間的 LRU 緩存
    ScheduledExecutorService ：定時(shí)器線程池定時(shí)刪除緩存
public class ConcurrentCache<K,V> {

    public static void main(String[] args) {
        ConcurrentCache<Integer,String> concurrentCache = new ConcurrentCache<>(3);
        concurrentCache.put(1,"Java",3000);
        concurrentCache.put(2,"C++",3000);
        concurrentCache.put(3,"Python",1500);
        System.out.println(concurrentCache.size());//3
        try {
            Thread.sleep(2000);
        }catch (Exception e){

        }
        System.out.println(concurrentCache.size());//2
    }

    class DLinkNode<K,V>{
        private K key;
        private V value;
        private DLinkNode<K,V> pre;
        private DLinkNode<K,V> next;
        public DLinkNode(){};
        public DLinkNode(K key, V value){
            this.key = key;
            this.value = value;
        }
    }

    private ConcurrentHashMap<K, DLinkNode<K,V>> cache = new ConcurrentHashMap<>();
    private ScheduledExecutorService scheduledExecutorService;
    private ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    private Lock readLock = readWriteLock.readLock();
    private Lock writeLock = readWriteLock.writeLock();

    private int capacity;
    private int size;
    private DLinkNode<K,V> head,tail;

    public ConcurrentCache(int capacity) {
        this.capacity = capacity;
        size = 0;
        head = new DLinkNode();
        tail = new DLinkNode();
        head.next = tail;
        tail.pre = head;
        scheduledExecutorService = Executors.newScheduledThreadPool(3);
    }

    public <V> V get(K key) {
        readLock.lock();
        try {
            DLinkNode<K,V> node = (DLinkNode<K,V>)cache.get(key);
            if(node != null){
                moveToHead(node);
                return node.value;
            }
        }finally {
            readLock.unlock();
        }
        return null;
    }

    public void put(K key, V value,long expireTime) {
        writeLock.lock();
        try{
            DLinkNode<K,V> node = (DLinkNode<K,V>)cache.get(key);
            if(node == null){
                node = new DLinkNode(key,value);
                addToHead(node);
                cache.put(key,node);
                size++;
                if(size > capacity){
                    DLinkNode rNode = removeTail();
                    cache.remove(rNode.key);
                    size--;
                }
                if (expireTime > 0){
                    removeAfterExpireTime(key,expireTime);
                }
            }else{
                node.value = value;
                moveToHead(node);
            }
        }finally {
            writeLock.unlock();
        }
    }

    public int size() {
        return cache.size();
    }

    private void removeAfterExpireTime(K key,long expireTime){
        scheduledExecutorService.schedule(new Runnable() {
            @Override
            public void run() {
                cache.remove(key);
                removeKey(key);
            }
        },expireTime, TimeUnit.MILLISECONDS);
    }

    private void moveToHead(DLinkNode node){
        removeNode(node);
        addToHead(node);
    }

    private void removeKey(K key){
        DLinkNode<K,V> node = (DLinkNode<K,V>)cache.get(key);
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void removeNode(DLinkNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void addToHead(DLinkNode node){
        node.pre = this.head;
        node.next = this.head.next;
        this.head.next.pre = node;
        this.head.next = node;
    }

    private DLinkNode removeTail(){
        DLinkNode rNode = this.tail.pre;
        removeNode(rNode);
        return rNode;
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容