LRU理解
LRU算法是页面置换算法的一种，英文为Least Recently Used。中文翻译叫最近最少使用。这个翻译太狗屁了，不好理解。不过可以看一下LRU算法数据的插入规则，就知道到底什么是LRU了。
依次插入4 7 0 7 1 0 1 2 1 2 6

看这个应该很容易理解，大概就是按时间顺序排队，时间最近的页面排在最前面，时间远的排在后面，最近的又重复的，提到最前面，超出就淘汰出内存。

LRU实现
数据插入的逻辑

因为在缓存页面时，需要保留页面名称和页面的内容，我们就假设，页面置换时每个页面有两个关键字段，页面名称和页面内容。
依据上面的假设，需要注意：
1>如果链表中不存在页面名称的数据，需要判断链表的容量，新增链表结点时，容量超出链表的容量，需要淘汰链表的尾结点数据。否则直接新增结点。
2>如果链表中粗在页面名称的数据，则可能页面名称的结点在链表中间，也可能在链表头部。为了思考简单，我们直接删除原来的结点，在链表头部新增结点。删除结点是，需要重新修改原来结点前后结点的关系。
3>新增节点时，需要修改头节点和新增结点，以及原来头结点的后续节点和新增结点的关系。
具体实现

import java.util.HashMap;import java.util.Map;/*** LRU算法* 基于Map和链表实现* @param <T>*/
public class LRUCache2<T> {private int capacity;private Map<String, Node> data = new HashMap<>();private Node head;private Node tail;/*** 构造方法* @param capacity*/public LRUCache2(int capacity) {this.capacity = capacity;head = new Node();tail = new Node();head.next = tail;tail.pre = head;}public <T> void add(String id, T value) {//存在元结点，则修改元结点关系Node<T> currentNode = data.get(id);//数据不存在if (currentNode == null) {//判断容量超出if (data.size() > capacity) {Node pre = tail.pre;tail = pre;data.remove(id);}//数据存在} else {Node<T> pre = currentNode.pre;Node<T> next = currentNode.next;if (pre != null) {pre.next = next;}if (next != null) {next.pre = pre;}}//插入链表首部currentNode = new Node(value);Node<T> next = head.next;head.next = currentNode;//修改链表前后结点currentNode.pre = head;currentNode.next = next;next.pre = currentNode;//data.put(id, currentNode);}public  T get(String id) {Node<T> n = data.get(id);if (n != null) {add(id, n.value);return n.value;}return null;}public void print() {Node data = head;while (data != null) {System.out.println(data.value);data = data.next;}}class Node<T> {Node pre;Node next;T value;public Node() {}public Node(T value) {this.value = value;}}public static void main(String[] args) {LRUCache2<Integer> cache = new LRUCache2(1024);cache.add("7", 7);cache.add("0", 0);cache.add("1", 1);cache.add("2", 2);cache.add("0", 0);cache.add("3", 3);cache.add("0", 0);cache.add("4", 4);cache.print();cache.get("0");System.out.println("----------------");cache.print();}
}