什么是LRU算法？如何实现LRU算法？

LRU (Least recently used) 最近最少使用，如果数据最近被访问过，那么将来被访问的几率也更高。 LRU算法的设计原则是如果一个数据近期没有被访问到，那么之后一段时间都不会被访问到。所以当元素个数达到限制的值时，优先移除距离上次使用时间最久的元素。 可以使用双向链表Node+HashMap<String, Node>来实现，每次访问元素后，将元素移动到链表头部，当元素满了时，将链表尾部的元素移除，HashMap主要用于根据key获得Node以及添加时判断节点是否已存在和删除时快速找到节点。 PS:使用单向链表能不能实现呢，也可以，单向链表的节点虽然获取不到pre节点的信息，但是可以将下一个节点的key和value设置在当前节点上，然后把当前节点的next指针指向下下个节点，这样相当于把下一个节点删除了 ```java //双向链表 public static class ListNode { String key;//这里存储key便于元素满时，删除尾节点时可以快速从HashMap删除键值对 Integer value; ListNode pre = null; ListNode next = null; ListNode(String key, Integer value) { this.key = key; this.value = value; } } ListNode head; ListNode last; int limit=4; HashMap<String, ListNode> hashMap = new HashMap<String, ListNode>(); public void add(String key, Integer val) { ListNode existNode = hashMap.get(key); if (existNode!=null) { //从链表中删除这个元素 ListNode pre = existNode.pre; ListNode next = existNode.next; if (pre!=null) { pre.next = next; } if (next!=null) { next.pre = pre; } //更新尾节点 if (last==existNode) { last = existNode.pre; } //移动到最前面 head.pre = existNode; existNode.next = head; head = existNode; //更新值 existNode.value = val; } else { //达到限制，先删除尾节点 if (hashMap.size() == limit) { ListNode deleteNode = last; hashMap.remove(deleteNode.key); //正是因为需要删除，所以才需要每个ListNode保存key last = deleteNode.pre; deleteNode.pre = null; last.next = null; } ListNode node = new ListNode(key,val); hashMap.put(key,node); if (head==null) { head = node; last = node; } else { //插入头结点 node.next = head; head.pre = node; head = node; } } } public ListNode get(String key) { return hashMap.get(key); } public void remove(String key) { ListNode deleteNode = hashMap.get(key); ListNode preNode = deleteNode.pre; ListNode nextNode = deleteNode.next; if (preNode!=null) { preNode.next = nextNode; } if (nextNode!=null) { nextNode.pre = preNode; } if (head==deleteNode) { head = nextNode; } if (last == deleteNode) { last = preNode; } hashMap.remove(key); } ```