实现lru 缓存，lru缓存,思路：用map+链表实现

实现lru 缓存，lru缓存,思路：用map+链表实现

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

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

LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.ShowTags```java 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;    }  }

```