一、LRU算法

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

二、Java代码实现

public class LRUCache {    class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int _key, int _value) {key = _key; value = _value;}    }    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();    private int size;    private int capacity;    private DLinkedNode head, tail;    public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head;    }    public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) {     return -1; } // 如果 key 存在，先通过哈希表定位，再移到头部 moveToHead(node); return node.value;    }    public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) {     // 如果 key 不存在，创建一个新的节点     DLinkedNode newNode = new DLinkedNode(key, value);     // 添加进哈希表     cache.put(key, newNode);     // 添加至双向链表的头部     addToHead(newNode);     ++size;     if (size > capacity) {  // 如果超出容量，删除双向链表的尾部节点  DLinkedNode tail = removeTail();  // 删除哈希表中对应的项  cache.remove(tail.key);  --size;     } } else {     // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部     node.value = value;     moveToHead(node); }    }    private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node;    }    private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev;    }    private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node);    }    private DLinkedNode removeTail() { DLinkedNode res = tail.prev; removeNode(res); return res;    }}