场景：
用户信息存在于数据库里，但是由于我们对用户系统的性能要求比较高，显然不能每一次请求都去数据库。所以可以在内存中创建一个哈希表作为缓存，每次查找一个用户的时候现在哈希表中查询，以此提高性能。但是当用户数据超过一定的数值时，会发生内存溢出，造成服务器宕机。
解决方法：
LRU全称 Least Recently Used ,也就是最近最少使用的意思，是一种内存管理算法，最早应用于Linux操作西永。
LRU算法基于一种假设：长期不被使用的数据，在未来被用到的几率不大。因此，当数据所占内存达到一定阈值时，我们要移除掉最近最少被使用的数据。
在LRU算法中，使用了一种有趣的数据结构，这种数据结构叫做哈希链表。
什么是哈希链表呢？
我们都知道，哈希链表是由若干个Key-value所组成，在逻辑上，这些Key-Value是无所谓排列顺序的，谁先谁后都一样。
在哈希链表中，这些Key-Value不再是彼此无关的存在，而是被一个链条串了起来，每一个Key-Value都具有它的前驱Key-Value、后继Key-Value，就像双向链表中的节点一样。这样一来，原本无序的哈希表拥有了固定的排列顺序。
依靠哈希链表的有序性，我们可以把Key-Value按照最后的使用时间来排序。
示例代码：
private Node head;
private Node end;
//缓存存储上限
private int limit;
private HashMap<String, Node> hashMap;
public LRUCache(int limit){this.limit=limit;hashMap=new HashMap<String, Node>();}
public String get(String key){Node node=hashMap.get(key);
if(node==null){return null;}
refreshNode(node);return node.value;}
public void put(String key,String value){Node node=hashMap.get(key);
if(node==null){
//如果key不存在，插入key-value
if(hashMap.size()>=limit){String oldKey=removeNode(head);
hashMap.remove(oldKey);}
node=new Node(key,value);
addNode(node);
hashMap.put(key,node);}else{ //如果key存在，刷新key-value
node.value=value;refreshNode(node);}}
public void remove(String key){
Node node=hashMap.get(key);
removeNode(node);
hashMap.remove(key);}
/**
* 刷新被访问的节点位置 * @param node 被访问的节点
*/
private void refreshNode(Node node){
//如果访问的是尾节点，无需移动节点 if (node == end ) { return ; }
//移除节点
removeNode(node);
//重新插入节点 addNode ( node ); }
/** * 删除节点 * @param node 要删除的节点 */
private String removeNode(Node node){
if(node==end){
//移除尾节点
end=end.pre;}else if(node==head){
//移除头节点 head = head . next ; } else {
//移除中间节点 node . pre . next = node . next ; node . next . pre = node . pre ; }
return node.key;}
/** * 尾部插入节点 * @param node 要插入的节点 */
private void addNode(Node node){
if(end!=null){
end.next=node;
node.pre=end;
node.next=null;}
end=node;
if(head==null){
head=node;
}}
class Node {
Node(String key, String value) {
this.key = key;
this.value = value;
}
public Node pre;
public Node next;
public String key;
public String value;
}
以上例代码非线程安全，如有需求，需要加上synchronized修饰符
对于刚才这种类似的需求也可以使用缓存数据库redis来实现，Redis底层也实现了类似于LRU的回收算法。
FIFO算法：
先进先出算法：即FIFO，通过缓存中的块进入队列的先后顺序进行淘汰和替换，先进入缓存的数据块最先被替换。
随机替换算法：
随机替换算法：顾名思义，就是通过随机获得一个需要被替换的块号，并用新的数据替换该块。
LFU算法：
最不经常使用算法：即LFU，这个算法需要记录每一个缓存块被访问的频率，每一次替换都从最低访问频率的数据块开始。
MRU算法：
最近最常使用算法，即MRU，这个算法会最先移除最近最常使用的数据块。
