LRU缓存

LRU简介

构建双向链表，使用HashMap来进行contains。使用ReentrantLock来控制并发访问,当发生put或者get的请求，把对应的数据move到头部，当容量满了之后，淘汰末尾的数据；

代码实现

定义双向链表的节点

 class CacheNode<K, V>{
        CacheNode pre;
        CacheNode next;
        K key;
        V value;
        public CacheNode(K k, V v) {
            this.key=k;
            this.value=v;
        }
    }

声明LRU缓存

public class LRUCache<K, V> {
    private AtomicInteger currentCacheSize;
    private ReentrantLock lock;
    private int CacheCapcity;
    private CacheNode first;
    private CacheNode last;
    private HashMap<K,CacheNode> caches;

    public LRUCache(int size){
        currentCacheSize = new AtomicInteger(0);
        this.CacheCapcity = size;
        caches = new HashMap<K,CacheNode>(size);
        lock=new ReentrantLock();
    }

插入数据

  public void put(K k,V v){
        lock.lock();
        try{
            CacheNode cacheNode=caches.getOrDefault(k,new CacheNode<>(k,v));
            if (currentCacheSize.get()>caches.size()){
                removeLruCacheLast();
            }else {
                cacheNode.value=v;
                caches.put(k,cacheNode);
                currentCacheSize.incrementAndGet();
            }
            moveCacheNodeHead(cacheNode);
        } finally {
            lock.unlock();
        }

    }

插入数据

 public Optional<V> get(K k){
        lock.lock();
        try{
            return (Optional<V>) Optional.ofNullable(caches.get(k)).map(x->{
                moveCacheNodeHead(x);
                return Optional.of(x.value);
            }).orElse(Optional.empty());
        } finally {
            lock.unlock();
        }
    }

删除数据

  public Optional<V> remove(K k){
        lock.lock();
        try{
            return (Optional<V>) Optional.ofNullable(caches.get(k)).map(x->{
                removeLruCacheNode(x);
                caches.remove(k);
                return Optional.of(x.value);
            }).orElse(Optional.empty());
        } finally {
            lock.unlock();
        }
    }

淘汰末尾数据

 private void removeLruCacheLast() {
        if(last!=null){
           last= last.pre;
        }
    }

移动节点到头部

private void moveCacheNodeHead(CacheNode cacheNode) {
        if(first == cacheNode){
            return;
        }else{
            if(last!=null){
                if(cacheNode.next != null){
                    cacheNode.next.pre = cacheNode.pre;
                }
                if(cacheNode.pre != null){
                    cacheNode.pre.next = cacheNode.next;
                }
                if(cacheNode == last){
                    last= last.pre;
                }
            }else {
                first=last=cacheNode;
            }
        }
        cacheNode.next=first;
        first.pre = cacheNode;
        first = cacheNode;
        first.pre=null;
    }

删除节点

    private void removeLruCacheNode(CacheNode<? extends Object, ? extends Object> cacheNode) {
        if(cacheNode.next != null){
            cacheNode.next.pre = cacheNode.pre;
        }
        if(cacheNode.pre != null){
            cacheNode.pre.next = cacheNode.next;
        }
        if(cacheNode == last){
            last= last.pre;
        }
        if(cacheNode == first){
            first = cacheNode.next;
        }
    }