LRU缓存

1.LRU 缓存机制可以通过哈希表辅以双向链表实现，用一个哈希表和一个双向链表维护所有在缓存中的键值对

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); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        int b = lRUCache.get(2);    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 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实现线程安全的 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;
    }

}

3. 实现一个线程安全并且带有过期时间的 LRU 缓存
   ScheduledExecutorService ：定时器线程池定时删除缓存

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