LRU算法 O(1)时间复杂度

实现LRU算法，查找删除时间复杂度都为O(1)
LRU Cache是一个Cache置换算法，含义是“最近最少使用”，当Cache满（没有空闲的cache块）时，把满足“最近最少使用”的数据从Cache中置换出去，并且保证Cache中第一个数据是最近刚刚访问的

实现思路
利用hashmap加链表来实现这个原理
链表元素node由两个元素构成（key-value），在hashmap中存入node的key值，以及node；hashmap的构成为<Integer,Node>

为保证每次查找为O(1)并要判断双向链表里面是否含有元素，所以要将node设为两个值，key和value，其中node的key与map的值相同，当hashmap中存在key的时候，则双向链表中也存在key。利用这个特质，能完成查找删除都为O(1)

将最小使用的元素删除，核心就是每次插入的时候，都插入到链表的头结点；每次get一个元素时候，将get的那个元素删除，然后将元素插入到头结点

import java.util.HashMap;

public class LRU {


    int capacity;
    HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    Node head = null;
    Node end = null;

    public LRU(int capacity) {
        this.capacity = capacity;
    }

    /**
     * 每次使用的时候，就将用的元素删除，然后放到链表头部
     * @param key
     * @return
     */
    public int get(int key) {
        if (map.containsKey(key)) {
            Node n = map.get(key);
            remove(n);
            setHead(n);
            printNodes("get");
            return n.value;
        }
        printNodes("get");
        return -1;
    }


    public void remove(Node n) {
        if (n.pre != null) { //如果n不是头结点，将元素删除
            n.pre.next = n.next;
        } else {
            head = n.next;  //将n方法到头结点位置
        }

        if (n.next != null) {   //操作另外一个指针
            n.next.pre = n.pre;
        } else {
            end = n.pre;
        }

    }

    /**
     * 将元素设置成头结点
     * @param n
     */
    public void setHead(Node n) {
        //将n插入到头结点位置
        n.next = head;
        n.pre = null;

        if (head != null)
            head.pre = n;

        //将头结点设为n
        head = n;

        if (end == null)
            end = head;
    }

    /**
     * 对map插入操作
     * @param key
     * @param value
     */
    public void set(int key, int value) {
        //如果存在key，将元素放到头位置
        if (map.containsKey(key)) {
            Node old = map.get(key);
            old.value = value;
            remove(old);
            setHead(old);
        } else {
            //如果不存在 就插入头位置
            Node created = new Node(key, value);
            if (map.size() >= capacity) {
                map.remove(end.key);
                remove(end);
                setHead(created);

            } else {
                setHead(created);
            }

            map.put(key, created);
        }
        printNodes("set");
    }

    public void printNodes(String explain) {

        System.out.print(explain + ":" + head.toString());
        Node node = head.next;
        while (node != null) {
            System.out.print(node.toString());
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LRU lruCacheTest = new LRU(5);
        lruCacheTest.set(1, 1);
        lruCacheTest.set(2, 2);
        lruCacheTest.set(3, 3);
        lruCacheTest.set(4, 4);
        lruCacheTest.set(5, 5);
        System.out.println("lruCacheTest.get(1):" + lruCacheTest.get(1));
        lruCacheTest.set(6, 6);
        System.out.println("lruCacheTest.get(2):" + lruCacheTest.get(2));
    }

}

/**
 * 双向链表
 */

class Node {
    int key;
    int value;
    Node pre;
    Node next;

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

    @Override
    public String toString() {
        return this.key + "-" + this.value + " ";
    }


}