class LFUCache {
class Node{
int key;//key
int val;//val
int freq;//使用频率
int t;//最后一次被使用的时间
public Node(int key,int val,int freq,int t){
this.key = key;
this.val = val;
this.freq = freq;
this.t = t;
}
}
class NodeComparator implements Comparator{
//当使用频率不一样时 按使用频率升序排序
public int compare(Node n1,Node n2){
if(n1.freq != n2.freq)
return n1.freq - n2.freq;
else//当使用频率一样的时候 按使用的时间升序排序
return n1.t - n2.t;
}
}
private Map map;
private TreeSet set;
//时间计数器 从0开始
private int t;
//LFU缓存的容量
private int capacity;
public LFUCache(int capacity) {
this.map = new HashMap<>();
this.set = new TreeSet<>(new NodeComparator());
this.t = 0;
this.capacity = capacity;
}
public int get(int key) {
//时间计数器加一
this.t += 1;
if(map.get(key) == null){
return -1;
}
else{
Node node = map.get(key);
set.remove(node);
//该key的使用频率加一
node.freq = node.freq + 1;
//更新key最后被使用的时间
node.t = this.t;
set.add(node);
map.put(key,node);
return node.val;
}
}
public void put(int key, int value){
if(this.capacity == 0)
return ;
this.t += 1;
//如果key本来就存在于map中
if(map.get(key)!=null){
Node node = map.get(key);
set.remove(node);
//更新val值
node.val = value;
//更新最后使用时间
node.t = this.t;
//使用频率加一
node.freq = node.freq + 1;
set.add(node);
map.put(key,node);
}else{
//如果LFU缓存中没有空间 弹出最近最久未使用的
if(set.size() >= this.capacity){
map.remove(set.first().key);
set.remove(set.first());
}
Node node = new Node(key,value,1,this.t);
map.put(key,node);
set.add(node);
}
}
}
哈希表 + 双向链表
class LFUCache {
class Node{
int key;//key
int val;//val
int freq;//key 使用频率
Node prev;//前驱指针
Node next;//后驱指针
public Node(int key,int val,int freq){
this.key = key;
this.val = val;
this.freq = freq;
}
}
class DoublyLinkedList{
//双向链表
Node head;//头指针
Node tail;//尾指针
int size;//双向链表中节点个数
public DoublyLinkedList(){
head = new Node(0,0,0);//头节点
tail = new Node(0,0,0);//尾节点
head.next = tail;
tail.prev = head;
size = 0;
}
public void addFirst(Node node){
Node headNext = head.next;
head.next = node;
node.prev = head;
node.next = headNext;
headNext.prev = node;
size += 1;
}
public void remove(Node node){
Node nodePrev = node.prev;
Node nodeNext = node.next;
nodePrev.next = nodeNext;
nodeNext.prev = nodePrev;
size -= 1;
}
public Node getHead(){
return head.next;
}
public Node getTail(){
return tail.prev;
}
}
// key, Node
private Map keyMap;
//每个频率 对应的节点放在双向链表中 双向链表按操作时间排序 越久没操作的节点在链表中的位置越靠后
private Map freqMap;
//LFU缓存容量
private int capacity;
//最小操作频率
private int minFreq;
public LFUCache(int capacity) {
keyMap = new HashMap<>();
freqMap = new HashMap<>();
this.capacity = capacity;
minFreq = 0;
}
public int get(int key) {
if(this.capacity == 0)
return -1;
if(keyMap.get(key) == null){
return -1;
}
else{
Node node = keyMap.get(key);
DoublyLinkedList dl = freqMap.get(node.freq);
dl.remove(node);
if(dl.size == 0){
freqMap.remove(node.freq);
if(node.freq == minFreq)
minFreq += 1;
}
node.freq += 1;
if(freqMap.get(node.freq) == null)
freqMap.put(node.freq,new DoublyLinkedList());
freqMap.get(node.freq).addFirst(node);
keyMap.put(key,node);
return node.val;
}
}
public void put(int key, int value) {
if(this.capacity == 0)
return ;
if(keyMap.containsKey(key)){
Node node = keyMap.get(key);
DoublyLinkedList dl = freqMap.get(node.freq);
dl.remove(node);
if(dl.size == 0){
freqMap.remove(node.freq);
if(node.freq == minFreq)
minFreq += 1;
}
node.freq += 1;
node.val = value;
if(freqMap.get(node.freq) == null)
freqMap.put(node.freq,new DoublyLinkedList());
freqMap.get(node.freq).addFirst(node);
keyMap.put(key,node);
}
else{
if(keyMap.size() >= capacity){
Node node = freqMap.get(minFreq).getTail();
keyMap.remove(node.key);
freqMap.get(minFreq).remove(node);
if(freqMap.get(minFreq).size == 0)
freqMap.remove(minFreq);
}
Node newNode = new Node(key,value,1);
if(freqMap.get(newNode.freq) == null)
freqMap.put(newNode.freq,new DoublyLinkedList());
freqMap.get(newNode.freq).addFirst(newNode);
minFreq = 1;
keyMap.put(key,newNode);
}
}
}



