LRU缓存实现

第一种方式，使用LinkedHashMap

package com.lru;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author Join
 * @date 2018/4/9 14:41
 */

/**
 * 1. 新数据插入到链表头部；
 2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
 3. 当链表满的时候，将链表尾部的数据丢弃。

 利用LinkedHashMap实现简单的缓存， 必须实现removeEldestEntry方法
 */
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(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 put(K key, V value) {
        try {
            lock.lock();
            return super.put(key, value);
        } finally {
            lock.unlock();
        }
    }

    @Override
    public int size() {
        try {
            lock.lock();
            return super.size();
        } finally {
            lock.unlock();
        }
    }

    @Override
    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();
        }
    }
}

第二种实现方式：链表+HashMap

package com.lru;


import java.util.*;

public class LruCache<K,V> {
    private int currentCacheSize;
    private int CacheCapcity;
    private HashMap<K,CacheNode> caches;
    private CacheNode first;
    private CacheNode last;

    public LruCache(int size){
        currentCacheSize=0;
        this.CacheCapcity=size;
        caches=new HashMap <K,CacheNode>(size);

    }

    public void put(K k,V v){
        CacheNode node=caches.get(k);
        if(node==null){
            if(caches.size()>=CacheCapcity){
                caches.remove(last.key);
                removeLast();
            }
            node=new CacheNode();
            node.key=k;
        }

        node.value=v;
        moveToFirst(node);
        caches.put(k,node);

    }


    public Object get(K k){
        CacheNode node=caches.get(k);
        if(node==null){
            return null;
        }
        moveToFirst(node);
        return node.value;
    }

    public Object remove(K k){
        CacheNode node=caches.get(k);
        if(node!=null){
            if(node.pre!=null){
                node.pre.next=node.next;
            }
            if(node.next!=null){
                node.next.pre=node.pre;

            }
            if(node==first){
                first=node.next;
            }
            if(node==last){
                last=node.pre;
            }
        }
        return caches.remove(k);

    }

    public void clear(){
        first=null;
        last=null;
        caches.clear();
    }

    private void moveToFirst(CacheNode node){
        if(first==node){
            return;
        }
        if(node.next!=null){
            node.pre.next=node.next;
        }
        if(node.pre!=null){
            node.pre.next=node.next;
        }
        if(node==last){
            last=last.pre;
        }

        if(first==null||last==null){
            first=last=node;
            return;
        }
        node.next=first;
        first.pre=node;
        first=node;
        first.pre=null;

    }


    public void removeLast(){
        if(last!=null){
            last=last.pre;
            if(last==null){
                first=null;
            }else {
                last.next=null;
            }
        }
    }


    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        CacheNode node=first;
        while (node!= null){
            sb.append(String.format("%s:%s",node.key,node.value));
            node=node.next;
        }
        return sb.toString();

    }
}


class CacheNode {
    CacheNode pre;
    CacheNode next;
    Object key;
    Object value;

    public CacheNode() {

    }

}

测试用例：

public class Test {
    public static void main(String[] args) {

        LruCache<Integer,String> lru = new LruCache<Integer,String>(3);

        lru.put(1, "a");    // 1:a
        System.out.println(lru.toString());
        lru.put(2, "b");    // 2:b 1:a
        System.out.println(lru.toString());
        lru.put(3, "c");    // 3:c 2:b 1:a
        System.out.println(lru.toString());
        lru.put(4, "d");    // 4:d 3:c 2:b
        System.out.println(lru.toString());
        lru.put(1, "aa");   // 1:aa 4:d 3:c
        System.out.println(lru.toString());
        lru.put(2, "bb");   // 2:bb 1:aa 4:d
        System.out.println(lru.toString());
        lru.put(5, "e");    // 5:e 2:bb 1:aa
        System.out.println(lru.toString());
        lru.get(1);         // 1:aa 5:e 2:bb
        System.out.println(lru.toString());
        lru.remove(11);     // 1:aa 5:e 2:bb
        System.out.println(lru.toString());
        lru.remove(1);      //5:e 2:bb
        System.out.println(lru.toString());
        lru.put(1, "aaa");  //1:aaa 5:e 2:bb
        System.out.println(lru.toString());
    }
}