实现lru 缓存详解编程语言

思路：用map+链表实现，map用来提高查询速度，链表用来存放元素。链表头放入最新的元素，表尾为最老元素。访问cache命中，或者cache满写入时都需要对链表内容和map进行调整。

JDK里面有一个LinkedHashMap就是基于这个思路实现的。

    public class LRUCache {   
        static class Node {   
            int key;   
            int value;   
       
       
            @Override   
            public String toString() {   
                return "Node{" +   
                        "key=" + key +   
                        ", value=" + value +   
                        '}';   
            }   
        }   
       
       
        static private LinkedList<Node> cache;   
        static private int cap;   
        static private Node indexMap[];   
       
        public LRUCache(int capacity) {   
            cache = new LinkedList<Node>();   
            indexMap = new Node[100000];   
            cap = capacity;   
        }   
       
        static public boolean isFull() {   
            return cache.size() == cap;   
        }   
       
        static public Node find(int key) {   
            if (cache.isEmpty())   
                return null;   
            Node tar = null;   
       
            if ((tar = indexMap[key]) == null)   
                return null;   
       
            cache.remove(tar);   
            cache.addFirst(tar);   
            return tar;   
       
        }   
       
         public int get(int key) {   
            Node node = find(key);   
            if (node == null) {   
                return -1;   
            }   
            return node.value;   
        }   
       
         public void set(int key, int value) {   
            Node node = null;   
            if ((node = find(key)) != null) {   
                node.value = value;   
                return;   
            }   
       
            //not find the element   
       
            if (isFull()) {   
                indexMap[cache.getLast().key] = null;   
                cache.removeLast();   
            }   
       
       
            Node newNode = new Node();   
            newNode.key = key;   
            newNode.value = value;   
            cache.addFirst(newNode);   
            indexMap[key] = newNode;   
       
        }   
    }