LRU和LFU算法

大家好，欢迎来到IT知识分享网。

在redis的学习中，了解到了两种缓存清理算法，分别是LRU和LFU，在此针对这两种算法进行学习。

1.LRU算法

LRU（Least Recently Used）称为最近最少使用算法。基本的思想是：长期不被使用的数据，在未来被用到的几率也不大，因此当新的数据进来时，就可以优先将这些数据替换掉。

1.1 LRU算法中数据结构

哈希链表，哈希表我们知道是又多个k-v键值对组成的，而哈希链表就是将这些节点在连接起来，每个节点都有一个前驱节点和后继节点，就像双向链表中的节点一样，使得哈希表拥有了固定的排列顺序。基于这个有序性，就可以把k-v键值对按照使用时间的先后顺序进行排列。

 1.2 LRU算法思路

维护一个哈希表和双向链表，哈希表负责存储数据，双向链表维护顺序。当添加元素的时候，新的元素添加到双向链表的末尾，访问元素时，如果不存在则跳过，如果存在，则将该元素从双向链表中取出，然后在插入到链表的末尾。当需要进行清理的时候，优先清理链表头部的数据。（越靠近链表的头部，说明数据越少使用，因此可以将该数据优先删除—- 头尾无所谓，主要是有一头代表数据不经常使用）

1.3 LRU代码实现

public class LRUCache{ private Map<Integer, ValueNode> map; private int capacity; private ValueNode head; private ValueNode tail; // LRU缓存构造器，初始化容量，map，头节点和尾节点 public LRUCache(int capacity) { this.capacity = capacity; map = new HashMap<>(); head = new ValueNode(-1, -1); tail = new ValueNode(-1, -1); head.right = tail; tail.left = head; } // get方法，如果key存在，取key的时候将节点从原来的位置删除，然后插入到最后 public int get(int key) { if (map.containsKey(key)) { ValueNode valueNode = map.get(key); refreshNode(valueNode); return valueNode.value; } return -1; } // put方法，如果key存在，则替换原来的value，如果不存在，则put进去 // 如果map中的数量已经超过了capacity，则删除最前面的节点，同时记得要在map中把这个节点删除！！！！ // 最后刷新双向链表，将节点移至双向列表的最后面 public void put(int key, int value) { ValueNode valueNode = null; if (map.containsKey(key)) { valueNode = map.get(key); valueNode.value = value; } else { valueNode = new ValueNode(key, value); if (map.size() >= capacity) { map.remove(head.right.key); deleteNode(head.right); } map.put(key, valueNode); } refreshNode(valueNode); } // 刷新双向列表，其实就是先吧当前节点在原链表中删除，然后在插入到链表的最后面 private void refreshNode(ValueNode node) { deleteNode(node); ValueNode left = tail.left; node.right = tail; node.left = left; left.right = node; tail.left = node; } // 删除双向链表中的节点 private void deleteNode(ValueNode node) { if (node.right != null) { ValueNode right = node.right; right.left = node.left; node.left.right = right; } } // 定义双向链表节点，包括键值，左右节点，构造器 class ValueNode { // 定义键值 int key; int value; // 定义左右节点 ValueNode left; ValueNode right; public ValueNode(int key, int value) { this.key = key; this.value = value; } } } 

2.LFU算法

LFU（least frequently used）最近最不经常使用的算法，对于每个数据，维护其使用的次数以及最近的使用时间，删除的策略是：优先删除使用次数最少的数据，如果存在多个使用次数相同的数据，则优先删除最远一次使用的数据。（描述有点拗口，可以这样理解：a,b两个个资源，其中a使用了5次，b使用了2次，则优先删除b，如果ab都使用了5次，a上次使用时5s前，b上次使用时2s前，则优先删除a）

2.1 LFU的数据结构

LFU数据结构相比较LRU会复杂很多：首先仍是key-value哈希表，这样set和get的时间复杂度都是O(1), 此外，还维护另外一个time-LinkList哈希表，这个哈希表用于存储每个key-value的使用次数，其中value是一个双向链表，维护着每个数据的使用顺序（类似LRU）；

2.2 LFU算法思路

维护两个哈希表，其中key-value哈希表用于存储数据，key就是key，value记录key.value以及使用次数

time-value哈希表用于存储数据使用次数和使用先后顺序的链表。key为数据的使用次数，value是一个双向链表，记录着相同使用次数的数据使用顺序的先后。

读取数据：

key-value哈希表判断是否存在该数据，不存在在返回-1；如果存在，返回这个数据的值，同时在time-value哈希表进行维护：

1. 将该数据从当前次数下的双向链表中删除，如果删除后链表为空，将链表从time-value哈希表中删除（key的值为原来的time）；
2. 将该数据插入当前次数+1的双向链表中，如果这个链表不存在，则创建一个新的双向链表，然后插入到time-value哈希表中（key的值是原来的time+1）

插入数据：

更新旧数据：

思路和读取数据基本一致：

1. 将该数据从当前次数下的双向链表中删除，如果删除后链表为空，将链表从time-value哈希表中删除（key的值为原来的time）；
2. 将该数据插入当前次数+1的双向链表中，如果这个链表不存在，则创建一个新的双向链表，然后插入到time-value哈希表中（key的值是原来的time+1）
3. key-value哈希表中更新数据

插入新数据：

1. 插入数据前先判断是否需要删除数据 ：如果需要删除，则获取time-value中使用频率最小的链表，删除链表最前端的数据。
2. 添加新节点：
   1. 将新的数据插入到key-value哈希表中
   2. 判断key为1的数据在time-value哈希表中是否存在
      1. 存在：将该数据插入到链表中
      2. 不存在：创建一个新的链表，插入该数据，并在time-value哈希表插入该数据，其中key的值为1

维护time-value哈希表中key的最小值：

定义一个全局变量minTimes，分析什么时候对这个数据进行更新：

1. 每次插入新的数据，minTimes的值要更新为1；
2. 每次更新节点的访问频率时，如果原访问频率刚好是最小访问次数，并且更新完后原访问频率的对应链表为空，则minTimes要加1；

2.3 LFU算法代码

下面代码也是调试很久才跑通所有用例，代码结构未优化。

package LRU_LFU; import java.util.HashMap; import java.util.Map; public class LFUCache { private Map<Integer, ValueNode> kvMap; private Map<Integer, LinkNodeList> timeMap; private int capacity; private int minTimes = 1; // 初始化cache，定义capacity public LFUCache(int capacity) { if (capacity <= 0) { return; } this.capacity = capacity; kvMap = new HashMap<>(); timeMap = new HashMap<>(); } // 从缓存中获取数据，如果不存在，则返回负一 public int get(int key) { if (kvMap.containsKey(key)) { // 如果存在，则将该节点的访问次数加1，在timeMap中进行维护 ValueNode node = kvMap.get(key); deleteNode4LinkList(node); node.count++; insertNode4LinkList(node); return node.value; } else { return -1; } } // 给链表中添加节点，然后维护timeMap private void insertNode4LinkList(ValueNode node) { LinkNodeList linkNodeList; if (timeMap.containsKey(node.count)) { linkNodeList = timeMap.get(node.count); } else { linkNodeList = new LinkNodeList(); } linkNodeList.insertNode(node); timeMap.put(node.count, linkNodeList); } // 删除链表中的节点 private void deleteNode4LinkList(ValueNode node) { LinkNodeList linkNodeList = timeMap.get(node.count); linkNodeList.deleteNode(node); if (linkNodeList.isEmpty()) { // 如果删除节点后链表为空，则将链表从timeMap中移除 timeMap.remove(node.count); if (minTimes == node.count) { // 如果移除的链表key恰好是最小访问次数，则最小访问次数要加1 this.minTimes = minTimes +1; } } } // 给缓存中加入数据 public void put(int key, int value) { if (capacity <=0) { return; } if (kvMap.containsKey(key)) { // 如果存在则将该节点的访问次数加1，更新value，然后维护kvMap和timeMap ValueNode node = kvMap.get(key); deleteNode4LinkList(node); node.count++; node.value = value; insertNode4LinkList(node); kvMap.put(key, node); } else { if (kvMap.size() == capacity) { removeNodes(); } ValueNode node = new ValueNode(key, value, 1); if (timeMap.containsKey(1)) { LinkNodeList linkNodeList = timeMap.get(1); linkNodeList.insertNode(node); timeMap.put(node.count, linkNodeList); } else { LinkNodeList linkNodeList = new LinkNodeList(); linkNodeList.insertNode(node); timeMap.put(node.count, linkNodeList); this.minTimes = 1; } kvMap.put(key, node); } } // 清理最少使用次数的节点，如果次数相同，则清理最远一次操作的节点 private void removeNodes() { LinkNodeList linkNodeList = timeMap.get(minTimes); ValueNode valueNode = linkNodeList.head.right; int key = valueNode.key; linkNodeList.deleteNode(valueNode); if (linkNodeList.isEmpty()) { timeMap.remove(minTimes); } kvMap.remove(key); } // 定义双向链表中的节点，包括键值,计数器，左右节点，构造器 class ValueNode { // 定义键值 int key; int value; int count; // 定义左右节点 ValueNode left; ValueNode right; // 构造器 public ValueNode(int key, int value, int count) { this.key = key; this.value = value; this.count = count; } } // 定义双向链表，维护两个虚拟节点，作为头节点和尾节点 class LinkNodeList { private final ValueNode head; private final ValueNode tail; // 双向链表定义头和尾，并且头尾相连接。 public LinkNodeList() { head = new ValueNode(-1, -1, 1); tail = new ValueNode(-1, -1, 1); head.right = tail; tail.left = head; } // 双向链表中插入节点，插入的位置在链表的末尾 public void insertNode(ValueNode node) { ValueNode left = tail.left; node.right=tail; node.left=left; left.right=node; tail.left=node; } // 双向链表删除节点，删除的节点时是链表的头部 public void deleteNode(ValueNode node) { ValueNode right = node.right; ValueNode left = node.left; left.right =right; right.left=left; node.right=null; node.left=null; } // 判断双向链表是否为空 public boolean isEmpty() { return head.right == tail; } } } 

此外，还有一种仿照LRU写LFU的思路，效率可能比上述要慢，就暂时不写了。