LFU

Least Frequently Cache

1.Idea

Least Frequently Used (LFU) is a type of cache algorithm used to manage memory. The standard characteristics of this method involve the system keeping track of the number of times a item is referenced in memory. When the cache is full and requires more room the system will purge the item with the lowest reference frequency.

2.Implementation

// Use three hashmap + linkedHashSet
public class LFUCache {
    int min;
    int capacity;
    Map<Integer, Integer> values;
    Map<Integer, Integer> freq;

    // Map frequency to a group of keys
    // The head of the LinkedHashSet is the LRU key
    Map<Integer, LinkedHashSet<Integer>> freqToLRUKeys;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.min = -1;
        values = new HashMap<>();
        freq = new HashMap<>();
        freqToLRUKeys = new HashMap<>();
    }

    public int get(int key) {
        if (!values.containsKey(key)) {
            return -1;
        }

        // Update frequency
        int count = freq.get(key);
        freq.put(key, count + 1);

        freqToLRUKeys.get(count).remove(key);
        // When count is equal to min and the bucket of min is equal to zero, update min
        if (count == min && freqToLRUKeys.get(count).size() == 0) {
            ++min;
        }

        // Update freqToLRUKeys
        if (!freqToLRUKeys.containsKey(count + 1)) {
            freqToLRUKeys.put(count + 1, new LinkedHashSet<>());
        }
        freqToLRUKeys.get(count + 1).add(key);
        return values.get(key);
    }

    public void put(int key, int value) {
        if (capacity <= 0) {
            return;
        }

        // If key exist in the map, update it
        if (values.containsKey(key)) {
            values.put(key, value);
            get(key);
            return;
        }

        // If out of capacity, remove the least frequently used key
        if (values.size() >= capacity) {
            int evictedKey = freqToLRUKeys.get(min).iterator().next();
            freqToLRUKeys.get(min).remove(evictedKey);
            freq.remove(evictedKey);
            values.remove(evictedKey);
        }

        // If key doesn't exist in the map, add it
        values.put(key, value);
        freq.put(key, 1);

        // The min frequency should be 1
        min = 1;
        if (!freqToLRUKeys.containsKey(1)) {
            freqToLRUKeys.put(1, new LinkedHashSet<Integer>());
        }
        freqToLRUKeys.get(1).add(key);
    }
}

3.Time & Space Complexity

1. get: O(1)

2. put: O(1)

3. Space: O(n), where n is the capacity