LRU、LFU 内存淘汰算法的设计与实现

1、背景介绍

LRU、LFU都是内存管理淘汰算法，内存管理是计算机技术中重要的一环，也是多数操作系统中必备的模块。应用场景：假设 给定你一定内存空间，需要你维护一些缓存数据，LRU、LFU就是在内存已经满了的情况下，如果再次添加新的数据，该淘汰哪些数据来留出新数据的内存空间？？？

2、LRU(least recently used)

LRU(east recently used)，即最近最少使用 ，也就是说 在内存满的情况下，将会淘汰很久都没有使用过的数据。例如 leetcode 146题。

需求：现在需要设计一个算法，使得插入新数据、获取已经存入的数据，使得平均时间复杂度O(1)。

设计思路：因为插入、获取数据时，都会更新时间戳，还需要使得平均时间复杂度O(1)，可以使用双链表+哈希表的方式来存储。

如上图，哈希表里存储 键与双链表节点，双链表的head表示最近使用过的数据，tail表示很久都没使用过的数据。

• 插入数据时，在哈希表建立key与Node节点，然后把Node节点插入双链表的头部位置。

• 获取数据时，从哈希表拿到Node节点，然后把Node节点从双链表中分离出来，插入双链表的头部位置即可。

  

以上两个步骤，时间复杂度都是O(1)。所以符合题意。

代码如下：

// lc146题 直接能过的代码
class LRUCache {// LRU，最近最少使用// 用双链表节点包装进行连接private HashMap<Integer, Node> map; // 哈希表，存储key与双链表节点private int maxSize; // 缓存的最大容量private Node head, tail; // 头部是最近使用的，尾部 是很久没使用的private static class Node { // 双链表节点int key, val;Node left, right;public Node(int k, int v) {key = k;val = v;}}public LRUCache(int capacity) {map = new HashMap<>();maxSize = capacity;}public int get(int key) {if(!map.containsKey(key)) return -1;Node node = map.get(key);if (node == head) return node.val;apart(node); //分离出node节点node.right = head; // 插入到双链表的头部位置head.left = node;head = node;return node.val;}public void put(int key, int value) {if (!map.containsKey(key)) {Node node = new Node(key, value);node.right = head;if (head != null) head.left = node;if (tail == null) tail = node;head = node;map.put(key, node);if (map.size() > maxSize) { // 容量超了，删除双链表的尾部元素if (tail.left != null) {tail.left.right = null;}map.remove(tail.key);Node pre = tail.left;tail.left = null;tail = pre;}} else {Node node = map.get(key);node.val = value;get(key); // 调用get，使其向前移动}}// node的左右两边连接，将node抽离出private void apart(Node node) {node.left.right = node.right;if (node.right != null) {node.right.left = node.left;}if (node == tail) {tail = node.left;}node.left = node.right = null;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

3、LFU(least frequancy used)

LFU(least frequancy used), 即不常用算法，按照每个数据的访问次数来判断数据的使用情况。如果一个数据在近一段时间内没有被访问或者被访问的可能性小，则会被淘汰。（简单点说，就是按照“使用频率”来分级的）例题：leetcode 460题

需求：现在需要设计一个算法，使得插入、获取数据的平均时间复杂度O(1)。

设计思路：按照使用频率进行划分，相同频率的数据放在同一个“桶”内，从左往右频率逐渐升高；而桶内部是从上往下，按照插入桶内的时间来排序，新插入的节点在桶的顶部，很久之前插入的节点在桶的底部，如下图所示：

注意：当内存满了的时候，会删除 频率最低的桶内，最后的一个数据节点。

代码实现如下：

public class LFUCache {public LFUCache(int K) {capacity = K;size = 0;records = new HashMap<>();heads = new HashMap<>();headList = null;}private int capacity; // 缓存的大小限制，即Kprivate int size; // 缓存目前有多少个节点private HashMap<Integer, Node> records;// 表示key(Integer)由哪个节点(Node)代表private HashMap<Node, NodeList> heads; // 表示节点(Node)在哪个桶(NodeList)里private NodeList headList; // 整个结构中位于最左的桶// 节点的数据结构public static class Node {public Integer key;public Integer value;public Integer times; // 这个节点发生get或者set的次数总和public Node up; // 节点之间是双向链表所以有上一个节点public Node down;// 节点之间是双向链表所以有下一个节点public Node(int k, int v, int t) {key = k;value = v;times = t;}}// 桶结构public static class NodeList {public Node head; // 桶的头节点public Node tail; // 桶的尾节点public NodeList last; // 桶之间是双向链表所以有前一个桶public NodeList next; // 桶之间是双向链表所以有后一个桶public NodeList(Node node) {head = node;tail = node;}// 把一个新的节点加入这个桶，新的节点都放在顶端变成新的头部public void addNodeFromHead(Node newHead) {newHead.down = head;head.up = newHead;head = newHead;}// 判断这个桶是不是空的public boolean isEmpty() {return head == null;}// 删除node节点并保证node的上下环境重新连接public void deleteNode(Node node) {if (head == tail) {head = null;tail = null;} else {if (node == head) {head = node.down;head.up = null;} else if (node == tail) {tail = node.up;tail.down = null;} else {node.up.down = node.down;node.down.up = node.up;}}node.up = null;node.down = null;}}// removeNodeList：刚刚减少了一个节点的桶// 这个函数的功能是，判断刚刚减少了一个节点的桶是不是已经空了。// 1）如果不空，什么也不做//// 2)如果空了，removeNodeList还是整个缓存结构最左的桶(headList)。// 删掉这个桶的同时也要让最左的桶变成removeNodeList的下一个。//// 3)如果空了，removeNodeList不是整个缓存结构最左的桶(headList)。// 把这个桶删除，并保证上一个的桶和下一个桶之间还是双向链表的连接方式//// 函数的返回值表示刚刚减少了一个节点的桶是不是已经空了，空了返回true；不空返回falseprivate boolean modifyHeadList(NodeList removeNodeList) {if (removeNodeList.isEmpty()) {if (headList == removeNodeList) {headList = removeNodeList.next;if (headList != null) {headList.last = null;}} else {removeNodeList.last.next = removeNodeList.next;if (removeNodeList.next != null) {removeNodeList.next.last = removeNodeList.last;}}return true;}return false;}// 函数的功能// node这个节点的次数+1了，这个节点原来在oldNodeList里。// 把node从oldNodeList删掉，然后放到次数+1的桶中// 整个过程既要保证桶之间仍然是双向链表，也要保证节点之间仍然是双向链表private void move(Node node, NodeList oldNodeList) {oldNodeList.deleteNode(node);// preList表示次数+1的桶的前一个桶是谁// 如果oldNodeList删掉node之后还有节点，oldNodeList就是次数+1的桶的前一个桶// 如果oldNodeList删掉node之后空了，oldNodeList是需要删除的，所以次数+1的桶的前一个桶，是oldNodeList的前一个NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.last : oldNodeList;// nextList表示次数+1的桶的后一个桶是谁NodeList nextList = oldNodeList.next;if (nextList == null) {NodeList newList = new NodeList(node);if (preList != null) {preList.next = newList;}newList.last = preList;if (headList == null) {headList = newList;}heads.put(node, newList);} else {if (nextList.head.times.equals(node.times)) {nextList.addNodeFromHead(node);heads.put(node, nextList);} else {NodeList newList = new NodeList(node);if (preList != null) {preList.next = newList;}newList.last = preList;newList.next = nextList;nextList.last = newList;if (headList == nextList) {headList = newList;}heads.put(node, newList);}}}public void put(int key, int value) {if (capacity == 0) {return;}if (records.containsKey(key)) {Node node = records.get(key);node.value = value;node.times++;NodeList curNodeList = heads.get(node);move(node, curNodeList);} else {if (size == capacity) {Node node = headList.tail;headList.deleteNode(node);modifyHeadList(headList);records.remove(node.key);heads.remove(node);size--;}Node node = new Node(key, value, 1);if (headList == null) {headList = new NodeList(node);} else {if (headList.head.times.equals(node.times)) {headList.addNodeFromHead(node);} else {NodeList newList = new NodeList(node);newList.next = headList;headList.last = newList;headList = newList;}}records.put(key, node);heads.put(node, headList);size++;}}public int get(int key) {if (!records.containsKey(key)) {return -1;}Node node = records.get(key);node.times++;NodeList curNodeList = heads.get(node);move(node, curNodeList);return node.value;}
}