LFU算法的Java代码实现
站长
· 阅读数 44
算法简介
算法基础解释，已经会的可以直接跳过哈。
LFU是最近不经常使用算法。
听到这个名字，就问你迷糊不？
还有个类似的叫LRU算法，叫最近最少使用算法。它的代码实现，本人实现了一波，有兴趣可以看下：
https://juejin.cn/post/7226604941728841765
好了，两者的应用场景基本一致，大多数都是缓存。
本质上就是当我缓存的地方满了，现在又要添新的值，需要舍弃哪个旧值？
LRU就是舍弃缓存数据中最后一次访问时间最早的数据。（注重时间）
LFU即使舍弃访问次数最少的数据中最后一次访问时间最少的数据（注重次数+时间）
什么？你还不懂？那我可要举例子了。
玩过游戏吧，如果背包满了，现在又捡到了新的装备，所以要丢掉背包中的一个物品来放新的。
LRU就是每捡到一个东西就放到背包最后面，然后过程中使用的也放在后面。这样我要扔东西就是直接扔最前面那一个就可以了。
LFU就是：使用了两次的物品就是比使用1次的重要，我得先扔使用1次的。以此类推。如果多个相同次数，扔最后使用时间最早的
你甚至可以理解为LFU就是先按照使用次数筛了下数据，再按照LRU选择
如何实现呢？
首先，既然先按照使用次数进行筛选，那么肯定要知道某个调用次数下都有哪些节点吧。
所以数据结构是Map<调用次数，双向链表>。双向列表的原因是便于将某个节点删除。
由于双向队列的实现是O（n）删除节点，所以一般是自行实现双端队列。
同时添加新数据要放在队首，淘汰要从队尾拿，所以为了O(1),要维护到队头节点和队尾节点的映射。
所以一般是采用两个Map来实现。
其次，为了能够在O（1）时间内得到是否包含数据，还需要一个Map<key,Node>来维护数据。
综上：为了实现O（1）的时间复杂度，总共需要3个Map。
逻辑分析
1、get方法：相对简单。
你看，是不是很清晰，很简单。QAQ
2、put方法：可以复用get方法。
你看复用了后是不是也很简单。
代码实现
你看，流程图有了，接下来就是编码能力了。
1、定义数据节点
class Node{
String key;
String value;
//调用次数，小于0表示头尾节点
Integer times;
Node pre;
Node next;
Node(String key, String value, Integer times){
this.key = key;
this.value = value;
this.times = times;
pre = null;
next = null;
}
}
解释下： key和value就不用了。 pre、next是双端队列的前后指针。 times:是当前节点的调用次数，目的是O（1）时间就能找到对应的双端队列的头尾节点。（因为每一个调用次数都会维护一个双端队列）
2、定义LFU的基本数据结构
public class LFUTest {
//数据Map
Map<String, Node> dataMap = new HashMap<>();
//引用次数头节点
Map<Integer, Node> headMap = new HashMap<>();
//引用次数尾节点
Map<Integer, Node> tailMap = new HashMap<>();
int size = 0;
int maxSize = 0;
//最小引用次数
int minCallTime = 1;
LFUTest(int maxSize){
this.maxSize = maxSize;
}
}
3、公告方法。从流程图可以看出，有的功能是重叠的，因此都抽出来
//创建某个引用次数的队列
private void createCallTimeDeque(int callTime){
Node head = new Node("head", "head", -1);
Node tail = new Node("tail", "tail", -1);
head.next = tail;
tail.pre = head;
headMap.put(callTime, head);
tailMap.put(callTime, tail);
}
//判断引用次数的双向队列是否空，为空则删除，
private void judgeAndDeleteCallTimeMap(int callTime){
if(headMap.get(callTime).next == tailMap.get(callTime)){
//只有head和tail（当然节点中也可以加字段表示是否是尾节点），说明队列已经空了,删除即可
headMap.remove(callTime);
tailMap.remove(callTime);
//如果该引用次数刚好是最小引用次数，则最小引用次数+1
if(callTime == minCallTime){
minCallTime++;
}
}
}
//从双向链表上删除节点
private void deleteNode(Node node){
node.next.pre = node.pre;
node.pre.next = node.next;
}
//把节点放到队首
private void addHead(Node node, Node head){
node.next = head.next;
head.next = node;
node.pre = head;
node.next.pre = node;
}
4、get方法
public Node get(String key){
//数据Map中没key，说明没数据，直接返回null
if(!dataMap.containsKey(key)){
return null;
}
Node node = dataMap.get(key);
//将数据从原来的双向队列中删除
deleteNode(node);
//获得原来的调用次数
int callTime = node.times;
//判断当前引用次数队列是否空,空则删除，同时变更最小引用数
judgeAndDeleteCallTimeMap(callTime);
callTime++;
//将节点放入下一个调用次数的双向队列
if(!headMap.containsKey(callTime)){
//不存在下一个调用次数的双向队列，所以要创建
createCallTimeDeque(callTime);
}
//将节点放入下一个调用次数的双向队列中
addHead(node, headMap.get(callTime));
//调用次数+1
node.times ++;
//完成，返回得到的数据即可
return node;
}
5、put方法
//存放数据
public void put(String key, String value){
if(dataMap.containsKey(key)){
//如果数据中已经有了数据，和get操作一致，但要重新设置value值
Node node = get(key);
//Java引用传递，所以直接重新setValue值就行
node.value = value;
return;
}
//最大容量。
if(size == maxSize){
//达到最大容量，得删除一个(最小引用数队列的队尾节点）
deleteNode(tailMap.get(minCallTime).pre);
//判断
judgeAndDeleteCallTimeMap(minCallTime);
size--;
}
//判断引用为1的队列
if(!headMap.containsKey(1)){
//不存在，就创建
createCallTimeDeque(1);
}
//创建封装数据
Node data = new Node(key, value, 1);
//将数据放在引用次数1的位置
dataMap.put(key, data);
addHead(data, headMap.get(1));
//最小引用次数为1，总数+1
minCallTime = 1;
size++;
}
最终代码
1、最终的主要代码，也不多啊，总共连回车也才150行嘛
public class LFUTest {
//定义节点
class Node{
String key;
String value;
//调用次数，小于0表示头尾节点
Integer times;
Node pre;
Node next;
Node(String key, String value, Integer times){
this.key = key;
this.value = value;
this.times = times;
pre = null;
next = null;
}
}
//数据Map
Map<String, Node> dataMap = new HashMap<>();
//引用次数头节点
Map<Integer, Node> headMap = new HashMap<>();
//引用次数尾节点
Map<Integer, Node> tailMap = new HashMap<>();
int size = 0;
int maxSize = 0;
//最小引用次数
int minCallTime = 1;
LFUTest(int maxSize){
this.maxSize = maxSize;
}
//get
public Node get(String key){
//数据Map中没key，说明没数据，直接返回null
if(!dataMap.containsKey(key)){
return null;
}
Node node = dataMap.get(key);
//将数据从原来的双向队列中删除
deleteNode(node);
//获得原来的调用次数
int callTime = node.times;
//判断当前引用次数队列是否空,空则删除，同时变更最小引用数
judgeAndDeleteCallTimeMap(callTime);
callTime++;
//将节点放入下一个调用次数的双向队列
if(!headMap.containsKey(callTime)){
//不存在下一个调用次数的双向队列，所以要创建
createCallTimeDeque(callTime);
}
//将节点放入下一个调用次数的双向队列中
addHead(node, headMap.get(callTime));
//调用次数+1
node.times ++;
//完成，返回得到的数据即可
return node;
}
//存放数据
public void put(String key, String value){
if(dataMap.containsKey(key)){
//如果数据中已经有了数据，和get操作一致，但要重新设置value值
Node node = get(key);
//Java引用传递，所以直接重新setValue值就行
node.value = value;
return;
}
//最大容量。
if(size == maxSize){
//达到最大容量，得删除一个(最小引用数队列的队尾节点）
deleteNode(tailMap.get(minCallTime).pre);
//判断
judgeAndDeleteCallTimeMap(minCallTime);
size--;
}
//判断引用为1的队列
if(!headMap.containsKey(1)){
//不存在，就创建
createCallTimeDeque(1);
}
//创建封装数据
Node data = new Node(key, value, 1);
//将数据放在引用次数1的位置
dataMap.put(key, data);
addHead(data, headMap.get(1));
//最小引用次数为1，总数+1
minCallTime = 1;
size++;
}
//打印
public void printAll(){
System.out.println("-----");
for(Integer callTime : headMap.keySet()){
Node head = headMap.get(callTime);
System.out.print(callTime+":");
while(head != null){
System.out.print( "{"+head.key+","+head.value+"}");
head = head.next;
}
System.out.println();
}
System.out.println("*****");
}
//创建某个引用次数的队列
private void createCallTimeDeque(int callTime){
Node head = new Node("head", "head", -1);
Node tail = new Node("tail", "tail", -1);
head.next = tail;
tail.pre = head;
headMap.put(callTime, head);
tailMap.put(callTime, tail);
}
//判断引用次数的双向队列是否空，为空则删除，
private void judgeAndDeleteCallTimeMap(int callTime){
if(headMap.get(callTime).next == tailMap.get(callTime)){
//只有head和tail（当然节点中也可以加字段表示是否是尾节点），说明队列已经空了,删除即可
headMap.remove(callTime);
tailMap.remove(callTime);
//如果该引用次数刚好是最小引用次数，则最小引用次数+1
if(callTime == minCallTime){
minCallTime++;
}
}
}
//从双向链表上删除节点
private void deleteNode(Node node){
node.next.pre = node.pre;
node.pre.next = node.next;
}
//把节点放到队首
private void addHead(Node node, Node head){
node.next = head.next;
head.next = node;
node.pre = head;
node.next.pre = node;
}
}
2、这里贴下测试代码吧
public static void main(String[] args) {
int data[] = new int[]{2,1,2,1,2,3,4};
LFUTest lfuTest = new LFUTest(3);
for(int i : data){
if(lfuTest.get(i+"") == null){
lfuTest.put(i+"", i+"v");
}
lfuTest.printAll();
}
lfuTest.put("4", "4+V");
lfuTest.printAll();
}
小结
LFU算法的实现主要是依靠3个Map，其中一个Map用来记录数据，一个Map记录调用次数和头节点的关系，便于直接在某个调用次数的队头插入数据。一个Map记录调用次数和尾节点的关系，便于直接将队尾的元素去除。
整体都是以空间换时间的思想。代码的复杂度为O（1），因此如果可以接受稍微高点的复杂度，那么可以将调用次数的两个Map合并成一个Deque，这样只有2个map，但是deque的常用实现类LinkedList在1.8时候删除Node是for遍历，所以删除的时间复杂度就是O（n）了；同理，如果接受get复杂度为O（n），那么可以去掉数据Map。
以上分析目的是让大家更了解为啥要用3个Map，实际场景中，一般都是追求时间复杂度而牺牲部分空间复杂度，所以基本是都是3个Map常用。
转载自:https://juejin.cn/post/7226650721985495095