LRU算法

LRU(Least Recently Used)即最近最少使用算法，是一种缓存淘汰算法，在内存不足时，可以通过淘汰掉最久使用的元素，这样让新的元素可以加入进来。在Redis等缓存中间件中有广泛的使用，它的时间插入和删除时间复杂度都是O(1)。
下面通过实现一个简单的LRU算法。其实现原理是通过hash列表可以快速定位到元素，新增元素时，如果元素在hash列表中，则删除当前元素并转移到列表尾部，如果不在hash列表中则插入列表尾部。同理，获取元素的时候也是通过上述原理。

public class LRUCache {

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1,1);
        cache.put(2,2);
        System.out.println(cache.get(1));
        cache.put(3,3);

        System.out.println(cache.get(2));
        cache.put(4,4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }


    private final int capacity;

    private HashMap<Integer,Entry> map;

    private Entry head;

    private Entry tail;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>((int)(capacity/0.75 + 1),0.75f);
        head = new Entry(0,0);
        tail = new Entry(0,0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if(map.containsKey(key)) {
            Entry entry = map.get(key);
            popToTail(entry);
            return entry.value;
        }
        return -1;
    }


    public void put(int key,int value) {
        if (map.containsKey(key)) {
            Entry entry = map.get(key);
            entry.value = value;
            popToTail(entry);
        }else {
            Entry newEntry = new Entry(key,value);
            if(map.size() >= capacity) {
                Entry first = removeFirst();
                map.remove(first.key);
            }
            addToTail(newEntry);
            map.put(key,newEntry);
        }
    }

    class Entry {
        int key;
        int value;
        Entry prev;
        Entry next;

        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private void popToTail(Entry entry) {
        Entry prev = entry.prev;
        Entry next = entry.next;
        prev.next= next;
        next.prev = prev;
        Entry last = tail.prev;
        last.next = entry;
        tail.prev = entry;
        entry.prev = last;
        entry.next = tail;
    }

    private Entry removeFirst() {
        Entry first = head.next;
        Entry second = first.next;
        head.next = second;
        second.prev = head;
        return first;
    }

    private void addToTail(Entry entry) {
        Entry last = tail.prev;
        last.next = entry;
        tail.prev = entry;
        entry.prev = last;
        entry.next = tail;
    }
}