浅析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; } public static void main(String[] args) { LRUCache lruCache = new LRUCache(5); lruCache.put("001", "用户1信息"); lruCache.put("002", "用户1信息"); lruCache.put("003", "用户1信息"); lruCache.put("004", "用户1信息"); lruCache.put("005", "用户1信息"); lruCache.get("002"); lruCache.put("004", "用户2信息更新"); lruCache.put("006", "用户6信息"); System.out.println(lruCache.get("001")); System.out.println(lruCache.get("006")); }

以上例代码非线程安全，如有需求，需要加上synchronized修饰符

对于刚才这种类似的需求也可以使用缓存数据库redis来实现，Redis底层也实现了类似于LRU的回收算法。

FIFO算法：

先进先出算法：即FIFO，通过缓存中的块进入队列的先后顺序进行淘汰和替换，先进入缓存的数据块最先被替换。

随机替换算法：

随机替换算法：顾名思义，就是通过随机获得一个需要被替换的块号，并用新的数据替换该块。

LFU算法：

最不经常使用算法：即LFU，这个算法需要记录每一个缓存块被访问的频率，每一次替换都从最低访问频率的数据块开始。

MRU算法：

最近最常使用算法，即MRU，这个算法会最先移除最近最常使用的数据块。