LRU和LFU算法_lru算法和lfu

在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的思路，效率可能比上述要慢，就暂时不写了。