浅析LRU算法及常用算法

场景：

用户信息存在于数据库里，但是由于我们对用户系统的性能要求比较高，显然不能每一次请求都去数据库。所以可以在内存中创建一个哈希表作为缓存，每次查找一个用户的时候现在哈希表中查询，以此提高性能。但是当用户数据超过一定的数值时，会发生内存溢出，造成服务器宕机。

解决方法：

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，这个算法会最先移除最近最常使用的数据块。

浅析LRU算法及常用算法