算法 - lru（最近最少使用）

算法 - lru（最近最少使用）"/>

算法 - lru（最近最少使用）

实现该缓存满足如下两点:

1. get(key) - 如果该元素(总是正数)存在，将该元素移动到lru头部，并返回该元素的值，否则返回-1。
2. set(key,value) - 设置一个key的值为value(如果该元素存在),并将该元素移动到LRU头部。否则插入一个key,且值为value。如果在设置前检查到，该key插入后，会超过cache的容量，则根据LRU策略，删除最近最少使用的key。
   分析

需求：抽离出一个用户系统，向各个业务系统提供用户的基本信息。

解决：创建数据库的缓存层。该缓存层会移除最近最少被使用的数据，当缓存层数据所占内存达到一定阈值。

作用：移除最近最少被使用的数据，当缓存层数据所占内存达到一定阈值。

哈希链表(LinkedHashmap)

场景：按照最后的使用时间来排序，依靠哈希链表的有序性，
作用：使无序的哈希表拥有了固定的排列顺序。key-value被一个链条串了起来。具有它的前驱Key-Value、后继Key-Value，就像双向链表中的节点一样。

步骤

1. 缓存了4个用户，这4个用户是按照时间顺序依次从链表右端插入的。
2. 此时，业务方访问用户5，由于哈希链表中没有用户5的数据，我们从数据库中读取出来，插入到缓存当中。这时候，链表中最右端是最新访问到的用户5，最左端是最近最少访问的用户1。
3. 请求访问用户2，哈希链表中存在用户2的数据，①用户2从它的前驱节点和后继节点之间移除②重新插入到链表最右端。这时候，链表中最右端变成了最新访问到的用户2，最左端仍然是最近最少访问的用户1。
4. 请求修改用户4，①将用户4从它的前驱和后继节点之间移除②重新插入到链表最右端，并更新用户信息。
5. 访问用户6，缓存中没有，需要插入到哈希链表。假设缓存容量到上线，必须先删除最近最少访问的数据，那么位于哈希链表最左端的用户1就会被删除掉，然后把用户6插入到最右端。

代码

java中的LinkedHashMap对哈希链表做了很好的实现。我们现在自己写代码简单实现：

 package chapter6.part3;import java.util.HashMap;class Node {Node(String key, String value){this.key = key;this.value = value;}public Node pre; //前驱节点public Node next; //后置节点public String key; //节点的keypublic String value; //节点的value
}public class LRUCache {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>();}/*** 获取value通过key从容器中*/public String get(String key) {Node node = hashMap.get(key); //通过get“键”的形式进行值的获取if (node == null){return null;}refreshNode(node);return node.value;}/*** 移除key*/public void remove(String key) {Node node = hashMap.get(key);removeNode(node);hashMap.remove(key);}/*** 存放key*/public void put(String key, String value) {Node node = hashMap.get(key);if (node == null) {//如果key不存在，插入key-value 增加key-value if (hashMap.size() >= limit) {String oldKey = removeNode(head);  //删除节点，返回该节点的keyhashMap.remove(oldKey); //将该节点的}node = new Node(key, value);addNode(node);hashMap.put(key, node);}else {//如果key存在，刷新key-value 更新Key-valuenode.value = value;refreshNode(node);}}/*** 刷新被访问的节点位置* @param  node 被访问的节点*/private void refreshNode(Node node) {//如果访问的是尾节点，无需移动节点if (node == end) {return;}removeNode(node);  //改变节点的位置//重新插入节点到尾部addNode(node); //改变节点的位置,多出一个节点}/*** 改变节点的位置* @param  node 要删除的节点*/private String removeNode(Node node) {if(node == head && node == end){//移除唯一的节点head = null;end = null;}else if(node == end){//移除尾节点end = end.pre;end.next = null;}else if(node == head){//移除头节点head = head.next;head.pre = null;}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;}}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"));;}
}

Redis支持和LRU相关淘汰策略包括，volatile-lru 设置了过期时间的key参与近似的lru淘汰策略
allkeys-lru 所有的key均参与近似的lru淘汰策略