LRU算法

LRU(Least Recently Used)即最近最少使用算法扰才，是一種緩存淘汰算法谊惭，在內(nèi)存不足時叹话，可以通過淘汰掉最久使用的元素朝墩，這樣讓新的元素可以加入進來醉拓。在Redis等緩存中間件中有廣泛的使用，它的時間插入和刪除時間復雜度都是O(1)收苏。
下面通過實現(xiàn)一個簡單的LRU算法亿卤。其實現(xiàn)原理是通過hash列表可以快速定位到元素，新增元素時鹿霸，如果元素在hash列表中排吴，則刪除當前元素并轉(zhuǎn)移到列表尾部，如果不在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;
    }
}