力扣原题
460. LFU 缓存机制
请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。
实现 LFUCache 类：LFUCache(int capacity) - 用数据结构的容量capacity 初始化对象
int get(int key)- 如果键存在于缓存中，则获取键的值，否则返回 -1。
void put(int key, int value)- 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局(即两个或更多个键具有相同使用频率)时，应该去除 最久未使用 的键。
注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
示例：输入：
["LFUCache","put","put","get","put","get","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
输出：
[null,null,null,1,null,-1,3,null,-1,3,4]
解释：
LFUCachelFUCache=newLFUCache(2);
lFUCache.put(1,1);
lFUCache.put(2,2);
lFUCache.get(1);//返回1
lFUCache.put(3,3);//去除键2
lFUCache.get(2);//返回-1(未找到)
lFUCache.get(3);//返回3
lFUCache.put(4,4);//去除键1
lFUCache.get(1);//返回-1(未找到)
lFUCache.get(3);//返回3
lFUCache.get(4);//返回4复制代码
LFU (Least Frequently Used)缓存机制在缓存满的时候，删除缓存里使用次数最少的元素，然后在缓存中放入新元素；
数据的访问次数很重要，访问次数越多，就越不容易被删除；
根据题意，「当存在平局(即两个或更多个键具有相同使用频率)时，最近最少使用的键将被去除」，即在「访问次数」相同的情况下，按照时间顺序，先删除在缓存里时间最久的数据。
说明：本题其实就是在「力扣」第 146 题：LRU缓存机制 的基础上，在删除策略里多考虑了一个维度(「访问次数」)的信息。
核心思想：先考虑访问次数，在访问次数相同的情况下，再考虑缓存的时间。
解题思路
题目意思：缓存是有限的，在缓存满的时候，删除哪些元素，就有不同的缓存删除策略。由于题目的时间复杂度要求 O(1)，空间肯定不能省，存取数据时间性能最好的就是哈希表，因此底层的数据结构一定是一个哈希表；
又由于缓存大小有限制，删除策略是「先看访问频次，再看访问时间」，所以需要记录每个数据访问的频次；
「删除某个数据」得 O(1)，访问某个数据，时间优先级得提前(提前到当前频次最高)，这样的数据结构符合在头尾访问数据最快，并且删除其中一个结点也得是 O(1)，这种数据结构是「双向链表」；
「链表」结点得记录：1、value，2、key(在哈希表里删除的时候用得上)，3、访问次数信息，以便知道下一个访问次数是多少；4、前驱结点引用，5、后继结点引用；
哈希表存储的 key 就是题目的 key，方便快速查询和删除，value 是结点的引用，方便对结点进行操作。
下面是内存结构示意图：
每次访问一个已经存在的元素的时候：应该先把结点类从当前所属的访问次数双链表里删除，然后再添加到它「下一个访问次数」的双向链表的头部。
代码实现importjava.util.HashMap;
importjava.util.Map;
publicclassLFUCache{
/**
*key就是题目中的key
*value是结点类
*/
privateMapmap;
/**
*访问次数哈希表，使用ListNode[]也可以，不过要占用很多空间
*/
privateMapfrequentMap;
/**
*外部传入的容量大小
*/
privateIntegercapacity;
/**
*全局最高访问次数，删除最少使用访问次数的结点时会用到
*/
privateIntegerminFrequent=1;
publicLFUCache(intcapacity){
//显式设置哈希表的长度=capacity和加载因子=1是为了防止哈希表扩容带来的性能消耗
//这一步操作在理论上的可行之处待讨论，实验下来效果是比较好的
map=newHashMap<>(capacity,1);
frequentMap=newHashMap<>();
this.capacity=capacity;
}
/**
*get一次操作，访问次数就增加1；
*从原来的链表调整到访问次数更高的链表的表头
*
*@paramkey
*@return
*/
publicintget(intkey){
//测试测出来的，capacity可能传0
if(capacity==0){
return-1;
}
if(map.containsKey(key)){
//获得结点类
ListNodelistNode=removeListNode(key);
//挂接到新的访问次数的双向链表的头部
intfrequent=listNode.frequent;
addListNode2Head(frequent,listNode);
returnlistNode.value;
}else{
return-1;
}
}
/**
*@paramkey
*@paramvalue
*/
publicvoidput(intkey,intvalue){
if(capacity==0){
return;
}
//如果key存在，就更新访问次数+1，更新值
if(map.containsKey(key)){
ListNodelistNode=removeListNode(key);
//更新value
listNode.value=value;
intfrequent=listNode.frequent;
addListNode2Head(frequent,listNode);
return;
}
//如果key不存在
//1、如果满了，先删除访问次数最小的的末尾结点，再删除map里对应的key
if(map.size()==capacity){
//1、从双链表里删除结点
DoubleLinkedListdoubleLinkedList=frequentMap.get(minFrequent);
ListNoderemoveNode=doubleLinkedList.removeTail();
//2、删除map里对应的key
map.remove(removeNode.key);
}
//2、再创建新结点放在访问次数为1的双向链表的前面
ListNodenewListNode=newListNode(key,value);
addListNode2Head(1,newListNode);
map.put(key,newListNode);
//【注意】因为这个结点是刚刚创建的，最少访问次数一定为1
this.minFrequent=1;
}
//以下部分主要是结点类和双向链表的操作
/**
*结点类，是双向链表的组成部分
*/
privateclassListNode{
privateintkey;
privateintvalue;
privateintfrequent=1;
privateListNodepre;
privateListNodenext;
publicListNode(){
}
publicListNode(intkey,intvalue){
this.key=key;
this.value=value;
}
}
/**
*双向链表
*/
privateclassDoubleLinkedList{
/**
*虚拟头结点，它无前驱结点
*/
privateListNodedummyHead;
/**
*虚拟尾结点，它无后继结点
*/
privateListNodedummyTail;
/**
*当前双向链表的有效结点数
*/
privateintcount;
publicDoubleLinkedList(){
//虚拟头尾结点赋值多少无所谓
this.dummyHead=newListNode(-1,-1);
this.dummyTail=newListNode(-2,-2);
dummyHead.next=dummyTail;
dummyTail.pre=dummyHead;
count=0;
}
/**
*把一个结点类添加到双向链表的开头(头部是最新使用数据)
*
*@paramaddNode
*/
publicvoidaddNode2Head(ListNodeaddNode){
ListNodeoldHead=dummyHead.next;
//两侧结点指向它
dummyHead.next=addNode;
oldHead.pre=addNode;
//它的前驱和后继指向两侧结点
addNode.pre=dummyHead;
addNode.next=oldHead;
count++;
}
/**
*把双向链表的末尾结点删除(尾部是最旧的数据，在缓存满的时候淘汰)
*
*@return
*/
publicListNoderemoveTail(){
ListNodeoldTail=dummyTail.pre;
ListNodenewTail=oldTail.pre;
//两侧结点建立连接
newTail.next=dummyTail;
dummyTail.pre=newTail;
//它的两个属性切断连接
oldTail.pre=null;
oldTail.next=null;
//重要：删除一个结点，当前双向链表的结点个数少1
count--;
//维护
returnoldTail;
}
}
/**
*将原来访问次数的结点，从双向链表里脱离出来
*
*@paramkey
*@return
*/
privateListNoderemoveListNode(intkey){
//获得结点类
ListNodedeleteNode=map.get(key);
ListNodepreNode=deleteNode.pre;
ListNodenextNode=deleteNode.next;
//两侧结点建立连接
preNode.next=nextNode;
nextNode.pre=preNode;
//删除去原来两侧结点的连接
deleteNode.pre=null;
deleteNode.next=null;
//维护双链表结点数
frequentMap.get(deleteNode.frequent).count--;
//【注意】维护minFrequent
//如果当前结点正好在最小访问次数的链表上，并且移除以后结点数为0，最小访问次数需要加1
if(deleteNode.frequent==minFrequent&&frequentMap.get(deleteNode.frequent).count==0){
//这一步需要仔细想一下，经过测试是正确的
minFrequent++;
}
//访问次数加1
deleteNode.frequent++;
returndeleteNode;
}
/**
*把结点放在对应访问次数的双向链表的头部
*
*@paramfrequent
*@paramaddNode
*/
privatevoidaddListNode2Head(intfrequent,ListNodeaddNode){
DoubleLinkedListdoubleLinkedList;
//如果不存在，就初始化
if(frequentMap.containsKey(frequent)){
doubleLinkedList=frequentMap.get(frequent);
}else{
doubleLinkedList=newDoubleLinkedList();
}
//添加到DoubleLinkedList的表头
doubleLinkedList.addNode2Head(addNode);
frequentMap.put(frequent,doubleLinkedList);
}
publicstaticvoidmain(String[]args){
LFUCachecache=newLFUCache(2);
cache.put(1,1);
cache.put(2,2);
System.out.println(cache.map.keySet());
intres1=cache.get(1);
System.out.println(res1);
cache.put(3,3);
System.out.println(cache.map.keySet());
intres2=cache.get(2);
System.out.println(res2);
intres3=cache.get(3);
System.out.println(res3);
cache.put(4,4);
System.out.println(cache.map.keySet());
intres4=cache.get(1);
System.out.println(res4);
intres5=cache.get(3);
System.out.println(res5);
intres6=cache.get(4);
System.out.println(res6);
}
}复制代码插入一个新结点的时候，因为这个结点之前肯定没有被访问过，此时设置 minFrequent = 1，相当于归位了；
当 put 和 get 的时候，都有把当前链表里的结点移到另一个链表结点的操作。如果移除的那个链表恰好是访问次数最小链表，并且移除以后链表的结点个数为 0，minFrequent 需要加 1 。
复杂度分析时间复杂度：get 时间复杂度 O(1)，put 时间复杂度 O(1)。由于两个操作从头至尾都只利用了哈希表的插入删除还有链表的插入删除，且它们的时间复杂度均为 O(1)，所以保证了两个操作的时间复杂度均为 O(1)。
空间复杂度：O(capacity)，其中 capacity 为 LFU 的缓存容量。哈希表中不会存放超过缓存容量的键值对。
如果觉得《lfu算法c语言 LeetCode算法系列 460. LFU 缓存机制》对你有帮助，请点赞、收藏，并留下你的观点哦！
