LFU Chache 24
Question
LFU (Least Frequently Used) is a famous cache eviction algorithm.
For a cache with capacity k, if the cache is full and need to evict a key in it, the key with the lease frequently used will be kicked out.
Implement set and get method for LFU cache.
Example
Given capacity=3
set(2,2)
set(1,1)
get(2)
2
get(1)
1
get(2)
2
set(3,3)
set(4,4)
get(3)
-1
get(2)
2
get(1)
1
get(4)
4
Solution
与LRU类似。用HashMap来存key及其对应node。用PriorityQueue(MinHeap)来对HashMap中的node以frequence为key进行排序（重构Comparator
代码如下：
public class test {
private class Node{
int key;
int value;
int freq;
public Node(int key, int value, int freq){
this.key = key;
this.value = value;
this.freq = freq;
}
}
HashMap<Integer, Node> map = new HashMap<Integer, Node>();
PriorityQueue<Node> queue = new PriorityQueue<Node>(new Comparator<Node>(){
public int compare(Node node1, Node node2){
return node1.freq - node2.freq;
}
});
int capacity = 3;
public static void main(String[] args){
test t = new test();
t.set(2,2);
t.set(1, 1);
System.out.println(t.get(2));
System.out.println(t.get(1));
System.out.println(t.get(2));
t.set(3, 3);
t.set(4, 4);
System.out.println(t.get(3));
System.out.println(t.get(2));
System.out.println(t.get(1));
System.out.println(t.get(4));
}
private int get(int key){
if(!map.containsKey(key)){
return -1;
}
Node curt = map.get(key);
int res = curt.value;
curt.freq++;
return res;
}
private void set(int key, int value){
if(map.containsKey(key)){
map.get(key).value = value;
map.get(key).freq++;
return;
}
if(map.size() == capacity){
Node curt = queue.poll();
map.remove(curt.key);
}
Node node = new Node(key, value, 1);
map.put(key, node);
queue.offer(node);
}
}