LFU Cache

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.

Solution:

Same idea to LRU Cache, but a combination of HashMap and PriorityQueue would be more suitable due to the frequency. Timestamp is used to hybrid with LRU. To be specific, when two or more datanode have same frequency, we remove the one with least recent used.

Code:

class DataNode {
    int val;
    int key;
    int timestamp;
    int freq;
    public DataNode(int inKey, int inVal, int inTimestamp) {
        this.key = inKey;
        this.val = inVal;
        this.freq = 1;
        this.timestamp = inTimestamp;
    }
    public void hit(int inTimestamp) {
        this.freq += 1;
        this.timestamp = inTimestamp;
    }
}

public class LFUCache {

    private HashMap<Integer, DataNode> hmap;
    private Queue<DataNode> q;
    private int capacity;
    private int timestamp;

    public LFUCache(int inCapacity) {
        this.capacity = inCapacity;
        this.hmap = new HashMap<>();
        this.q = new PriorityQueue<>(capacity, new Comparator<DataNode>() {
            public int compare(DataNode a, DataNode b) {
                if (a.freq != b.freq) {
                    return a.freq - b.freq;
                }
                return a.timestamp - b.timestamp;
            } 
        });
    }

    public void set(int key, int value) {
        if (get(key) != -1) {
            hmap.get(key).val = value;
            return;
        }
        DataNode newNode = new DataNode(key, value, getTimestamp());
        if (q.size() >= capacity) {
            DataNode node = q.poll();
            hmap.remove(node.key);
        }
        q.offer(newNode);
        hmap.put(key, newNode);
    }

    public int get(int key) {
        if (!hmap.containsKey(key)) {
            return -1;
        }
        DataNode dn = hmap.get(key);
        q.remove(dn);
        dn.hit(getTimestamp());
        q.offer(dn);
        return dn.val;
    }

    private int getTimestamp() {
        this.timestamp++;
        return this.timestamp;
    }
}