2018-11-06 20:06:04
LFU（Least Frequently Used）算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。
如何高效的实现一个LFU Cache是一个难点，其实现方式要比LRU要复杂一点，问题的核心就是如果对不同的freq进行计数和维护。这里用到的思路和最大频率栈是类似的，也就是对每个freq都开辟一个Set来进行单独的维护。
为了实现的方便，我们可以在每个freq节点中放入一个LinkedHashSet，这样就可以很方便的进行编码。
public class LFUCache {
private FreqNode head;
private FreqNode tail;
private HashMap<Integer, Integer> key2val;
private HashMap<Integer, FreqNode> key2node;
private int capacity;
public LFUCache(int capacity) {
this.capacity = capacity;
this.head = new FreqNode(0);
this.tail = new FreqNode(Integer.MAX_VALUE);
this.key2val = new HashMap<>();
this.key2node = new HashMap<>();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (capacity == 0) return -1;
if (key2val.containsKey(key)) {
int res = key2val.get(key);
increaseFreq(key);
return res;
}
return -1;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (key2val.containsKey(key)) {
key2val.put(key, value);
increaseFreq(key);
}
else {
maintainSize();
key2val.put(key, value);
key2node.put(key, head);
head.keys.add(key);
increaseFreq(key);
}
}
private void increaseFreq(int key) {
FreqNode cur = key2node.get(key);
FreqNode next = null;
if (cur.next.freq == cur.freq + 1) {
next = cur.next;
}
else {
next = new FreqNode(cur.freq + 1);
next.next = cur.next;
cur.next.prev = next;
cur.next = next;
next.prev = cur;
}
next.keys.add(key);
cur.keys.remove(key);
key2node.put(key, next);
if (cur.keys.size() == 0 && cur != head) delete(cur);
}
private void maintainSize() {
if (key2val.size() >= capacity) {
FreqNode cur = head.next;
Iterator<Integer> iter = cur.keys.iterator();
int key = iter.next();
key2val.remove(key);
key2node.remove(key);
cur.keys.remove(key);
if (cur.keys.size() == 0) delete(cur);
}
}
private void delete(FreqNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
class FreqNode {
public int freq;
public FreqNode prev ;
public FreqNode next;
public LinkedHashSet<Integer> keys;
public FreqNode(int freq) {
this.freq = freq;
prev = null;
next = null;
keys = new LinkedHashSet<>();
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/